Match Editorial

Match summary

Happy new year ! The first SRM in 2009 attracted 1143 coders.  Div 2 easy was easy as always. Div 1 easy / Div 2 medium was not so standard and confused lots of coders. Div 1 Medium was tricky - like many other mediums. Hard problems in both division were solvable and about 20 coders in each division proved it.

Div 1 was won by Petr, who had the fastest solution for hard and earned 25 points in challenges. He was closely followed by WSX and Ostap. Both of them made succesfull challenges and needed one more to win this match and their rooms were full of wrong mediums, but they didn't use their chance. Great result anyway.

Div 2 was won by Alex_KPR, who had good times on all 3 problems. He was followed by hellodj and newcomer adrianoo07.

Value	250
Submission Rate	565 / 609 (92.78%)
Success Rate	538 / 565 (95.22%)
High Score	accn for 249.99 points (0 mins 12 secs)
Average Score	204.09 (for 538 correct submissions)

Of course, we should check each word separately. To check the given word, we should use definition: try all pairs of equal letters, and check if there is any different letter between them.

Alternatively, we can only check the letter after the first letter of that pair. There are some faster algorithms, but this one requires less code:

public int howMany(String[] words) {
  int ans = 0;
  for (int i = 0; i < words.length; i++) {
    boolean grouped = true;
    for (int j = 0; j < words[i].length()-1; j++)
      if (words[i].charAt(j) != words[i].charAt(j+1))
        for (int k = j+1; k < words[i].length(); k++)
          if (words[i].charAt(j) == words[i].charAt(k))
            grouped = false;
    if (grouped) ans++;
  }
  return ans;
}

Value	500
Submission Rate	243 / 609 (39.90%)
Success Rate	107 / 243 (44.03%)
High Score	Alex_KPR for 459.73 points (8 mins 33 secs)
Average Score	279.85 (for 107 correct submissions)

Value	250
Submission Rate	478 / 534 (89.51%)
Success Rate	375 / 478 (78.45%)
High Score	lovro for 247.91 points (2 mins 36 secs)
Average Score	196.29 (for 375 correct submissions)

Sooner or later you should notice one very important fact: all equal rows remain equal after any number of flips. So, if some row is lit at any moment, all initially equal rows will be lit as well and all other rows will not be lit. Therefore, the solution is to try for each row to make lit, and if it is possible, count the number of rows equal to this one and choose among such rows one with the maximal number of equal rows.

How to check if the given row can be lit after exactly K flips ? Note that the order of flips doesn't affect on the final result. Also, making 2 flips in the same column doesn't change row at all. Suppose we have M "off" lamps in this row. To be able to switch all these lamps to the "on" state we need exactly M flips. So, K should be no less than M. Now, if (K-M) is even, we can flip always the first column and at the end the row will be lit. If (K-M) is odd, it's impossible to lit this row after exactly (K-M) flips.

Take a look at lovro's code for a good example of using STL.

TreesDivision
Used as: Division Two - Level Three:

Value	1000
Submission Rate	53 / 609 (8.70%)
Success Rate	20 / 53 (37.74%)
High Score	adrianoo07 for 764.04 points (16 mins 55 secs)
Average Score	584.50 (for 20 correct submissions)

This problem needs a method, which is very common in geometry problems.

As there are at least 2 points, the optimal line always lies between some two points. We can move it so, that it "touches" (in this case it means that it is close enough) some point. After that, we can rotate this line from that point so, that it touches another point and these two touching points are on the different sides of it. So, we can start searching this line as the one, that touchs any two of the given points. Note, that these two points should not contain other points in the same line between them. In this case, that line wouldn't touch these two points and would touch other two points earlier.

For two fixed points, there are 2 ways to draw such line: In the first case the first point in on the left side from this line and the second point on the right side and in the second case - vice versa. For both cases we can determine which trees go to which brother. We will choose optimal line among all such possible lines.

To be able to do all the computations in integer numbers, reading Geometry tutorial would be useful.

Sample solution in Java:

private boolean between(int x1, int y1, int x2, int y2, int x, int y) {
  if (x < Math.min(x1, x2) || x > Math.max(x1, x2)) return false; 
  if (y < Math.min(y1, y2) || y > Math.max(y1, y2)) return false;
  return true;
}
public int minDifference(int x[], int y[], int income[]) {
  int best = Integer.MAX_VALUE, i, j, k, n = x.length, pa, pb, qa, qb;
  boolean good;
  // Line that touches points i and j                
  for (i = 0; i < n; i++) {
    for (j = i+1; j < n; j++) {
      good = true;
      // pa - First brother in the first case
      // qa - First brother in the second case
      pa = qa = income[i];
      // pb - Second brother in the first case
      // qb - Second brother in the second case
      pb = qb = income[j];
      for (k = 0; k < n; k++)
        if (k != i && k != j) {
          int dir = (x[i]-x[j])*(y[i]-y[k]) - (x[i]-x[k])*(y[i]-y[j]);
          if (dir < 0) {
            pa += income[k];
            qb += income[k];
          } else if (dir > 0) {
            pb += income[k];
            qa += income[k];
          } else {
            if (between(x[i], y[i], x[j], y[j], x[k], y[k])) {
              // Some point between
              good = false;
              break;
            } else if (between(x[i], y[i], x[k], y[k], x[j], y[j])) {
              pb += income[k];
              qb += income[k];
            } else {
              pa += income[k];
              qa += income[k];
            }
          }
        }
      if (good) {
        best = Math.min(best, Math.abs(pa - pb));
        best = Math.min(best, Math.abs(qa - qb));
      }
    }
  }
  return best;
}

