Internet Problem Solving Contest

IPSC 2017

Solution to Problem M – Matching pairs

If you were to try to solve a puzzle like this by hand, you cannot afford a quadratic-time approach – comparing each pair of figures manually is too slow. Essentially, you need to come up with some good hashing function.

When looking for identical shapes and/or mirror images, distinct features of some shapes (e.g., vertices of degree 1) can be used to eliminate some of the figures quickly.

For a more robust hash function, take another few steps towards the complete (circular) sequence of vertex degrees. This is a natural extension of the previous approach, as you can do it incrementally. For example, once you are done with degree-1 vertices, you can look at the number and placement of degree-2 vertices as well, and that may already be enough.

This can also be generalized to looking for complements, but it’s much more painful. If I absolutely had to find the pair of complementary figures manually, I would probably start by spending a linear amount of time on writing the complete degree sequence around each figure. When looking for a complement of a particular figure, you then need to invert its sequence and recall/check whether you have the new one somewhere.

Of course, this being IPSC, you also had other options. In particular, you could write a program that parses the input image, recovers the individual graphs and finds the matching pairs by comparing each pair of graphs.

Probably the fastest way to solve this task would be a combination of both approaches: quickly write a simple program that can, for example, guess vertex degrees (by hard-wiring their coordinates and counting dark pixels around them) and use those to print a small set of candidate pairs to be examined by hand.