Pebbles

Original source: ICPC Pacific Northwest 2007

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

2. Our goal is to assign pebbles to certain values. In what order should we approach this?

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

6. What data structure can be used to collect all these additional parameters?

7. Form a recurrence between your subproblems.

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

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