March 2011 Contest Problem Editorials

Our Tester for the month was David Stolp

BUYLAND (Written by Tomaz Hocevar)

The straightforward approach to solving this problem would be to compute the score for every position (r,c). Unfortunately, a quick estimate shows that it won't be fast enough. The problem looks similar to some kind of image filtering. If you're familiar with that field or with the use of filters in digital signal processing, you could sense that it will have something to do with Fast Fourier Transform. Let's begin by breaking down the score function which we're trying to evaluate at every (r,c).

p(r,c) is the function which we are evaluating and (hr,hc) is the offset of the restaurant in chef's layout. f(r,c) represents the height of the parcel and g(i,j) represents the relative height in preferred layout.

First three terms are not problematic. We can precompute a table of cumulative sums and later compute the fourth and fifth term in O(1) as well. The hard part is taking care of the last/sixth term. It is in fact a cross-correlation, which can be formulated as convolution. So the problem reduces to efficiently precomputing a convolution of country layout and preferred layout. That's where you need FFT to do it in O(n*log(n)), n=R*C. Once we have that, we can evaluate p(r,c) in constant time, find best solutions and output them.

However, FFT is hiding two problems. One of them are rounding errors related to floating-point computations. You needn't worry about it, because the values in this problem are very small. The other problem is a relatively big constant, which is hiding in front of the n*log(n) time complexity. Implementing an efficient convolution using FFT is a challenge, so here are some ideas:

· if you are coding in C++, stay away from STL for this purpose. Header "complex" might be tempting, but it's slow. 

· recursive implementations tend to outperform iterative ones on personal computers because they make better use of CPU's cache

· computing 2D FFT (first by rows and then by columns) proved to be faster for the same reason

· FFT of a real-valued sequence can be computed twice as fast as that of a complex-valued sequence. A slightly easier version computes FFT of two real sequences by merging them into a complex sequence and later reconstructing the results.

· Use some more advanced algorithm such as mixed-radix instead of the usual Cooley-Tukey radix-2 algorithm

· Number Theoretic Transform can also be very efficient with a good choice of primitive n-th root of unity to speed up modulo operations

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

KUNIQUE (Written by Ashar Fuadi)

If there is a number that occurs more than N/K times, then there is no solution, because otherwise there will be a subsequence that contains more than one occurence of the number, by pigeonhole principle.

If all numbers occur at most N/K times, then there is always a solution. Because we want the lexicographically smallest solution, it is easy to see that the following greedy algorithm works.

Repeat N/K times:

· M := number of remaining elements of the sequence

· While there is an element x that occurs exactly M/K times:

o Remove x from the sequence

· While the number of removed elements < K

o Remove the smallest element of the sequence

· Print the removed elements in this iteration in increasing order

To make the algorithm run within the time limit, we should use a balanced tree to store the number of occurrences of each number and to store the elements that occur M/K times. C++'s maps and sets are sufficient to store those information.

The idea is rather easy to come up with but the efficient implementation is somewhat harder that expected, so the number of TLE and WA solutions were large (as expected, too).

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

OMAX (Written by AnhDQ)

This problem can be solved by combining brute-force and dynamic programming (DP):

- At first, we find all non-empty sub-matrices, for each we call its two opposite vertices (x1, y1) and (x2, y2) respectively. Then your task is finding the maximal sum of the respective O-region. To do it, we must find the non-empty sub-matrix in range (x1 + 1, y1 + 1)..(x2 - 1, y2 - 1) which has the minimal value to remove. This minimal sum can be found by DP this way:

- We define F(i, j, k, t) as the minimal sum of a sub-matrix appearing in range (i, j)..(k, t), it should be calculated by Min{F(i + 1, j, k, t), F(i, j + 1, k, t), F(i, j, k - 1, t), F(i, j, k, t - 1), S} where S is sum of the sub-matrix having two opposite vertices respectively (i, j) and (k, t).

* This solution has the complexity of O((m x n)^2).

You can view the solutions here:

Problem Testers Solution

SKIRES (Written by Tomaz Hocevar)

Problems which ask to block all possible paths usually have something to do with cuts in a graph. This problem is no exception, we just need to set up the right model. Lets begin with some observations:

1. Raising cell A possibly results in new outgoing edges from A and blocks some incoming edges.

2. If in an optimal solution cell A is raised, then there is no valid path from the restaurant to A.

If such path existed, we might as well leave A at its initial height - possibly reducing the number of outgoing and increasing the number of incoming edges. Reducing the number of outgoing edges can only improve the solution and if we already have an incoming path, adding some new incoming edges won't change anything. Note that no path from A to town exists or the solution wouldn't be valid.

3. The height of every raised cell in an optimal solution will be equal to 1 + initial height of one of its neighbours.

It is obvious that the final height of any raised cell will be 1 + final height of one of its neighbours. But why can we make that claim with initial instead of final heights? Lets say we have two neighbouring raised cells A and B with h(B)=h(A)+1, where h(X) denotes final height of cell X. There is no need to raise cell B over A if there is no path from restaurant R to cell A, which follows from observation2.

We can model each cell with a linked list of 5 nodes. Last in the list is the outgoing node and the other four represent incoming nodes from neighbouring cells sorted by their height. Numbers next to nodes represent initial elevations of cells. Cutting an edge with cost x corresponds to raising the cell by x. All that's left is finding minium cut in this graph, which is equal to maximum flow by max-flow min-cut theorem.

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

SQUAGAME (Written by Ivan Mistreanu)

As usual this kind of games can be solved using Sprague-Grundy theory. However first we will have to find out how to calculate Sprague-Grundy values for the states of the game. In order to do this let's describe the game more formally. As the squares don't intersect for each square A we can determine the smallest enclosing square. We will consider the smallest enclosing square to be the parent of the square A.  For some squares there will be no enclosing square. So they will have no parent. That way we build a forest of rooted trees with nodes being the squares and roots being the trees with no parents. Now the turn of the game will be choosing any node of any tree and removing the subtree with the root in this node.

Let's divide the whole solution into 3 parts:

1. Build the forest effectively.

2. Calculate  Sprague-Grundy value of the game.

3. If the first player can win determine the winning move.

The first part can be done using sweep line algorithm. We will sweep over one of the axes. We will maintain the sorted list of tops and bottoms of all the squares that are currently intersected by the sweep line. When we come upon the left side of a square A we add its top and bottom to the list. Also in this case we should look at the previous element in the list for the bottom of our square. If this element is the bottom of a square B then the square B is the parent of the square A. If this element is the top of a square C then the parent of the square C is the parent of the square A. When we come upon the right side of the square A we remove its top and bottom from the list. Given that the add to list and remove from list operations are implemented with O(logn) complexity this part is O(nlogn).

When we have the forest built we can do the second part. Our game is actually Green Hackenbush on Trees. For this game it is known that each tree is equivalent of Nim-stack and the Sprague-Grundy value of the game is the Nim-sum of values of each tree. Now how to calculate the value of a tree. Let R be the root of a tree then the Sprague-Grundy value of the tree is 1 plus Nim-sum of the values of all its subtrees. The proof of this is left as an exercise. Knowing this we can derive an O(n) recursive algorithm to find the Sprague-Grundy of the game.

Now if the second player wins the game (i.e. the Sprague-Grundy value is 0) we just state this. If the first player can win (i.e. the value is not 0) we have to find a winning move. We can find all the winning moves in O(n) time using the method alike to determining the winning move for Nim. The method can be described as follows. Let the value of the game be S. In order to win we have to make a move to P-position (with 0 value). Let the value of some tree be T. We try to make a move in this tree so that its values becomes Q=S?T. If it were Nim-stacks we would just removed the needed amount of stones, but with trees it's a little more complex. We will make a query to the tree if we can make its value equal to Q: makeTreeValue(tree, Q). The answer to the query will be the numbers of the nodes we need to remove to make the value of the tree equal to Q or -1 if it can't be done . If Q is 0 that the answer is the root of the tree. Otherwise we need to make the Nim-sum of the subtrees equal to Q-1. Let the current Nim-sum of the subtrees be R. Then we ask all the subtrees the same query: makeTreeValue(subtree, (Q-1)?R) - and gather the answers. And we do this for all the trees in the forest. Also according to the problem statement we need to pick the winning move with the smallest number.

The overall complexity is O(nlogn).

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

ALLINONE (Written by Zac Friggstad)

The problem is more commonly known as the "Traveling Repairman Problem" (TRP) or the "Minimum Latency Problem". It is, of course, NP-hard. The best approximation algorithm finds a solution in polynomial time that is guaranteed to have the average waiting time no more than 3.59 times the optimal [1]. The heart of the algorithm lies in approximating the minimum cost of a rooted k-trees which are minimum cost trees containing a given node and any k-1 other nodes.

At first, the problem might seem very similar to the more popular Traveling Salesman Path Problem (TSPP) where the goal is to visit all locations as fast as possible without the requirement that we must end where we started. However, there are simple instances where the optimum TSPP solutions looks quite different than the optimum TRP problem. Consider the following graph which is viewed as points on the real line. We start at location 0 and each location 0 < i < n is at point (-2)^i. The optimum TSP solution visits all nodes < 0 then all nodes > 0 (or vice-versa depending on whether n is odd or even) whereas the optimum TRP solution zig-zags back and forth across 0.

1) K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar, "Paths, trees, and minimum latency tours", in Proceedings of Foundations of Computer Science, pp 36-45, 2003.

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution