JOIN
 Match Editorial
SRM 360
Tuesday, July 24, 2007

## 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

AzimuthMonitoring
Used as: Division Two - Level One:
 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.

SumOfSelectedCells
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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

A1 A1 A1 ... A1 A1
A2 A2 A2 ... A2 A2
.
.
AH AH AH ... AH AH

This condition is necessary and turns out to be sufficient, because in such table, Jessie's sum will always equal A1 + A2 + ... + AH.

Similarly, if the height is greater than the width, checking the hypothesis reduces to checking that the table is of the following form:

A1 A2 ... AW
A1 A2 ... AW
A1 A2 ... AW
.
.
A1 A2 ... AW
A1 A2 ... AW

Now, consider a square table. Take four cells on the intersections of two rows and two columns: Aip, Ajp, Aiq, Ajq.

Assume the following inequality: Aip + Ajq ≠ Ajp + Aiq. 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:

A11 + Aij = Ai1 + A1j

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.

TakeSubstringGame
Used as: Division Two - Level Three:
 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.

PrinceOfPersia
Used as: Division One - Level Two:
 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.

Approach 1: MaxFlow

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 Ax and Bx, and an edge Ax → Bx with capacity 1.
• For each pair of adjacent empty cells x and y create edges Bx → Ay and By → Ax of infinite capacity.
• If p is the Prince's cell and q is the Princess's cell, call Bp the source and Aq 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(S3) and each check takes O(S), thus the complexity is O(S4).

ConvexArray
Used as: Division One - Level Three:
 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.

By darnley
TopCoder Member