The 2010 International Olympiad of Informatics (IOI) finished today. Probably the highest high school level programming competition in the world, with participants from many countries. Anyways.

An interesting problem was Task 3 of Day 1, titled *Quality of Living*. In a grid of rows and columns, each cell is given an unique *quality rank, *as in 1 being the best, 2 being the second best, and being the worst.

Given and as odd numbers with and , the task is to choose a rectangle of height and width so that the median quality rank of the rectangle is at a minimum.

For example, given , , , :

The best, or smallest median of all possible rectangles in the configuration is the one shown, with a median of 9. Since no rectangle has a smaller median, 9 is the answer to this problem.

For an arbitrary array and parameters and , how should a program calculate the smallest median?

Let’s consider brute force. There are possible positions for the rectangle to be placed, and we will check each of them. Checking for the median requires sorting, which is of complexity .

In order to earn full points for this problem, the program needs to handle 3000 x 3000 grids in under 10 seconds. In the worst case that and , this amounts to over 2 million sorts, or many billion operations, which is clearly too much.

### A binary search approach

An efficient solution takes a completely different approach. There is no way to possibly calculate the median for every position.

Instead, we conduct a binary search on , the smallest median. Let us arbitrarily ‘guess’ a value of . For each element on the grid, we assign it -1 if it’s smaller than , 1 if it’s greater than , or 0 if it is equal to (and therefore *is*) .

In the example above, if we choose 12 for , we get:

Now for any sub-rectangle, we can determine if its median is smaller or larger than our guess by summing it up.

If its sum is negative, then its median is smaller than our guess; if it’s positive then the median is larger than our guess. If the sum is exactly 0, it means that the number of elements smaller is equal to the number of elements bigger, implying that the median of this sub-rectangle *is* our guess.

So if we look at all the sub-rectangles, we can determine if our guess is correct or not. Furthermore, if it’s not correct, we know whether it’s too large, or too small:

If there is **any** sub-rectangle having a negative sum, then our guess is too big. That particular sub-rectangle has a smaller median, so our median can’t be the smallest anymore.

On the other hand, if **all **sub-rectangles have a positive sum, then our guess is too small.

We know we’ve got it when none of the sub-rectangles are negative, and at least one sub-rectangle has a 0 sum.

It turns out that going through the sub-rectangles can be done very efficiently:

The plan is, we start from the top of the first column and go down it, and when we reach the end we start at the top of the next column, and so on. We keep doing this until we reach the end.

As we are dealing with columns at a time, let us keep the sums of the relevant columns in an array `wsum[]`

. For example, in the grid:

Now to find the sum of the first sub-rectangle, we add up -2 and 1 and 1, getting 0.

Then we can use this result to find the sum of the next sub-rectangle down. Removing -2 and adding 3, we get 5, which is the sum of it. Thus moving down a space can be done with only 2 additions.

We use a similar idea when moving right a column after having finished our current one. Rather than calculate `wsum[]`

over from scratch, we can take the old `wsum[]`

, and for each row, subtract the removed element and add the new element.

This combination of ideas allow us to implement this task very efficiently, well able to solve the 3000 x 3000 subtask within 10 seconds.

I have an implementation in Java:

import java.util.*; import java.io.*; public class Main{ static int R = 0; static int C = 0; static int W = 0; static int H = 0; static int[][] a = null; public static void main(String[] args) throws Throwable { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // Initialize constants String l1 = in.readLine(); StringTokenizer l1tok = new StringTokenizer(l1); R = Integer.parseInt(l1tok.nextToken()); C = Integer.parseInt(l1tok.nextToken()); H = Integer.parseInt(l1tok.nextToken()); W = Integer.parseInt(l1tok.nextToken()); // Parse data into array. Each cell has its own line. a = new int[R][C]; for(int i=0; i<R; i++) for(int j=0; j<C; j++) a[i][j] = Integer.parseInt(in.readLine()); // Seperate the calculations from the parsing run(); } // Try m as the new smallest median, and decide if m should be larger or // smaller. Return -1 if it should be smaller, 1 if it should be bigger. // If we have found the smallest median then we return 0. static int tryMedian(int m){ // Does a median m exist at all in this configuration? boolean exists = false; // Individual row sums of the column we're on int wsum[] = new int[R]; // Initiate wsum for the first column layer for(int i=0;i<R;i++) { for(int j=0;j<W;j++) { int temp=0; if(a[i][j]>m) temp=1; if(a[i][j]<m) temp=-1; if(j==0) wsum[i]=temp; else wsum[i]+=temp; } } // Outer loop: goes through the columns for(int i=0;i<=C-W;i++) { // Sum for the rectangle we're looking at int block=0; // First block in the column for(int j=0;j<H;j++) block+=wsum[j]; // Go through the rest of the rows for(int j=0;j<=R-H;j++) { // Found a negative block: m is too big! if(block<0) return -1; // The median exists, so this is it (unless we find a negative) if(block==0) exists=true; // As long as we're not at the very end, adjust the sum if(j!=R-H) block+=wsum[j+H]-wsum[j]; } // If not at the last column, adjust the wsum if(i!=C-W) for(int j=0;j<R;j++) { int temp=0; // Remove element at the head if(a[j][i]>m) temp=1; if(a[j][i]<m) temp=-1; wsum[j]-=temp; temp=0; // Add the new element at the end if(a[j][i+W]>m) temp=1; if(a[j][i+W]<m) temp=-1; wsum[j]+=temp; } } // No negatives; return based on if we've found m as a median or not if(exists) return 0; return 1; } static void run() { // Min and max for binary search int min = 1; int max = R*C; while(true) { // Perform new iteration on binary search int mid = (max+min)/2; int result = tryMedian(mid); // Found lowest median, stop here if(result == 0){ System.out.println(mid); return; } // Keep searching; direction is determined by the result if(result == 1) min = mid+1; else max = mid-1; } } }

OMG the ioi 2010 was just !!!!!!!!!!!!

i couldn’t get more than 300 out of 800 !!

LikeLike

Great solution, and relatively simple to implement (much easier than mine, anyway). Thanks for posting.

LikeLike

Here is my solutions for this problem.

—

#include “quality.h”

#include

#define MAX_NUM 9000001

int S[3002][3002];

void comp_S(int x, int R, int C, int Q[3001][3001])

{

for(int i = 0; i = Q[i][0]);

for(int i = 0; i = Q[0][i]);

for(int i = 2; i <= R; i++)

for(int j = 2; j = Q[i-1][j-1]) – S[i-1][j-1] + S[i][j-1] + S[i-1][j];

}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])

{

int Ri = MAX_NUM, Le = 1;

while(Le+1 < Ri)

{

int m = (Le+Ri)/2;

int lessthanm = 0;

comp_S(m, R, C, Q);

for(int i = H; i <= R; i++)

for(int j = W; j W*H/2);

}

Ri = (lessthanm > 0) * m + (1-(lessthanm>0))*Ri;

Le = (1-(lessthanm>0))*m + (lessthanm > 0)*Le;

}

return Ri;

}

LikeLike

Actually my solution was using binary search and precalculation.

First I calculate the partial sums in array S[MAX][MAX], there i store number of elements lesser than m from begining of an array till some index (i,j) .Secondly, in binsearch i choose and integer m and ask following question, is there a median lesser than m in any of the rectangles? if yes i search for a lesser value else I go higher. Eventually I make N^2 iterations over all rectangles by iterating through all bottom right points of all rectangles and checking whether there is a median lesser than x for constant time, and i do it lg(N) times. Which gives me complexity of approximately O(N * lg(N) + N) where N is the total number of elements in the matrix which is R*C.

LikeLike