CEOI: Problem 2

The discussion on Problem 1 was quite active; I even posted a lower bound for the streaming complexity of the problem. The official solution is:

The basic idea is to sweep through each line i, and maintain the “height” of each column, i.e., the number of ones in that column extending upwards from line i. Given the heights of each column, one has to find a subset S of columns maximizing |S| • min(S). You can find this subset by trying values for min(S) and counting how many heights are greater or equal. By maintaining the heights in sorted order, this computation becomes linear time.

To make the algorithm run in O(N•M) time, the key observation is that, while the sweep line advances to another row, a height is either incremented or reset to zero. This means that one can maintain the sorted order in linear time: place the values that become zero up front, and maintain the order for the rest (which is unchanged by incrementing them).

Let us now move to a problem of average difficulty. Originally, I was worried that it would be too easy (the contestants really know dynamic programming), but it seems the details behind the dynamic program were unusual enough, and some people missed them.

Problem: Photo. You are given a skyline photograph taken during the night. Some rooms still have the light on. You know that all the buildings can be modeled by rectangles of surface area at most A. Find the minimum number of buildings that can lead to the picture.

In other words, you are given an integer A, and N points at integer coordinates (x,y). You must find a minimum number of rectangles with one side on the x-axis and area at most A, which cover all points. The rectangles may overlap.

Desired running time: polynomial in N.

CEOI: Problem 1

As I've announced before, I was the chair of the Scientific Committee at The 16^th Central European Olympiad in Informatics (CEOI'09). I will have a few non-technical post on the experience, but in the next 6 posts, I will simply let you enjoy the problems.

I would encourage all my theory friends to think about these problems. What you might gain:

1. You can form your own impression on the level of these contests (I think it is quite high, and it will allow us to recuit many researchers down the road. Consider that one has to solve and implement 3 problems in 5 hours.)
2. These are great algorithmic puzzles, of the kind that is hard to come by (as opposed to math puzzles, which are everywhere, but I find boring).
3. You may finally answer the question: Are you smarter than an 11^th grader? :)

Please feel free to use the comments section. The official solution to each problem will be posted together with the next problem.

To start lightly, today I will show you the easiest problem. (It is perhaps easy enough for an exam in Introduction to Algorithms... What do you think?)

Problem: LOGS. Given an N by M binary matrix, find the area of the biggest rectangle consisting entirely of values of 1, knowing that you can permute the columns of the matrix.

Desired running time: O(MN).

For example, if the matrix is:

001010

111110

011110

111110

011110

111111

110111

110111

000101

010101

The answer should be 21: by permuting the columns such that columns 2, 4, and 5 are adjacent, you have a rectangle of area 21 (rows 2-8 and columns 2, 4, 5).

PS: Yes, today's my birthday. Only 13 more years to win the Nevanlinna Prize :)