Value	500
Submission Rate	345 / 534 (64.61%)
Success Rate	87 / 345 (25.22%)
High Score	Krzysan for 445.60 points (10 mins 10 secs)
Average Score	248.18 (for 87 correct submissions)

There are many different solutions for this problem, but as it's success rate and the number of resubmits suggest, most of them are either wrong or at least they need to consider some special cases which are not so easy to find. We will describe the algorithm, which is not hard to prove correct and can be coded without much troubles.

In the beginning, we join any two words that should be joined until no such two words exist. Two words p and s should be joined, if there is some letter c such, that p ends with c and s begins with c. In this case we should change these two words with p+s. But there is main and the only trick in this solution: we should care about words which consist only of letters c. We should insert all these words between p and s. We can, for example at the beginning join those words, which consist of all equal letters and then unite all the other words. In fact, having all letters equal isn't necessary, it's enough that it's first and last letters are equal.

After joinings are done, we have one or more words that couldn't be joined more. Now, let's take their concatenation in any order. If the resulting word isn't grouped, then answer is "IMPOSSIBLE". Otherwise, all concatenations (which differ with words order) will give us all possible original words. Therefore, if after the joining process we get exactly one word, this word is the answer. Otherwise, the answer is "MANY".

zhuojie's solution does what's described here. Krzysan's very fast submission uses the same ideas.  

Exercise 1. Prove that the described algorithm is correct.

Exercise 2. Find a linear algorithm for this problem.

BuildersCountry
Used as: Division One - Level Three:

Value	1000
Submission Rate	42 / 534 (7.87%)
Success Rate	21 / 42 (50.00%)
High Score	Petr for 708.88 points (20 mins 1 secs)
Average Score	548.05 (for 21 correct submissions)

Like many other "hard" problems - this one relies on the smaller subproblems.

In the beginning, let's determine how much is paid to builders for building houses in the same city. In the i-th city, the first house costs before[i]*houseCost[i], the second (before[i]+1)*houseCost[i], ..., the last - (after[i]-1)*houseCost[i]. The total cost is houseCost[i]*(before[i]+after[i]-1)*(after[i]-before[i])/2. Now we will think about how to reduce "between cities" and road building payments.

Consider the second building phase for only two cities i and j connected by a road. When building after[i]-before[i] new houses in the i-th city, each of old before[j] builders int the j-th city will get houseCost[i] units of money, so this expense equals to (after[i]-before[i])*before[j]*houseCost[i]. Similarly, after building new houses in the j-th city, old i-th city builders are paid (after[j]-before[j])*before[i]*houseCost[j] units of money in total. What's left is how much money will new builders get.

Consider any new house x in the i-th city and new house y in the j-th city. If house x is built before house y, the builder from x will get houseCost[j] units of money for (x,y) houses pair. If house y is built before x, the builder from y will get houseCost[i] units for the same (x,y) pair.

Note that for each such (x,y) pair we will have to pay some amount - either houseCost[i] or houseCost[j], depending on which house is built before. We don't have any other expenses. From it we can conclude, that it's always better to build first all the houses in the city, which has more houseCost. So, the minimal total payment for new builder is Min(houseCost[i], houseCost[j])*(after[i] - before[i])*(after[j] - before[j]).

Now consider the second building phase for any number of cities. It's not hard to see that the same happens here: for any pair of houses x and y from the neighboring cities - we have to pay money to builder either from x or y (except the case when both x and y are old houses), depending on which one is built earlier. So, it's always profitable to build each time a new possible house in the city with maximal houseCost.

It's time to combine both phases of building. When building a new road between cities i and j, we have to pay not only roadCost*(before[i]+before[j]) units of money for constructing it, also we must consider that it adds to our expenses (after[i]-before[i])*before[j]*houseCost[i]+(after[j]-before[j])*before[i]*houseCost[j]+Min(houseCost[i],houseCost[j])*(after[i] - before[i])*(after[j] - before[j]) units. So, their sum is the actual cost of that road. If this road already exists, we only add that last amount to our answer.

The remaining part is clear - we must construct Minimal Spanning Tree (MST) from all existing and possible new roads (In fact it's not exactly spanning tree, there are some more edges). For it, you can use either Kruskal's or Prim's algorithm.

... and be careful - int overflow!

 Take a look at Petr's the fastest correct submission. If you like Prim's algorithm more, Alexus's solution does with it.