Quality of Living

Source: IOI 2010 (Day 1, Task 3), alternate link

1. Read the problem and summarise the task.
   • Try to keep your response to a couple of sentences.
   • Note the different format.
     • You write a function rather than the whole program.
     • No input scanning; it’s provided in arguments to the function.
     • No output printing; return the answer instead.
2. Propose a naive algorithm to solve the problem.
   • For every subrectangle of the desired size, find the median somehow.
   • Analyse the time complexity of your algorithm, and estimate its running time.
   • You should find that it’s too slow.
3. Identify at least two avenues by which to potentially reduce the running time of the algorithm, and evaluate which (if any) of these might be viable.

Would this problem be easier if we were instead testing a proposed median?

4. Consider the following related task: given the same input but also an integer T, design a function hasRectangle() which returns a boolean representing whether or not there is an H x W rectangle of median T. If this task could be solved efficiently, could we then solve the original problem efficiently too?
   • If so, write a wrapper function which solves the original problem using (asymptotically) as few calls to hasRectangle() as possible.
   • If not, modify the statement of the above task until we can use it to solve the original problem, and write a wrapper as above.
   • Reflector: design some test cases to check the correctness of this wrapper, particularly regarding off-by-one errors.

Now, we get to the question of testing a proposed median.

5. Propose a target time complexity for testing a proposed median, and discuss how that work might be distributed between preprocessing and querying each subrectangle.

6. Design an algorithm that tests a proposed median, and evaluate whether it meets the target time complexity.
   • This is hard!
   • Presenter: talk to other groups if you need a hint!
7. Implement your algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Run your tests and debug if necessary.
8. Submit your program for judging!
   • Debug as required.