## Sunday, August 22, 2010

### IOI: Another Hard Problem

You are given a matrix A[1..N][1..M] that contains a permutation of the numbers {1, ..., NM}. You are also given W≤N and H≤M. The goal is to find that rectangle A[i ... i+W][j ... j+H] which has the lowest possible median.

Running time: O(NM).

***

This could have been another hard problem at the IOI, but it was decided to give maximum score to solutions running in O(NM lg(NM)). This is considerably easier to obtain (but still interesting).

In the style of what Terry Tao tried for the IMO, I am opening this blog post as a discussion thread to try to solve the problem collectively ("poly-CS" ?). You are encouraged to post any suggestions, half-baked ideas, trivial observations, etc – with the goal to jointly reach a solution. If you think about the problem individually and find the solution, please don't post, as it will ruin the fun of the collective effort. Following this rule, I will not engage in the discussion myself.

I did not encourage a discussion for the first problem, since it was the kind of problem that only required one critical observation to solve. This second problem requires several ideas, and in fact I can see two very different solutions.

ilyaraz said...

Let's do binary search on the answer. Suppose we want to check if the answer is less than x. To this aim we calculate in O(nm) time for every subrectangle number of entries that are smaller than x.

It is O(nm log nm) time, though.

ilyaraz said...

One interesting special case is 1-d.

ilyaraz said...

Another algorithm for 1-d that achieves O(n log n) time (whp, though).

x := n + 1;
l := list of all subsegments of length w;
while (1) {
if there is no element in l whose median is lower than x -- break; (we perferom this check in O(n) time)
pick element from l at random;
x := its median;
}

ilyaraz said...
This comment has been removed by the author.
Cosmin said...

Another interesting special case is when W = N. I can do that in O(NM).

ilyaraz said...

Care to elaborate?

Anonymous said...

Note that when W=N, this is a generalization of 1d. How do you get O(n) in 1d?

ilyaraz said...

I do _not_ know yet. :)

Non-randomized O(N) solution for 1-d case (uses the fact that the numbers are small):

1. Sort the values in decreasing order (using countsort).

2. In decreasing order, mark each value as "out". Stop when there is no segment of length W with at least W/2 values not yet marked "out" (i.e. all segments have at least half of the elements marked out). The last value marked "out" before we stopped is the median.

How to achieve this in O(N): simply keep track of the leftmost segment of width W with at least W/2 values not yet marked out (and keep track of the # of values not marked out). Whenever we mark out a value, we just check if it is in this segment or not. When the # of unmarked values in the segment falls under W/2, we advance the segment to the right one step at a time, until we find the next suitable segment (if we don't, we're done, and the last segment we kept track of is the one we're looking for). Advancing one step is trivial in O(1), and we only advance at most O(N) times throughout.

I think this can be easily adapted for Cosmin's special case as well (we just maintain per-line counts).

Anonymous said...

@Radu, @Mihai: ca we assume the numbers are small? this makes the problem much easier.

Mihai said...

The blog entry says that the numbers are a permutation from 1 to MN.

Mihai said...

Radu, nice solution. I had two ways of doing O(n) in 1-d, but yours is different (and I think simpler than mine).

One feature of these discussions is that you can have fun going into side topics. (I understand that poly-math projects go into several subtopics regularly.)

So: Let's assume the numbers are large, i.e. you don't know how to sort them in linear time. Solve the 1-d problem in O(n) time.

ilyaraz proposed a randomized algorithm earlier. Randomization is kosher for this discussion.

But note that I can solve the problem deterministically in linear time, even when the numbers are large. So, you can try to come up with any solution (the simplest may be randomized), and later ask for a deterministic one if the first you discovered happened to be randomized.

I realized that my solution above works in 2d too, just keep counts for the current line (no of unmarked values in the H cells above), and updare in O(M) when we need to go to the next line. Does this make sense?

To be more clear.

Start on line i = H.

Maintain A[j] = # of unmarked values in cells (i-H+1,j) to (i,j).

When marking off a value (x, y), if it i-H+1 <= x <= i, decrement A[y]; if it is also in the current square, decrement the value for the current HxW rectangle.

We advance left to right as in the 1-d case. When we reach the right end and we have to move to the next line (i <- i+1), we just update A[j] <- A[j] - is_unmarked(i-H,j) + is_unmarked(i,j); this is O(M). Then we have read the first H values of A to get the value for the left-most rectangle, and then we can continue moving to the right when necessary.

Can't think of a way to avoid the sorting step right now, but an observation is that what we really need is not necessarily the entire sorted array, but a way to find all yet-unmarked values bigger than the current median.

Mihai said...

Very nice. That certainly solves the problem as I stated it originally.

ilyaraz said...

Deterministic solution for 1-d with running time O(n + k log n), where k is an index of minimum median in a sorted array (we do not assume that numbers are small).

Let us do binary search on the answer. But now we will do each iteration slightly more efficient.
Suppose we want to check if answer is less than x. We will keep track of a list of numbers that are smaller than x. And we can perform the check in time proportional to the length of this list (sweeping two pointers). That gives us O(n + k log n).

ilyaraz said...

Ok, it is actually O(n + k log U), where U is the biggest number in our array.

Thanks!

Unfortunately, I realize now that ideas like this can't be made to work for large numbers.. this algorithm tries to do too much in that not only it finds the best segment, but it finds the sequence of segments with decreasing ("best so far") median as you go from left to right (as well as all their medians as well).

Such an algorithm can be used to sort a set S of K numbers, with an input of size 3K+1:
K+1 very large numbers, the set S of K numbers, and K very small numbers.

With W=2K+1, for position 2K+i, the
best segment so far is [i+1, 2K+i] and its median is the ith largest element in S.

Anonymous said...

By binary search idea + Radu idea, you obtain O(nm lglg n). First you do binary search O(lglg n) rounds and you find out that the answer is in some range of nm/lg n values. Then you sort those in linear time and you apply Radu idea.

Binary search is possible because it requires finding median that takes linear time.