I_love_Saundarya's blog

By I_love_Saundarya, history, 5 years ago, In English

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.

»
5 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it
The answer is

P.S. This problem is similar to 1099E - Nice table

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Hint for a proof
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Thanks! Your hint really helped me and I was able to prove it.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

By the way, if you are interested in a slightly similar problem, check out 1178C - Tiles.