Judges' Comments on the Problems and their Solutions

Problem A: Annoying painting tool

The first thing to realise is that in an optimal solution, the painting operation is never applied more than once at the same position. Also, it doesn't matter in which order the operations are done, therefore we can do the painting operations from top to bottom, and from left to right.

Using these ideas we can check easily if a painting operation at some position is required or not. Since the pixel in the top left corner of a selected area for the painting operation will not be changed by later operations, we just check if it already has the required colour. If its colour still needs to be changed, we have to apply the painting operation.

After we have applied all the painting operations, we need to check the pixels in the rightmost m-c columns and bottom n-r rows if they have their required colour. If one of these pixels doesn't have its required colour, it is impossible to create the painting.

Since the size of the picture is at most 100 × 100, a naive implementation with O(n^4) runs in time. There exists an optimal solution which runs in O(n*m). The idea is to store how many operations have been applied with the top left corner in one of the first i rows and j columns. With this stored data it is possible to answer in constant time how many operations covering a pixel have been applied. An implementation of this approach can be found here.

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

Rating: Easy

Problem B: Black and white painting

If we ignore the colour constraint, there are n-7 possible rows and m-7 possible columns of the painting where the bottom right corner of the chess board can be placed. So there are a := (n-7)*(m-7) of these squares, but only about half of them are white. If a is even, exactly half of the squares are white. If a is odd, we have to round up or down to get the answer, depending on if the bottom right corner of the painting is white. Overall, we can see that the answer to this problem is just ((n-7)*(m-7)+c) div 2.

Judges' test data consists of all cases with 8 ≤ n,m ≤ 12, along with 150 random-generated test cases.

Rating: Easy

Problem C: Cylinder

Let r denote the radius of the circle. We have to distinguish two cases in this problem.

The first case is if we want to roll up the bottom part of the paper vertically, using w as the height of the cylinder. In this case, we want to maximize r under the constraint that the bottom part of the paper has a height of at least 2*r*PI; (the perimeter of the circle). Also, obviously 2*r ≤ w, otherwise the circle wouldn't fit on the sheet of paper.

The second case is if we want to roll up the bottom part of the paper horizontally. In this case, the height of the cylinder will be h-2*r, so we want to maximize r*r*PI*(h-2*r) subject to 0 ≤ r ≤ w / (2*PI). Derivating this function on r we see the maximum is reached for r = h/3. Since we know that h ≥ w, h/3 > w / (2*PI), which means the maximum in the allowed range for r occurs at w / (2*PI).

Now, to solve the problem, we just try both possibilities and take the maximum resulting volume.

Judges' test data consists of 5050 test cases with only integers for w and h.

Rating: Medium

Problem D: Deli Deli

This is the easiest problem of the problem set. All you have to do is to implement exactly what is written in the problem statement. Since the number of words is so low, there is no need to use an efficient implementation.

Judges' test data consists of 10 replacement rules and 42 words.

Rating: Easy

Problem E: Expressions

This problem can be restated as: given the post-order traversal of the syntax tree of an arithmetic expression, construct the reverse level-order traversal of the syntax tree.

The easiest way to realise that this is the required solution is to analyse the second example test case. Another way is to think about in which order we need the values to be stored in the queue. Each inner node of the syntax tree (representing an operator) requires its operands stored in the queue, first its right child, then its left child. Since we can't skip a value, these two values must be put into the queue one after another, which implies their children (if any) also have to be processed from right to left, with no other value in between. Applying this argument starting with the root of the syntax tree gives us the result.

An easy way to implement this is to build the syntax tree using the algorithm with the stack described in the problem statement. Then we do a level order traversal of the syntax tree, and in the end we reverse the resulting string. A java implementation is here

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

Rating: Medium

Problem F: Frequent values

This problem can be reduced to the range maximum query problem. For each distinct value in the input, store only how often it appears in the input. Then, each query corresponds to the maximum of these frequency values in some interval. However, we have to take care to adjust the query ranges accordingly. This can be done by storing for each position i in the input the index of the frequency corresponding to the value at position i. If this value also appears outside of the query range, we have to exclude it from the range maximum query and handle it as special case.

There are several ways to answer range maximum queries:

1. by checking all values in the range, which is too slow for the given limits
2. Using a binary tree data structure which has the frequency values as leaves and for each inner node stores the maximum of its two children. This data structure can be built in O(n) and queries can be answered in O(log n). An implementation can be found here
3. Precalculating the answers for range sizes which are a power of 2. This step needs O(n log n). Then, each query can be answered in constant time, using the fact that each query size can be covered by two (possibly overlapping) queries with ranges which are a power of 2.
4. Divide the frequency array into blocks of size sqrt(n). Precalculate the answer for each block (overall O(n)). Then, each query can be answered by a linear scan of the precalculated results of the blocks completely inside the query range, and also scanning the parts of the query range not covered by the blocks. This leads to a complexity of O(sqrt(n)) for each query.
5. Sorting the queries by left end point. Then, we go through the frequency values from back to front, maintaining a list of indices of the next improvement (bigger frequency value). To answer a query with the left end point corresponding to the current frequency value, we can do a binary search for the largest improvement index ≤ the right end point of the query range. Since the list of improvement indices is usually small, this runs quite fast, but in the worst case a query still needs O(log n). An implementation can be found here.
6. It is possible to answer range maximum queries optimally with queries in constant time and O(n) precalculation. More information can be found here.

It is also possible to process the given input values directly. Again, we have to do some preprocessing to be able to answer queries efficiently. One such possible solution (similar to approach number 2 above) builds a binary tree with following information for each node in the tree:

• The maximum frequency in the range covered by the node.
• The frequency of the first value in the range.
• The frequency of the last value in the range.

An implementation can be found here.

Judges' test data consists of four test cases, two of them with maximum n and q.

Rating: Hard

Problem G: Grocery store

This problem can either be solved by precomputing the answers with brute force, or by using an optimised brute force algorithm.

There are several ways to make it fast enough, the easiest way however is to solve the equation a*b*c*d = a+b+c+d for d, so that we only need to brute force the values a, b and c. Note that there may occur precision problems when we use floating point operations, so it is better to transform the problem so that only integer operations are needed. This can be done by multiplying each prize by 100, however to adjust the sum accordingly we have to multiply the sum by 10⁶. Solving this modified equation we get: d = (1000000*(a+b+c))/(a*b*c-1000000). However we still need to check that d is an integer which satisfies d ≥ c and a+b+c+d ≤ 2000.

Rating: Medium

Problem H: Halloween treats

This problem probably would have been easier given following hint: There always exists a solution with a selection of consecutive neighbours. The reason why this is true follows from the fact that c ≤ n, using the pigeonhole principle.

Let us define partial sums S_i as the sum of the first i values a_i, with S₀ = 0. Then, the sum of the values a_i from position i to j can be calculated as S_j - S_i-1. Now, the sum of the values a_i from position i to j is divisible by c if and only if S_i-1 = S_j (mod c). Since there are n+1 values S_i, but only c ≤ n different remainders modulo c, according to the pigeonhole principle there must be two partial sums with the same remainder modulo c.

A linear algorithm solving this problem can be derived as follows: For i = 1 to n, calculate the partial sum S_i as S_i-1+a_i. Store in a table of size c at position S_i mod c the index i. If there is already an index j stored there, then we know S_i and S_j are equal modulo c and we can construct the solution using the indices j+1 to i.

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

Rating: Hard