IOI 2010: Quality of living

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;
    }
  }
}