Solution for “photo” (Day 1)

The key observation is that any two rectangles in an optimal solution are either disjoint or nested (one of them is taller, and has the base included in the other). If two rectangles were to intersect in any other way, the shorter one can be shrunk horizontally until it is disjoint from the other.

We can decompose an optimal solution by recursively splitting the initial set as follows:

§ If the covering rectangles in the optimal solution can be split in two sets using a vertical line that does not intersect any of the rectangles, split the set of points according to this line. We have N possibilities to try for such a horizontal partition. § If the rectangles cannot be split as above, then there is a rectangle whose base covers all the others'. This rectangle must cover the projection of all points on the x-axis, so it will stretch between the minimum and maximum x coordinate of the points in the set. Without loss of generality, this rectangle can be as tall as possible, given the constraint on the base.

Considering these two cases, we can see that each relevant subset of the initial set is delimited by three lines: it lies between two vertical lines, and above a horizontal line. Let C(i,j,k) be the minimum number of rectangles needed to cover the points C(x,y) with the following properties:

We can now solve the problem using dynamic programming:
C(i,j,k) = min { min x=i..j-1 (C(i, x, k) + C(x+1, j, k)), 1 + C(newi, newj, newk) }
... where newi, newj, newk are the points on the left, right, and down border the subset of points not covered by the base rectangle.

There are O(N^3) states and for each, we perform O(N) operations. Thus, the time complexity is O(N^4). Solutions based on backtracking earn between 20 and 40 points, depending on the optimizations used in the backtracking.
[홈으로]  [뒤 로]