I_love_Saundarya's blog

By I_love_Saundarya, history, 9 days 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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 days 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

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Hint for a proof
    • »
      »
      »
      8 days 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.

»
9 days 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.