Pebbles

Source: PACNW 2007

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

The input format is very unpleasant. We will never ask you to infer the number of test cases per file or the size of a grid by parsing the values and accounting for the whitespace. Let’s instead suppose the number of test cases is at most 100 and given in the first line of input, and that each grid is preceded by a single line containing its dimension.

2. Choose a natural order to assign pebbles.

3. Propose a very simple subproblem, so that if you knew the answer to all subproblems, then you could deduce the overall answer. Start with as few parameters as possible.

4. When you are at a square, what information would let you know whether it is legal to place a pebble here?
   • This should be part of your subproblem specification.
   • What further information do you need to know in order to maintain it? That should also be part of your subproblem specification.
   • Continue until this stabilises.
   • What data structure can be used to collect all these additional parameters?

5. Form a recurrence between your subproblems.

6. Analyse the time complexity of your algorithm, and estimate the running time.
   • If the algorithm is too slow, consider optimisations to reduce the number of subproblems or the work per subproblem.
7. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.

Unfortunately this problem isn’t available for judging.