November 25, 2010

IOI Photos have been posted

August 15, 2010

July 29, 2010

IOI Program

July 29, 2010

Schedule updated including information about new Evening Lectures.

July 5, 2010

May 27, 2010

Registration activated and many ioi2010.org web updates. # Day 1 Task 3: Quality of Living

Cities in Alberta tend to be laid out as rectangular grids of blocks. Blocks are labeled with coordinates 0 to R-1 from north to south and 0 to C-1 from west to east.

The quality of living in each particular block has been ranked by a distinct number, called quality rank, between 1 and R*C, where 1 is the best and R*C is the worst.

The city planning department wishes to identify a rectangular set of blocks with dimensions H from north to south and W from west to east, such that the median quality rank among all blocks in the rectangle is the best. H and W are odd numbers not exceeding R and C respectively. The median quality rank among an odd number of quality ranks is defined to be the quality rank m in the set such that the number of quality ranks better than m equals the number of quality ranks worse than m.

You are to implement a procedure rectangle(R,C,H,W,Q) where R and C represent the total size of the city, H and W represent the dimensions of the set of blocks, and Q is an array such that Q[a][b] is the quality rank for the block labeled a from north to south and b from west to east.

Your implementation of rectangle must return a number: the best (numerically smallest) possible median quality rank of an H by W rectangle of blocks.

Each test run will only call rectangle once.

### Example 1

```R=5, C=5, H=3, W=3,
Q=  5 11 12 16 25
17 18  2  7 10
4 23 20  3  1
24 21 19 14  9
6 22  8 13 15
```
For this example, the best (numerically smallest) median quality rank of 9 is achieved by the middle-right rectangle of Q shown in bold. That is,
```rectangle(R,C,H,W,Q)=9
```

### Example 2

```R=2, C=6, H=1, W=5,
Q=  6  1  2 11  7  5
9  3  4 10 12  8
```
For this example the correct answer is 5.

Assume R and C do not exceed 30.

Assume R and C do not exceed 100.

Assume R and C do not exceed 300.

Assume R and C do not exceed 1 000.

Assume R and C do not exceed 3 000.

### Implementation Details

• Use the RunC programming and test environment
• Implementation folder: /home/ioi2010-contestant/quality/ (prototype: quality.zip)
• To be implemented by contestant: quality.c or quality.cpp or quality.pas
• Contestant interface: quality.h or quality.pas