Judges' Comments on the Problems and their Solutions

Problem A: Alfredo's Pizza Restaurant

The probably easiest solution to this problem involves following insight: It is not bad if we align the center of the rectangle with the center of the circle. This means, we simply need to check that the length of the diagonals of the rectangle is not bigger than the diameter of the circle.

Let D be the length of the diagonals of the rectangle with width w and length l. According to the Pythagorean Theorem, we know that D * D = w * w + l * l. In this problem, it was enough to take the square root of the expression w*w + l*l to calculate D and compare it to the diameter of the circle (2 * r). However, if we want to be extra careful and avoid floating point errors, we can compare D*D with the squared diameter 4*r*r instead.

Judges' test data consists of 302 test cases; in 101 of the test cases, the rectangle fits exactly in the circle, in 93 test cases the rectangle fits in the circle without touching the border of the circle, and in the remaining 108 test cases the rectangle doesn't fit in the circle.

Rating: Easy

Problem B: Broken Keyboard

A naive solution to this problem would be: we try all positions in the string as starting position. For a fixed starting position, extend the substring until we are either at the end of the string, or the number of different characters exceeds the parameter m. With the given limit of up to one million characters for a given string, it is obvious, that this naive solution is too slow.

We can turn this solution into a linear solution by going through the text with two pointers, one pointer points to the current end position, one pointer points to the current starting position in the string. As before, we increase the end pointer until the number of different characters exceeds m, then we increase the start pointer until the number of different characters in the current substring goes back to m. This can be implemented efficiently by having a counter for each possible character, which stores for each character the number of occurrences in the current substring. In addition we have a meta-counter, which stores how many character counts are non-zero. This meta-counter is increased when a character counter is increased from 0 to 1, and the meta-counter is decreased when a character counter is decreased from 1 to 0.

Judges' test data consists of 211 test cases, 3 of them have the maximum size of one million characters.

Rating: Medium

Problem C: Convert Kilometers to Miles

The main idea that is needed to solve this problem is how to calculate the representation of a number n in the Fibonacci system. This can be done easily with a greedy algorithm: As long as the number n is not zero, find the biggest Fibonacci number ≤ n and subtract it from n, and set the corresponding bit in the Fibonacci system representation to 1.

We will show with induction that this greedy algorithm is correct. Obviously, for n = 1, there is only one representation in the Fibonacci system, and this representation is also found by the greedy algorithm. Now assume that the greedy algorithm is correct for all values < n (n > 1). To calculate the representation of n in the Fibonacci system, the greedy algorithm subtracts the biggest Fibonacci number ≤ n. If n is a Fibonacci number, the greedy algorithm finds a representation which consists of a one followed by only zeros, so it fulfills the requirement that there should be no two consecutive bits set to 0. If n is not a Fibonacci number, the greedy algorithm subtracts a Fibonacci number F_k < n, i.e. n - F_k > 0. According to the induction hypothesis, the greedy algorithm calculates the correct representation of the number n - F_k. It remains to show that adding the bit b_k=1 to the Fibonacci system representation of n - F_k yields a correct Fibonacci system representation of n. This is the case if the Fibonacci system representation of n - F_k does not contain any b_i = 1 with i ≥ k-1.

We prove this by showing a stricter claim: n - F_k < F_k-1. Assume for the sake of contradiction, that n - F_k ≥ F_k-1. Then it follows that F_k+1 = F_k-1 + F_k ≤ n, which is a contradiction because the greedy algorithm did subtract the biggest Fibonacci number F_k with F_k ≤ n.

With the given condition that no two consecutive bits in the Fibonacci system representation of a number should be 1 it is possible to show by induction, that the Fibonacci system representation is unique. This can be done in three steps:

1. ∑_i=1..k F_i*2-1 < F_k*2.
2. ∑_i=1..k F_i*2 < F_k*2+1.
3. ∑_i=1..2*k F_i < F_k*2+2.

Judges' test data consists of all numbers between 3 and 24999.

Rating: Easy

Zeckendorf representation

Problem D: Decode the Strings

First of all, we have to figure out how to decode the strings. Let p[1], ..., p[n] be the permutation used for encoding. If p[i] = j, it means a character from the input string was moved from position j to position i, therefore the permutation p'[1], ..., p'[n] for decoding needs to have p'[j] = i. This can be simplified to: p'[p[i]] = i, i.e. p' is the inverse permutation of p. Applying the encoding steps with the inverse permutation m times would give us the decoded string, however a naive implementation would be too slow.

Let us look at an individual character how it changes positions with each encoding step. If it is currently at a position p[i], it will be moved to position i, and it is only moved to position i if it was at position p[i] in the step before. This is true because the permutation p contains each integer between 1 and n exactly once. Since there are only n positions, the character will be moved back to its original position after at most n steps. Obviously, after it was moved back to its original place it will be moved through the same set of positions and in the same order in the next encoding steps. Therefore, we can determine for each character in the input string the number l of encoding steps needed such that it is back at its original place, and then determine the position where it is after m modulo l steps. A naive implementation of this idea would lead to an O(n^2) algorithm.

We can further optimize the algorithm by realizing that after we have determined for some character the set of positions it traverses cyclically, we do not need to determine these positions again for any other character in the cycle. This leads to an O(n) algorithm.

For someone familiar with the symmetric group on the set X = {1, ..., n} the following solution may be easier: Each permutation represents a bijective function from X to X (in our case, p(i) = p[i]). The group operation is function composition, which is associative. Let us define p¹(i) = p[i], and p^k(i) = p^k-1(p¹(i)). We need to calculate p^m(i). We distinguish two cases:

• If m is even, p^m(i) can be calculated as p^m/2(p^m/2(i)).
• If m is odd, p^m(i) can be calculated as p¹(p^⌊m/2⌋(p^⌊m/2⌋(i))).

Judges' test data consists of 63 test cases, most of the encoded strings are taken from the source code of a solution to this problem.

Rating: Medium

Encoding
Symmetric Group

Problem E: El Dorado

This problem can be solved with dynamic programming. We calculate the number of increasing subsequences of length j where the last number of the sequence is at position i. This can be calculated with the following recurrence relation: CIS(i, 1) = 1, CIS(i, j) = ∑_{1 ≤ i'<i:ai'<ai}CIS(i', j-1) if j > 1. The answer for this problem is then the sum of the values CIS(i, k). Since we need a table of size n ⋅ k, and calculating an entry takes time O(n), the complexity of the solution is O(n² ⋅ k).

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

Rating: Medium

Problem F: Forest

The basic idea how to solve this problem is not as difficult as the implementation. Each tree blocks the view to other trees in some interval of angles relative to the origin, so if we order the trees such that tree i only blocks the view to trees j with j > i, we can process the trees in this order and insert the interval of angles that the current tree blocks in a list of blocked intervals (possibly uniting intervals if they overlap). If the interval of angles for some tree is already contained in the list of blocked intervals, the tree is not visible from the origin. Otherwise, it is a candidate for the solution, and we update the maximum distance found so far.

The first tricky thing is: how do we determine the order of the trees with the property mentioned above? It turns out that sorting by the point closest to the origin is wrong (test case 5 in the judge input), and sorting by the center of the circle is wrong, too (test case 3). We can sort the trees by the distance from the origin to the points where the tangents touch the circle. There are two such points for each circle, both points have the same distance from the origin, and the distance can be calculated with the Pythagorean Theorem as the square root of x²+y²-r². Let us call this distance D(x, y, r). Since we only need to compare these distances, we do not need to calculate the square root, we can compare the squared distances instead.

Now we want to show that sorting by D(x, y, r) gives us an order of the trees with the desired property. Take any two trees i and j (i ≠ j). Without loss of generality, assume D(x_i, y_i, r_i) ≤ D(x_j, y_j, r_j)

Another tricky detail which has to be handled in an implementation is how to represent the cyclic nature of the intervals. This can be done by considering intervals from -π to π, and if there is an interval from a to b where -&pi ≤ b ≤ a ≤ π, we can split the interval in two parts: [a, π] and [-π, b].

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

Rating: Hard

Problem G: A Game with Marbles

This problem can be solved by an optimized simulation: One has to realize that the number of game steps is independent of the order in which the game steps are executed. Therefore, we can remove all a_n marbles from bowl n in a single step and add as many marbles to each bowl i with 1 ≤ i < n , then continue with bowl n-1 and so on. This algorithm can also be optimized by keeping the sum of marbles which have to be added to smaller bowls.

Another way how to solve this problem is by looking at the process of executing a game step as the decrement of a power of 2: one deletes the highest bit, and sets all smaller bits to 1. Therefore, the answer for this problem can be calculated as: ∑_i=1..na_i ⋅ 2^i-1

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

Rating: Easy

Problem H: Help Bob

Since each pizza can be bought at most once, we could solve the problem by enumerating all subsets of pizzas. However the order of buying the pizzas does matter, since coupons cannot be used retrospectively, and it is too slow to try all permutations of how to buy the pizzas.

The important observation is: given the subset of pizzas already bought, we do not care anymore about the order in which this subset of pizzas was bought. Therefore, we can use dynamic programming to solve this problem. We represent the subset of pizzas already bought by a bitmask with n bits, where bit i is set to 1 if and only if pizza i was already bought. The recurrence relation can be formulated as follows:
minimum_price(mask) = min_{mask = submask + 2ⁱ} minimum_price(submask) + price of pizza i
where the price of pizza i is determined using discount coupons given for the pizzas bought before pizza i represented by the bitmask submask.

When calculating the minimum price for a subset of pizzas we only need to refer to bitmasks with a lower numeric value, therefore the recurrence relation can be calculated bottom up by enumerating all bitmasks with n bits from 0 to 2ⁿ-1. We need a table of size 2ⁿ, and each entry of the table can be calculated in O(n²) time, therefore the overall runtime is O(2ⁿ ⋅ n²).

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

Rating: Medium - Hard