Grid Painting- Editorial

editorial
, , , , , ,
1

**Problem Link : **
[Contest][1]
[Practice][2]

**Difficulty : ** Hard

**Pre-requisites : ** DP, Matrix exponentiation, k-length paths in a graph

**Solution : **

  1. When X = 1, there is no interdependency between two different rows. All you need to do is find the number of solutions for one row, and raise it to the total number of rows.

    For the number of solutions of a single row, it is a simple linear dp.

    For, 1 ≤ i ≤ m, 1 ≤ j < y, dp[i][j] = number of rows of length i with exactly j repeated squares of black or white appended in the end.

    Base case :
    dp[1][1] = 2

    Update :
    For i > 1,

    • If j = 1, the colour of the ith block is not the same as that of the (i-1)th block.

      So, we have dp[i][1] = Σdp[i-1][k], for 1 ≤ k < (min(i+1,y))

    • If j > 1, then the colour we consider now must be the previous colour. So, dp[i][j] = dp[i-1][j-1].

    Finally, the answer is (Σdp[m][k], for 1 ≤ k < y)^n

  2. The case for X=2 is more interesting. Here, there is interdependency between two consecutive rows.

    The first thing that comes to mind is to create a dp with two parameters - the index of the current row, and the configuration of the previous row as a bitmask.

    Now, evaluating the dp for every state requires 2^M steps. And the number of states is 2^M x N. So, overall complexity is O(2^(2M)*N) which is infeasible.

    There is a standard way of resolving this issue using matrix exponentiation. What we do is look at every possible configuration of a row as a node in a graph. We connect two edges of a graph if two rows can occur consecutively, that is that they do not form a single colour box of size X x Y.

    Constructing the graph is done via a single (2^M)*(2^M) loop that checks every pair of vertices if they can be connected in M^3 time (simple brute force algorithm). The graph is stored as an adjacency matrix.

    Now, we need the number of N-1 length walks of this graph. This is a problem solved by taking the adjacency matrix A, evaluating A^(N-1), and adding all the entries of the obtained matrix.

    We perform matrix exponentiation in log N steps, where each matrix multiplication takes (2^M)^3 = 2^21 time.

  3. What happens if we apply the same solution as above for the next case of X=3?

    Again we can create vertices of the graph as the configuration of two consecutive rows of the grid.
    Two vertices are joined if and only if the second row of the first vertex matches the first row of the second vertex, and the 3 rows are compatible to the condition that no X x Y block is uni-colour.

    Note that now the adjacency matrix is 2^(2M) x 2^(2M), and multiplication will require 2^(6M) = 2^30 time which will get TLE’d.

    Interestingly, observe that although the matrix is 2^(2M) x 2^(2M), it is very sparse, and only 2^M entries may be filled in every row.

    We store this matrix as an adjacency list, and multiply by using the naive algorithm, looking at only these (non-zero) entries. The multiplication now takes 2^(5M) = 2^25 time.

    However, only the initial matrix A is sparse, and A^2, A^4… may not be. Thus matrix exponentiation will not work in log time.

    This is why N was given to be small! We can still appply the naive algorithm, and iteratively pre-multiply A (which is always sparse) to the current matrix (which may not be sparse) to obtain the final answer.

    This is a total of N steps, giving the complexity as O(N*(2^(5M))).

**Setter’s code : **


[3]

  [1]: http://www.codechef.com/WPC1401/problems/IITK1P09
  [2]: http://www.codechef.com/problems/IITK1P09
  [3]: http://www.codechef.com/viewsolution/4942842