Good point, a link to the greedy submission: https://codeforces.me/gym/102920/submission/105509314

But maybe only people who solved the problem can view this submission, this is actually weird. Hmm, I'm not sure if I can just copy paste that code here, as that one is not by me. But the main idea in a nutshell is:

Visit every row from top to bottom and every cell from left to right within the current row. If the current cell is a '1' (and not covered yet), then try fitting a horizontal 1x2 starting from this cell. If you cannot, but the previous 2 cells were covered with a 1x2, change that to a 1x3 horizontal. If you can't do this either, try fitting a vertical 3x1 starting from the cell. If you still can't do that, fit a 2x1 vertical starting from the cell.

I think this greedy is tricky, I almost believed it, but then I found this counter-example. So now I'm still confused about the situation.

Your example is not valid, because the polyomino cannot contain any 'holes'. (I also thought about your example first before I came up with the one I showed above which 'hacks' some solutions.)

Also, I can try to explain the main idea of my solution (there might be significantly easier ones though):

Let's call a cell critical if it is a '1' and there is no 2x2 square of only '1's that contains this cell. Let's call a cell normal if it is a '1', but it is not critical. Now we can find the connected components of normal cells in the graph. Then we will remain with a tree structure with connected components and some 'channels' going between them formed by the critical '1's. (Note that this is something very similar to doing biconnected components, but not exactly. Also note that we used here that there are no 'holes' to get a tree)

Claim 1: every component here can be just tiled greedily with either only vertical tiles or only horizontal ones. (You can prove this by showing that it is impossible in a component to have a cell with no vertical neighbours and can do the same for horizontal... and we can use the fact that any 1 x K can be tiled when K > 1)

Claim 2: given a component and a critical cell that is adjacent to it, you can tile this greedily. (if the extra cell is vertically connected to it, the vertical greedy will work, otherwise the horizontal greedy.)

Now we can just root our tree at one of the components and recursively do the following:

• tile our component using either Claim 1 or Claim 2.

• start recursively tiling all adjacent channels with 1x2 dominos (note that these channels can be uniquely covered with 1x2 dominos greedily)

• when a channel 'arrives' to another component, we have two cases: if the last cell of the channel did not have a pair, we can just tile it with that component using Claim 2. Otherwise, we can just only tile the component with Claim 1 and follow the recursion from there.

So it's some kind of a dfs. Hope this makes sense more or less.

Ohh, that's a very nice way of approaching it :) Thanks for your explanation!

Thank u so much.