Here is the link to the problem : https://www.quora.com/Can-you-share-some-trickest-coding-questions-that-you-have-faced-in-any-coding-contest/answer/Rishabh-Jain-2492
There is N x M matrix filled with 0 and 1 only, lets say a matrix is special if every 2 x 2 sub matrix in it has two 0’s and two 1’s . Find the total number of special matrices you can have for N x M.
On the hunt of an efficient solution.
$$$2^n+2^m-2.$$$
You can notice that all special matrices have very similar form:
Or the same thing but rotated by 90 degrees. For example:
So each row/column is either 101010... or 010101...
However matrices like
1010
0101
and
0101
1010
(alternating rows / columns)
can be represented both ways so we subtract two.
Unfortunately, I'm not able to come up with proof for this.
But you can verify it using bruteforce.
P.S. This problem is similar to 1099E - Nice table
kostia244's "form" that all special matrices fit is equivalent to saying "there are either adjacent equal pairs in the X-direction or the Y-direction, but not both". Assume there's an adjacent horizontal pair of the same color somewhere, and an adjacent vertical pair of the same color somewhere, and try to reach a contradiction.
If you have a horizontal pair of cells of the same color, then the cells directly above them have to be the other color, and so on, so that entire pair of columns has to be alternating, like this:
If you also have a vertical pair of the same color, then an entire pair of adjacent rows has to be alternating. Where this vertical double-column and horizontal double-row overlap, you have a contradiction.
Thanks! Your hint really helped me and I was able to prove it.
By the way, if you are interested in a slightly similar problem, check out 1178C - Tiles.