Judges' Comments on the Problems and their Solutions

Problem A: Automatic Correction of Misspellings

This problem can be solved in at least two ways.
The first possibility is to write a function which determines if two words are similar or not, and then for each query go through the dictionary to find a similar word.
The second possibility is to generate all words which are similar to the query word and look in the dictionary if it contains such a word. Note that this lookup should be efficient, a linear search will be too slow.

Judges' test data consists of one random-generated test case with 10000 dictionary words and 1000 query words.

Rating: Easy

Reference

Problem B: Basic wall maze

This is a typical shortest-path problem. The only tricky part is how to handle the walls. One possibility which is used in the judge solution is to double the size of the grid and use the even grid positions (0 to 12) for walls and the odd grid positions for the original cells of the grid.
Since the size of the grid is so small, all well-known polynomial time shortest-path algorithms should run in time. The worst case has a shortest path of 25 steps, therefore a naive algorithm which is exponential in the length of the shortest path will be too slow.

Judges' test data is derived from the judge output of problem C.

Rating: Easy

Problem C: Construct the wall maze

This problem is the hardest problem of the problem set.
The solution consists of three parts: The first part is to check if two walls intersect, the second part is to check for a finished maze whether the given path is still valid, and the third part is to check that there is no shorter path possible.
The maze is constructed by using an optimized backtracking algorithm. The optimization idea is the following: When you have a wall which does not touch the given path, it is basically unused, so it can be placed on one of the borders as well. This works because there are 4 borders, but only 3 walls.

Judges' test data consists of 23 hand-crafted test cases.

Rating: Hard

Problem D: Dihedral groups

For solving this problem the following basic observation is necessary:
A configuration can be described by the number of rotations (a number between 0 and n-1) followed by the number of mirror operations (0 or 1).
Therefore the first step of the solution is to calculate the configuration resulting from the input sequence. After that we have to identify the minimum number of operations needed to get this specific configuration.

• If the configuration has the form r<a> m1, we can either construct it as "m1 r<n-a>" or as "r<a> m1".
• If the configuration has the form r<a> m0, we can either construct it as "m1 r<n-a> m1" or "r<a>".

Now the only thing left to take care of is to omit operations if they need not be used, i.e, r0 and m0 should not be printed. Note that since it is guaranteed that n is at least 3, we don't have to care about the case that a mirror operation does not change the configuration.

Judges' test data consists of 24 test cases. Most of the test cases are random-generated.

Rating: Medium

Problem E: Economic phone calls

This problem can be solved by either dynamic programming or greedy.
In the dynamic programming solution we calculate for each phone call i how many of the later phone calls we have to keep if we keep phone call i. To make things easier we first calculate the year of every phone call in the input by using the year recovery procedure described in the problem statement.
Let keep(i) denote the minimum number of later phone calls to be kept if we keep phone call i. Then, the recurrence relation looks as follows:

• keep(i) = 0 if phone call i occurred in the current year and there is no important phone call after phone call i.
• keep(i) = min_{j=i+1..n}(keep(j)+1) where phone call j appeared less than two years later, and there is no important phone call between phone call i and phone call j.

Obviously we can delete all phone calls which have appeared earlier than the first important phone call, so if phone call p is the first important phone call, keep(p) + 1 will be the overall number of phone calls we have to keep.
The greedy algorithm can be easily derived from the recurrence relation above by noticing that keep(i) is decreasing.

Judges' test data consists of 100 random-generated test cases.

Rating: Hard

Problem F: Flavius Josephus Reloaded

This problem can be solved by applying one idea of the Pollard Rho algorithm: Advance one pointer in steps of two, another pointer in steps of one. When they point to the same soldier, we know that this is one of the soldiers who will commit suicide. Every soldier whose number is calculated after that will commit suicide as well.
Another possibility is to store the numbers of the soldiers in a set and when we calculate a number which is already in the set, we have found the first soldier to commit suicide.

Judges' test data consists of 33 test cases.

Rating: Medium

Problem G: Wine trading in Gergovia

This problem is based on the so called "Earth movers distance", which is used to calculate a measure of similarity between two histograms. In the one dimensional case, the following greedy algorithm gives optimal results:
Go through the values from left to right, and try to reduce them to 0 by using greedily the closest values. To get the required linear time complexity, notice that only values to the right can be used to reduce the current value to 0 (since all values to the left are already 0). Therefore, we can add the current value to the next value and add the absolute value to the number of work units needed.

Judges' test data consists of 25 test cases, most of them are random-generated.

Rating: Easy

Problem H: Homogeneous squares

One solution to this problem uses the observation that subtracting 1 from each value in a row or each value in a column does not change the homogeneous property. Therefore we can reduce the first row and first column to zero. If there is any cell left with a non-zero entry, e.g., the cell in row i and column j, then the square will be not homogeneous, because a set of n independent positions containing cell (0,0) and cell (i,j) will have another sum than the slightly modified set which has cells (0,j) and (i,0) instead. But if all cells contain the value 0, the square is obviously homogeneous.
Another possibility for solving this problem is to generate random sets of n independent positions, and check if they all have the same sum. If we assume that the worst case has n! - (n-1)! sets of independent positions with the same sum (like in the case that only one cell is wrong), we can see that if we check about 5000 random sets of n independent positions, the probability that we will not identify a non-homogeneous square will be smaller than 1 percent.

Judges' test data consists of 40 test cases; most of them are random-generated.

Rating: Medium