More on Problem 2

You might be wondering what caused the hiatus in posting CEOI problems. My modus operandi as a researcher is to induldge in whatever obsession I currently have. For the past week, the raging obsession has been Problem 2 (tempered, of course, by the beaurocracy of joining AT&T).

Several people found the O(n⁴) solution, both during the real competition and on the blog. In addition, Berman, Karpinski, and Lingas also found this solution in a recent arXiv paper. (Thanks to Nate Xiaoming Xu for telling me about this paper!) Their paper is not about rectangle covers, but something about wireless antennas. This goes to show that olympiad problems are often deep enough to become research papers. The only additional skill that we have in research is keeping a straight face when we write the introductions. (Don't worry, it comes with age.)

As I announced in the comments to the previous blog post, I found an O(n³) solution. This appears to be tricky (several people tried to reconstruct my solution in the comments, but without success). My solution is described in this post.

I am still quite optimistic that O(n²) might be possible, but so far I haven't been able to beat cubic time. If you find a way, I will be impressed.

If you don't find a way but want to discuss promissing ideas, use the comments to this post. Think of this as an experimental poly-CS project. The discussion is open to anyone. Don't be shy to post, but please be use a nickname for identification ("CarpathianBlackMetal" is much more informative than "Anonymous"). Also number your comments (e.g. "This is comment #4 from CarpathianBlackMetal"). Do not delete a comment if you posted something wrong. Explaining why it is wrong is much more informative for the audience.

Now let me describe the solutions I know for this problem.

Observation 1. In an optimal solution, any two rectangles are either disjoint or "nested" (one of them is taller and has the base included in the other). If two rectangles were to intersect properly, the shorter one can be shrunk horizontally until the rectangles become disjoint.

Let the points have coordinates (x[i], y[i]). Assume they are sorted by x.

Observation 2. We can construct an optimal solution in which every rectangle satisfies:

1. it extends horizontally from some x[i] to some x[j];
   
2. it extends vertically up to A / (x[i] - x[j]), i.e. as high as possible.
   
3. it covers points i and j, i.e. y[i], y[j] ≤ A / (x[i] - x[j]).

Perhaps the only nonobvious condition is 3. But note that if the rectangle doesn't cover point i, I might as well move its edge inside (beyond point i), and thus increase the height. The only change that could happen would be to cover more points.

An O(n⁴) solution. We thus know that there are only O(n²) distinct rectangles to consider. Denote them by R(i,j); though not all pairs (i,j) are valid rectangles.

If R(i,j) is used in the solution, we have a well-contained subproblem to solve: cover all points between x[i] and x[j], which are not already covered by R(i,j), that is, they are above the rectangle. Let A(i,j) be the minimal number of rectangles needed to cover all such points. This is our dynamic program.

We fill the dynamic program by increasing values of j-i. To compute A(i,j), let S be the set of points k (i < k < j) which are not covered by the rectangle. Note that i and j are always covered (by condition 3. above). Thus, any information pertitent to covering S has already been computed by our dynamic program.

Let S={X1, X2, ... }. To compute A(i,j), we need to find splitters a < b < c < ... which minimize A(X1, Xa) + A(X{a+1}, Xb) + A(X{b+1}, Xc) + ...

This is a classic dynamic programming problem itself, or, if you wish, a shortest paths problem where A(x,y) is the length of the path from node x to node y. This subproblem can be solved in O(n²) time (which is "linear time", since there are n² subproblem A(x,y)). Thus, the original dynamic program is filled in O(n⁴).

An O(n³) solution. A common strategy for improving the running time is to try to maintain more information. Thus, I first reformulate the dynamic program above to use O(n³) state.

Let T(i,j,k) be the optimal number of rectangles to cover all points (x,y) with x[i] ≤ x ≤ x[j] and y ≥ heights[k], where heights contains all y's in sorted order. Unlike the previous solution, I consider all heights k, not just the maximal one for a fixed i and j.

This dynamic program is easy to fill in O(n⁴). For some triple (i,j,k), I will either:

• draw a rectangle from x[i] to x[j] of maximal height. If this height is more than y[k], I get the optimum for covering the remaining points from T(i,j,new height).
  
  
• if there is no rectangle spanning x[i] to x[j], there must be a break point m, such that T(i,j,k) = T(i,m,k) + T(m+1,j,k). Iterate to find the optimal such m.

To fill this in O(n³) requires a nice trick. The order of the computation will be: by increasing value of j-i, and, for some fixed (i,j), by increasing k.

To compute the optimal T(i,j,0), proceed exactly as above, taking time O(n). The rest of T(i,j,k) for k>0 can be computed in constant time per entry. For each T(i,j,k+1), I have two possibilities:

• T(i,j,k+1) = T(i,j,k).
  
  
• T(i,j,k+1) < T(i,j,k). Thus, the optimal solution for k+1 is different from the optimal solution for k. But the set of points that must be covered by these two solutions only differ by one point P (with y[P]=k). Thus, point P must not be covered by the solution for T(i,j,k+1) — if it were, the better solution for T(i,j,k+1) would also hold for T(i,j,k). Thus, x[P] is a break point in the solution T(i,j,k+1), and we have T(i,j,k+1) = T(i,P-1,k+1) + T(P+1,j,k+1).
  

Good luck thinking about this problem!