The decisive TopCoder Open finals hard problem

Let me remind you the hardest problem from this year's TCO finals (link to full problem statement): you are given a NxN (N<=50) grid with some cells black and some cells white. How many ways are there to place non-intersecting T-tetraminoes onto the grid such that each "central" cell of a tetramino falls onto a white cell, and each white cell is the central cell of some tetramino? You need to find this number in O(N^2).

TopCoder has published a great editorial which you can consult for more details, but I want to share an approach that is a bit different. First, we can notice that if a white cell is on the border of the field, then the corresponding tetramino can be placed immediately in exactly one way. If, after placing such tetraminoes, we find a white cell that has one of its adjacent cells already covered, we can also place the corresponding tetramino (see the picture for an example of such deterministic placement, white cells are denoted with circles). Finally, if two white cells are adjacent, we can also place the two corresponding tetraminoes. We can repeat this process until we either arrive at a contradiction, in which case we have zero solutions, or there are no more 'deterministic' tetraminoes left.

In the second case, let's consider the graph formed by the edges connecting the white cells to four neighboring black cells. It's not hard to see that its connected components can be handled separately, with the final result obtained by multiplication. When a connected component is a tree, then exactly one black cell in this connected component will remain empty (because it has 3K+1 black cells and K white cells, for example the picture on the left has 13 black and 4 white cells), and it's not hard to see that we can pick any black cell to be empty, after which the positioning of all tetraminoes is determined similarly to the "tetramino on the border" case, so we have 3K+1 solutions here.

Finally, when a connected component contains a cycle, then there are two ways to place the tetraminoes along that cycle, and all remaining tetraminoes are then placed deterministically. In case a connected component has more than one cycle, in other words the number of edges more than the number of vertices, there will be no solution (for example because the number of black cells will be fewer than 3K).