A -17 week

Codeforces hosted Mail.Ru Cup 2018 Round 2 during the Nov 5 - Nov 11 week (problems, results, top 5 on the left, analysis, my screencast). aid has claimed the victory thanks to solving problem G (that was already a very tricky geometry problem, and then let me quote the official analysis: "One thing you need to note here is that at given constraints you can't do those computations in floating point numbers, because the relative difference between r₁+r₂ and the distance from a vector to a polygon may be as low as 10⁻¹⁷. Therefore, you need to do all calculations in integers."). Moreover, his submission for G came with just 35 seconds remaining in the round. Congratulations on the persistence and the win!

One day later the Open Cup returned with the Grand Prix of Poland (results, top 5 on the left). 4 hours were enough for 13 problems for team Past Glory, while teams MIT THREE and Moscow SU: Red Santa required a bit more time but still solved everything. Congratulations to the top three!

In my previous summary, I have mentioned a Hacker Cup problem: there are w<=80 windows and s<=50 stars, both cells on a grid which represents a skyline. One must draw several buildings, each represented by a rectangle on the grid with line y=0 as the bottom side. Several buildings may intersect. Each window must be inside at least one building, and each star must not be inside any building. We need to find the minimum number of buildings required to satisfy those constraints. Such a problem would be too easy, so there's an extra twist: suppose we remove a random subset of windows (each window is removed independently with probability 0.5), what is the expected value of the minimum number of buildings required to cover all remaining windows without covering the stars?

First, suppose no windows are removed. It turns out that we can solve the problem greedily: let's go from top to bottom until we encounter a window that is not yet covered by any building. It's clear that we need to have some building covering this window, and since there are no uncovered windows above this one, the height of this building should be exactly equal to the height of this window. Then there's no reason not to extend this building as much as possible to the left and to the right, until we reach the boundary of the grid or the columns where there is a star at the same level or below this window. After that we exclude all windows covered by the newly added building and continue going from top to bottom.

Now we need to understand how we can run 2^w instances of this greedy at the same time, one per possible subset of windows that are removed. The usual way to run so many greedys in parallel is dynamic programming: we need share large parts of the greedy execution between different problem instances. But what can we share?

Consider the bottom-most star. While the greedy operates at its level or above, the computations to the left and to the right of it are completely independent, and when the greedy passes its level, there are no more relevant stars, and thus the only thing that matters is whether there's any yet uncovered window below that bottom-most star level: if there is at least one, we'll need to add exactly one building, otherwise we're already done.

So far, this seems like a promising way to organize the dynamic programming as we have split the problem into two almost independent sub-problems. We can repeat the same step again for each of the sub-problems by finding the bottom-most star in each. This way our sub-problem can be viewed as a segment together with a level, such that all stars within the segment are above that level, and we have only O(s) such sub-problems as we get two new sub-problems per one star.

However, there's a catch: for windows that are below the level, we need to know if they have been covered from above or not, in order to determine whether we need to add one to the answer on subsequent steps. The first idea of keeping a set of windows which are not yet covered results in exponential state space.

Here comes the key idea that puts everything together: consider one of our sub-problems, a segment together with a threshold level such that there are no stars below that level. Suppose we have already decided which windows there are removed and which are not, including the windows there that are below the threshold level, and ran the greedy until the threshold level. Then it turns out that instead of remembering the subset of windows below the threshold level which are not removed and not covered, it is enough to remember the top-most such window (and left-most of those if there are several top-most ones), because any building that will cover the top-most window and have height below the threshold level will also cover all those windows!

This means our dynamic programming has just O(w*s) states, and thus easily runs in time almost no matter how we implement the transition.

I have also mentioned a Codeforces problem: you are given a tree with nodes numbered from 1 to n (n<=1000) and a subset of nodes in it which forms a connected subtree, given as a list of numbers of the nodes. There's also a second, hidden numbering of all nodes with distinct numbers from 1 to n, and a second subset of nodes which also forms a connected subtree, which is given to you as a list of hidden numbers of its nodes. However, you don't know how the hidden numbers of the nodes correspond to the visible ones. You can ask an oracle questions of two types:

• What is the hidden number of the node with [visible] number x?
• What is the visible number of the node with hidden number y?

Your goal is to find any vertex that belongs to both given subsets, or report that there isn't any. You can ask at most 5 questions.

The solution here is beautifully simple. Let's take any hidden number that belongs to the second subset, and ask about its visible number, this way we find one node belonging to the second subset in our tree. Now let's find the node in the first subset that is closest to the known node of the second subset (since we're in a tree and the subset is connected, there will be exactly one closest node). It turns out that in case there is intersection between the two subsets, this node will belong to the intersection (again because the subsets are connected)!

All that remains is to ask the oracle about the hidden number of this node, and to check if it belongs to the second subset. We end up requiring just two questions to the oracle no matter how big the tree is.

Thanks for reading, and check back for more!