Editorial for DMOPC '20 Contest 7 P2 - Alice and Tiles


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AvaLovelace

Let's instead answer the equivalent question: What are the edges on the polygon's boundary, in clockwise order?

An edge is on the polygon's boundary if and only if it borders exactly one coloured tile. Also, we can compute the edges of a given tile in clockwise order fairly easily. So if we do this for all the coloured tiles and remove the edges that appear twice (by sorting or using a set data structure, for example), we get a list of all the edges on the polygon's boundary.

Now, we just need to output these edges in order. Notice that each edge in the list neighbours exactly two others. So we can create a map from each edge to its two neighbours, then trace a path from one edge to the next until we are back at our starting edge.

To make sure that this order is clockwise, recall that we computed the tiles' edges in clockwise order. We can store this directionality along with each edge. Then, when we choose an edge to start our path from, we make sure to trace it along the same direction as before.

Time complexity: \mathcal O(N \log N) or \mathcal O(N), depending on the set/map implementation you use.


Comments

There are no comments at the moment.