Match Editorial

Match summary

If 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 1000-pointer was the fastest. Top 3 was rounded out by Petr, who continues in his long-term 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 1000-pointer that allowed them to place in the top three without any successful challenges.

The Problems

Value	250
Submission Rate	616 / 670 (91.94%)
Success Rate	445 / 616 (72.24%)
High Score	tstan436 for 246.09 points (3 mins 35 secs)
Average Score	192.90 (for 445 correct submissions)

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.

Value	500
Submission Rate	233 / 670 (34.78%)
Success Rate	23 / 233 (9.87%)
High Score	omeometo for 429.06 points (11 mins 57 secs)
Average Score	247.33 (for 23 correct submissions)

Value	250
Submission Rate	500 / 573 (87.26%)
Success Rate	196 / 500 (39.20%)
High Score	Egor for 241.39 points (5 mins 24 secs)
Average Score	160.62 (for 196 correct submissions)

In this problem, a square table turns out to be a special case. Let's investigate the non-square 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₁ A₁ A₁ ... A₁ A₁
A₂ A₂ A₂ ... A₂ A₂
.
.
A_H A_H A_H ... A_H A_H

This condition is necessary and turns out to be sufficient, because in such table, Jessie's sum will always equal A₁ + A₂ + ... + 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₁ A₂ ... A_W
A₁ A₂ ... A_W
A₁ A₂ ... A_W
.
.
A₁ A₂ ... A_W
A₁ A₂ ... 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₁₁ + 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.

Value	1000
Submission Rate	54 / 670 (8.06%)
Success Rate	19 / 54 (35.19%)
High Score	omeometo for 749.92 points (17 mins 41 secs)
Average Score	570.02 (for 19 correct submissions)

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, single-digit 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.
Otherwise, it is losing.

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.

Value	500
Submission Rate	319 / 573 (55.67%)
Success Rate	144 / 319 (45.14%)
High Score	jakubr for 457.44 points (8 mins 49 secs)
Average Score	300.17 (for 144 correct submissions)

Based on a classical video game plot, this problem allowed two approaches.

Note: 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:

• For each empty cell x create two vertices A_x and B_x, and an edge A_x → B_x with capacity 1.
• For each pair of adjacent empty cells x and y create edges B_x → A_y and B_y → A_x of infinite capacity.
• If p is the Prince's cell and q is the Princess's cell, call B_p the source and A_q the sink of the network.

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 Max-flow min-cut theorem.

There is a (still increasing) number of maximum flow algorithms, many of which could have been implemented in this problem, say Ford-Fulcerson algorithm implemented by Petr in his solution.

Note that an infinite maximum flow corresponds to the answer -1.

Approach 2: Specificity of the problem

The answer is -1 if and only if the two 'P' cells are adjacent.

If they are not, here's a non-optimal 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³) and each check takes O(S), thus the complexity is O(S⁴).

Value	1000
Submission Rate	56 / 573 (9.77%)
Success Rate	30 / 56 (53.57%)
High Score	ACRush for 740.04 points (18 mins 14 secs)
Average Score	567.91 (for 30 correct submissions)

First, imagine a n-gon 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 n-gon with n > 3, then the last two concatenated integers were unnecessary.

From this, the following statement arises:
Let n be the length of beginning. If the answer is not {-1}, then the length of the answer equals m = max(6 - n, n % 2).

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 five-point 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.