Grid painting - Editorial

Problem link : contest

Difficulty : Hard

Pre-requisites : Matrix exponentiation, dp

Solution :

  • When X = 1, You can do a simple dp. For optimizing that dp, you need to use matrix exponentiation.
  • When X = 2, Idea is similar, but this time rows and coloumns of matrix will be larger.
  • When X = 3, You can notice that matrix created will be sparse, You can use this observation very well. As N is very small. Assume you want to compute A^n where n is small. Note that we will
    keep multiplying A by A, then A^2 by A, then A^3 by A, In the process we are always doing a multiplication by a sparse matrix.
    You can also do a dp here too. You don’t need matrix exponentiation too.

Setter’s solution: link