Judges' Comments on the Problems and their Solutions

Problem A: Another lottery

The important observation to solve this problem is: only the winner of the last round m matters, since ∑_i=1..m-1 2ⁱ = 2^m - 1, so even if someone wins all previous rounds, he will have won less money than the winner of the last round. The probability for a participant to win the last round is the number of his tickets of round m divided by the total number of tickets sold for round m.

To compute the reduced fraction, we can use the Euclidean algorithm to determine the greatest common divisor.

Judges' test data consists of 20 test cases.

Rating: Easy

Problem B: Ballot evaluation

The solution to this problem is straightforward: parse the input, compute the sum of the percentage values corresponding to the party names and compare them with the given integer using the specified operator. The parsing is simplified by the input format: all tokens are separated by whitespace, the party names have "+" tokens between them and a line is terminated by the operator token followed by an integer. So while the token after the current party name is a "+" token, continue reading party names. Otherwise it must be the operator token followed by the integer.

There remains one problem: since some decimal floating point numbers cannot be represented exactly as a binary floating point number, a direct calculation can lead to rounding errors and to a wrong result of a comparison. We therefore need to either convert all numbers to integers by multiplying by 10, or use comparisons which assume a small error epsilon. A comparison a < b for example can be written as a < b - epsilon, a ≤ b as a ≤ b + epsilon, and a = b becomes |a-b| < epsilon. A value of 10^-9 for example is appropriate.

Judges' test data consists of 10000 test cases, based on the results of the European parliament elections in Germany.

Reference:

Election results

Rating: Easy

Problem C: Cyclic antimonotonic permutations

One possible way to solve this problem is to generate solutions for small test cases and look for patterns. But there is also a constructive solution which we describe in the following.

We generate permutations which fulfill the antimonotonic property by placing the numbers > n/2 at odd positions, and numbers ≤ n/2 at even positions. We show by induction that there always exists such a permutation which is also cyclic. We use n = 1 as the induction base case. Obviously, the permutation 1 is cyclic and has the number 1 (which is > n/2) at an odd position. Now let n > 1, and suppose that there exists such a cyclic antimonotonic permutation of size n-1. We distinguish two cases:

1. n is odd: take the antimonotonic cyclic permutation of size n-1. The value (n+1)/2 is by construction at an odd position. We replace it with n and place (n+1)/2 at position n instead. Now, the permutation still has all numbers > n/2 at odd positions, and all other numbers at even positions, and the cycle now contains also the value n.
2. n is even: take the antimonotonic cyclic permutation of size n-1. Replace the value n/2 by n and place n/2 at position n instead. Note that n/2 is moved from an odd position to an even position, which is also required for the permutation of size n. Again, the cycle now contains also the value n.

In both cases, we have constructed a cyclic antimonotonic permutation of size n from the cyclic antimonotonic permutation of size n-1 (which exists according to the induction hypothesis) which proves the inductive step. Therefore it is possible to construct a cyclic antimonotonic permutation for all values of n ≥ 1.

The construction method described in the proof can be implemented as a dynamic programming solution to this problem. Just keep another array which stores the position of each number in the permutation in order to reach linear time complexity.

Judges' test data consists of 80 test cases, which cover all values n ≤ 50 and a few big test cases.

Rating: Medium-Hard

Problem D: Dark roads

The condition that there should be at least one illuminated path from every junction to every other junction simply means that we want to keep the streets corresponding to a minimum spanning tree. The problem can then be solved either with the Kruskal algorithm or the Prim algorithm.

Judges' test data consists of 7 test cases.

Reference

Kruskal Algorithm
Prim Algorithm

Rating: Easy - Medium

Problem E: Elias gamma coding

This problem can be solved with dynamic programming. We calculate the minimal encoding length when using k different prefixes, and then determine the optimum choice for k. Analyzing the two optimization steps gives us the following property: Consider two numbers, one with a bits, the other with b bits. Without loss of generality, assume a ≤b. After applying any combination of optimization steps, the prefix used for the number with a bits is never longer than the prefix used for the number with b bits.

This means that in order to get the minimum encoding length using k different prefixes, we need to partition the given numbers c_i into k different intervals. Each interval consists of numbers which are encoded using the same prefix, for example all integers with 5 to 7 bits are encoded using the prefix 01. More generally, consider the interval of all numbers with between a and b bits. Let the prefix assigned to this interval have length l. All numbers whose binary representation consists of between a and b bits are possibly padded with leading zeros, such that each number has exactly b bits. Therefore, the costs to encode all these numbers is (l + b) ⋅ ∑_i=a..bc_i.

To find the optimal partition into intervals, we can use the following recurrence relation. Let i denote the maximum number of bits to be considered and let j denote the number of prefixes to be used (j ≤ i).

C(0, 0) = 0
C(i, j) = min_k=j..i(C(k-1, j-1) + (i + j) * ∑_m=k..ic_m)

The minimum encoding length can then be determined as min_i=1..k C(n, i). This recurrence relation can be calculated using a 2-dimensional array. Each entry i, j of the array can be calculated in linear time by starting with k = i and going down to k = j, each time updating the sum of the values c_m. Therefore, the overall complexity of the solution is O(n³).

Judges' test data consists of 100 test cases.

Rating: Medium - Hard

Problem F: Food portion sizes

We need the following observation to solve this problem: for at least one person, the food portion size x must be chosen in such a way that there is no excess food, i. e. y_i / x is an integer.
Proof: Assume there is an optimal solution without this property. We derive a contradiction by showing how to improve this solution. For each person, determine how often he goes to fetch food, and determine the average remainder of food per time. If we take the minimum such average, decreasing the food portion size by this amount does not change the number of times the persons go to fetch food. However, the excess food is decreased, therefore the overall costs are decreased, which is a contradiction to the assumption that the solution was optimal.

We can check with brute force all food portion sizes y_i / k (1 ≤ k ≤ 3) and thus determine the minimum costs. The complexity of this solution is O(n²).

Judges' test data consists of 100 test cases, most of them are generated randomly.

Rating: Medium

Problem G: Generate random numbers

This problem can be solved by a simple simulation. The simplest way to calculate a_i is by calculating (a_i-1² div 100) mod 10000. We can use a boolean array to store for each number if it has already been generated. If the next value has been generated before, we can stop, because we have reached a cycle. The only tricky detail is that the given first number a₀ should be counted, too, when calculating the number of generated random numbers.

Judges' test data consists of the numbers from 1 to 9999.

Rating: Easy

Problem H: Hotel Booking

The key idea is to realize, that we do not care about the exact path on each day, just where the path ends each day. Each day is finished in a hotel or in the destination city. In the first step, we calculate for the start city and for each hotel which other hotels are reachable within 10 hours, and if the destination city is reachable. This can be done with the Dijkstra algorithm.

With the information calculated in this step we can build a graph which contains direct edges for each possible day trip. In the second step, we just need to find a shortest path in this unweighted graph, which can be done with a breadth-first search.

Judges' test data consists of 45 test cases.

Reference

Problem D Ulm Local Contest 1999
Dijkstra Algorithm
Breadth-first search

Rating: Medium