## IPSC 2009

## Solution to Problem R – Reverse quick search

Once again, the easy set can easily be solved by hand. For the hard set a greedy approach works. We generated
the inputs for Q using a randomized backtracking algorithm – we always find the first cell that does not belong
to any polygon, generate a random polygon that contains it, check that the remaining area is still connected, and
if yes, we continue recursively.

Of course, those who are good with pen and paper puzzles can solve even R2 by hand: