Author: [Lalit Kundu]
Tester: [Tasnim Imran Sunny]
Editorialist: [Devendra Agarwal]
Matrix Multiplication and Fast Exponentiation
You are given a chess board of nxm size. From odd row, you can move from black spot to neighbouring black spot in the next row. From even row , you can move to any neighbouring spot in the next row. Your aim is to find the total number of Ways to reach the end row starting from the first row.
Let us first solve the problem where we can move into any neighbouring spot in the next row.
We will define a state to contain m column vectors.
ith entry of the jth column denotes number of ways to reach jth column of the chess board(in this state i.e. some row , row number is the state) from ith column of the first row of the chess board.
For Ex: Let m be 4.
Set of column vectors are : even = [ [1 1 0 0] [1 1 1 0] [0 1 1 1] [0 0 1 1] ].Please note that 1D array inside the list are columns and not rows of the matrices. This is the First State i.e. N=2. Look at the first column vector(i.e [1 1 0 0]), this implies number of ways to reach the 1st column of second row(of the original matrix) from first row i.e. You can reach 1st column of second row from 1st column and second column of the first row. Thus the column vector [1 1 0 0].
Now Can we get the state of column vectors for Nth Row ?
Yes , It will be evenN-1.
Assume that you are currently at a state which can be represented as a coloumn vector.
Now you are making some transitions from this state to some another state.
All transitions are based not on the values of the current coloumn vector we are having but on some constant things (eg. in this case row number).
Now you can observe that if this is the case, then you can always represent your transition from one coloumn to other coloumn as a process of multiplying the starting coloumn vector by some matrix.
Note that the matrix is independent of the values of your current coloumn vector, So you can treat it as a constant matrix.
So multiplication of n such matrices can be considered as doing An.
Now let us come back on our problem.
Here we need to make one more matrix , odd matrix for coming from even state to odd state. [ We have seen it for odd state to even state ]. We can construct the basic column vectors.
Now, we will alternatively multiply even and odd to get to N-1 states. This can be done by fast exponentiation.
We will use T = even*odd matrix. Our answer would be T(N-1)/2 * even if (N-1) is odd otherwise T(N-1)/2.
Explanation from Setter
We can form a basic dp. DP[n][j]=DP[n-1][j-1] + DP[n-1][j] + DP[n-1][j+1] if, n is odd, DP[n][j]=DP[n-1][j-1] + DP[n-1][j+1] if, n is even
We have to solve for large N. If we have say, DP[n][a]=DP[n-1][a_1] + DP[n-1][a_2] … + DP[n-1][a_n], we build a matrix in which DP[a][a_i] is 1 for all i. The sum of all elements in (N-1)'th power of this matrix will give us the answer.
But here, our DP depends on if n is odd or even. So we build two matrices, matrix-even and matrix-odd. Our answer is multiplication of these matrices one after the other alternately.
So, we find the (N/2)'th power of multiply (matrix-even, matrix-odd) and multiply with matrix-even depending on the requirement. We can multiply matrices in M^3. So, total complexity is O(N*M^3).
Alternatively this is my explantion, This will also be incorporated into editorial.
Explanation from Praveen
You can simply think it like this. Assume that you are currently at a state which can be represented as a coloumn vector. Now you are making some transitions from this state to some another state.
All your transitions are based not on the values of the current coloumn vector you are having but on some constant things (eg. in this case row number) Now you can observe that if this is the case, then you can always represent your transition from one coloumn to other coloumn as a process of multiplying the starting coloumn vector by some matrix.
Note that your matrix is independent of the values of your current coloumn vector, So you can treat it as a constant matrix. So multiplication of n such matrices can be considered as doing A^n.
Now in our problem, in even case, we have different matrix for multiplication and for odd case different So Assume the starting vector is V.
let us denote the matrix to be multiplied in the even case by E and in the odd case by O So we will do, V * E, then V * E * O, then V * E * O * E, etc.
So now our single matrix that we were saying to multiply with the coloumn vector will be E * O. You can multiply this matrix n / 2 times and by one single matrix O if required (case when n is odd)
AUTHOR’S and TESTER’S SOLUTIONS: