Tuesday, January 6th, 2009 Match summaryHappy 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. GroupedWordCheckerUsed as: Division Two  Level One:
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) {LampsGrid Used as: Division Two  Level Two: Used as: Division One  Level One:
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 (KM) is even, we can flip always the first column and at the end the row will be lit. If (KM) is odd, it's impossible to lit this row after exactly (KM) flips. Take a look at lovro's code for a good example of using STL.
TreesDivision
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) {GroupedWord Used as: Division One  Level Two:
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
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 ith 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 ith city, each of old before[j] builders int the jth 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 jth city, old ith 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 ith city and new house y in the jth 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. 
