Hello,
I’m trying to understand why when there is a solution, the answer is 2^(k-1) instead of 2^k.
Clearly, 2^k overcounts even on a 1x1 grid but I can’t see an intuitive reason why that’s true.
Any help is appreciated.
Also, I think the solution is wrong to say that the answer is 0 if there is an odd cycle in the new graph.
Afaik, the new graph is always bipartite (edges are always between rows and columns). I think what the author meant to say was that if the 2 colors corresponding to a row/col node are in the same component then the solution is 0.
If this is the case, then I guess the problem shouldn’t be under the 2-coloring category?