Tuesday, July 24, 2007 Match summaryIf each SRM makes the TopCoder community one degree better, we're on the spot where we started more than 6 years ago. Because 360 degrees make a full cycle. SRM 360 Division 1 leader's title was taken by Egor, thanks to his five successful challenges, allowing him to regain a target sign. Second place went to ACRush, whose 1000pointer was the fastest. Top 3 was rounded out by Petr, who continues in his longterm struggle for new records. Division 2 victory was deserved by Japanese newcomer omeometo, who promises to be a worthy Div 1 competitor: no one else could solve both the medium and the hard. shravas and yiyiyi4321 follow, both with good time on the 1000pointer that allowed them to place in the top three without any successful challenges. The ProblemsAzimuthMonitoringUsed as: Division Two  Level One:
There was no trick in this problem. The correct solution was to follow the given instructions one by one and calculate the new azimuth correctly after each instruction. A slippery place is the fact that the azimuth must be between 0 and 359. A natural way to implement it is to write azimuth += change; // ATTENTION! azimuth %= 360; // IT'S WRONG! Be aware that the remainder operation '%' can return negative result, for example (99) % 360 produces 99 (566) % 360 produces 206 A detailed explanation can be found in Java Language Specification or other sources. To take a remainder modulo 360 and ensure it's between 0 and 359, one can write azimuth = ((azimuth % 360) + 360) % 360; // Works for general case or azimuth = (azimuth + 360) % 360; // In this specific problem The fastest solution by tstan436 explains what was expected. SumOfSelectedCellsUsed as: Division Two  Level Two: Used as: Division One  Level One:
In this problem, a square table turns out to be a special case. Let's investigate the nonsquare case first. Suppose the width of the table is greater that its height. The number of cells selected by Jessie will be the height of the table. Hence it is possible to unselect one cell and select another one in the same row. In order for the hypothesis to be correct, the integers written in these two cells must be equal. Consequently, the entire table should look like
A_{1} A_{1} A_{1} ... A_{1} A_{1} This condition is necessary and turns out to be sufficient, because in such table, Jessie's sum will always equal A_{1} + A_{2} + ... + A_{H}. Similarly, if the height is greater than the width, checking the hypothesis reduces to checking that the table is of the following form:
A_{1} A_{2} ... A_{W} Now, consider a square table. Take four cells on the intersections of two rows and two columns: A_{ip}, A_{jp}, A_{iq}, A_{jq}. Assume the following inequality: A_{ip} + A_{jq} ≠ A_{jp} + A_{iq}. In this case, in some Jessie's selection, she can unselect the left two integers and select the right two, thus changing the overall sum. Hence, in order to satisfy the hypothesis, all such pairs of sums should be equal. Fortunately, the opposite also holds: if all equalities are satisfied, the hypothesis is correct. More detailed analysis shows that it is enough to check the following equality for all i and j: A_{11} + A_{ij} = A_{i1} + A_{1j} By the way, that means that one column and one row determine the rest of the table. Egor showed the best understanding of this problem, writing a coherent and fast solution first, and making 5 successful challenges later. TakeSubstringGameUsed as: Division Two  Level Three:
The contestants were asked to find a winning strategy for yet another impartial game. As explained in a previously written tutorial, such games should most usually be analyzed in terms of winning and losing positions. In this game, position is the number written on the board. According to the rules, singledigit numbers 1 through 9 are losing positions, because the player that faces such number can't make a move. For all greater numbers, the following general rule should be used: If there is a move from the current position to a losing position, then
the current position is winning. The following pseudocode performs the analysis of all the positions. for i = 10 to n do for m : all proper substrings of i do if (m > 0) and (not winning[i  m]) then // There is a move to a losing position. winning[i] = true; Now, if winning[n] is true, find the smallest substracted m that leads us to a losing position and return this m. PrinceOfPersiaUsed as: Division One  Level Two:
Based on a classical video game plot, this problem allowed two approaches. Approach 1: MaxFlowNote: to understand this approach one needs a thorough understanding of flow networks. A tutorial is available in the Educational Content section. Build a flow network according to the following rules:
Now a route from the Prince to the Princess corresponds to a simple flow of size 1 in this network. And the suggested problem is to find the size of the minimum cut, which is the same as the size of maximum flow, according to the Maxflow mincut theorem. There is a (still increasing) number of maximum flow algorithms, many of which could have been implemented in this problem, say FordFulcerson algorithm implemented by Petr in his solution. Note that an infinite maximum flow corresponds to the answer 1. Approach 2: Specificity of the problemThe answer is 1 if and only if the two 'P' cells are adjacent. If they are not, here's a nonoptimal solution for Jaffar: lock the poor Princess. She has 0 to 4 empty cells adjacent to her cell, so put obstacles in each of these cells and prevent her from any movement. Hence, the correct answer for the problem is no more than 4. How can we check that the answer is 3 or less? Iterate over all triples of empty cells, and for each triple try to put obstacles in these three cells and check whether the Prince and the Princess are disconnected. To check this property use any graph search algorithm, DFS being probably the easiest to implement. Similarly, (better even before checking triples) check the empty set of cells, all single empty cells and all pairs of empty cells. As soon as the set being checked separates the heroes, return the size of that set. If S is the size of the maze (height × width), the number of sets to check is O(S^{3}) and each check takes O(S), thus the complexity is O(S^{4}). ConvexArrayUsed as: Division One  Level Three:
First, imagine a ngon with n > 3. Remove the last vertex. The remainder is still a valid convex polygon. Thus if we can concatenate some array of length 2+ to our beginning and get a valid ngon with n > 3, then the last two concatenated integers were unnecessary. From this, the following statement arises: Now, the correct solution is to check all arrays of length m in lexicographical order, and for each array check whether beginning concatenated with this one gives a convex array. How to check that an array is convex? The first three conditions are already satisfied, provided we only consider arrays of length m containing integers of range 1..50. Now check the convexity. Since 180 degree angles are not allowed, we are to check that orientation of all triples of consecutive vertices is the same. Probably, if the 4th example weren't given, a number of coders wouldn't go beyond this check. But it is useful to know that this check is incomplete, the simplest counterexample being a fivepoint star. There are several workarounds to that, here's a suggestion that is easy to code: count the groups of consecutive vertices with strictly increasing y coordinates, and the groups with strictly decreasing y coordinates. In a simple polygon there will be no more than 3 such groups. In all polygons that were falsely considered convex by the previous check, this number will be at least 4. (Prove this as an exersize.) The only dubious place is how do we check all the arrays when m is 6 (or 5). Well, the specificity of the problem delights us here: when searched lexicographically, the correct answer {1, 1, 1, 2, 2, 1} will be found instantaneously. 
