Editorial for DMOPC '22 Contest 5 P5 - Twos and Threes
Submitting an official solution before solving the problem yourself is a bannable offence.
Consider the bipartite graph formed by treating each block as a vertex in a graph and adding edges between adjacent blocks. The critical observation is as follows:
There exists a winning tiling of the region if and only if there exists a subset of the edges such that each vertex is incident to at least one edge and the edges form a collection of paths and cycles.
Indeed, the forward direction is immediate. To see the backwards direction, note that any odd-length path can be tiled using a triomino and then a series of dominoes, and any even-length path can be tiled using only dominoes. Cycles can be treated as paths by ignoring an arbitrary edge.
Now we also note that a set of edges forms a collection of paths and cycles if and only if each vertex has degree 1 or 2. With this in mind, we can construct a flow network as follows:
- Connect the source to each of the "odd" vertices with a capacity range of .
- Connect each "odd" vertex to each of the adjacent "even" vertices with a capacity range of .
- Connect each of the "even" vertices to the sink with a capacity range of .
Any flow satisfying all of the constraints corresponds to a collection of paths and cycles. To find such a flow, we may use flows with demands.