## Editorial for DMOPC '22 Contest 5 P5 - Twos and Threes

**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:

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.

## Comments