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 R rows and C columns, each cell is given an unique quality rank, as in 1 being the best, 2 being the second best, and R \times C being the worst.

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

For example, given R=5, C=5, H=3, W=3:

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

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

Let’s consider brute force. There are (R-H) \times (C-W) 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 n \log n.

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 H=1500 and W=1500, 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 m, the smallest median. Let us arbitrarily ‘guess’ a value of m. For each element on the grid, we assign it -1 if it’s smaller than m, 1 if it’s greater than m, or 0 if it is equal to (and therefore is) m.

In the example above, if we choose 12 for m, 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 W columns at a time, let us keep the sums of the relevant columns in an array wsum[]. For example, in the m=12 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;
    }
  }
}

4 thoughts on “IOI 2010: Quality of living

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

    1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s