×

# WW2 - editorial

Practice
Contest
Author: Lalit Kundu
Tester: Tasnim Imran Sunny
Editorialist: Devendra Agarwal

Medium

# PREREQUISITES:

Matrix Multiplication and Fast Exponentiation

# PROBLEM:

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.

# SOLUTION:

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:

This question is marked "community wiki".

56273842
accept rate: 0%

In explaination from Setter, what is he trying to do in following statement ->

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.

How does it gives the answer ?

(20 Jun '17, 18:18)

 2 i am unable to under the editorial soln, "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] ]." Can some body explain me what does above lines mean ??? According to me if m=4 , then it should be like this for n=1 [1 1 1 1] for n=2 [1 2 2 1] for n=3 [3 5 5 3] for n=4 [5 8 8 5] where each arr[i][j] represents no of ways to reach that cell. answered 22 Sep '14, 00:43 31●3 accept rate: 0% Please see my answers below containing setter's and mine explanation. (22 Sep '14, 00:49) @deepansh90 : Please look at that section again. I hope that i made it clear. (24 Sep '14, 13:28)
 1 This is the explanation from the setter. It would be incorporated into the editorial. 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). answered 22 Sep '14, 00:48 2.5k●52●136●170 accept rate: 20%
 1 Alternatively this is my explantion, This will also be incorporated into editorial. 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) answered 22 Sep '14, 00:50 2.5k●52●136●170 accept rate: 20% 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 So now our single matrix will be E * O what will be the values of E and O for n=4 ? (22 Sep '14, 00:59) That is your homework to figure out. Actually you can find that using my above answer using setter's approach. (22 Sep '14, 01:10)
 0 Getting WA in this question.... Did the same as stated in editorial.. Don't know which case I'm leaving... Plzz Jst give me the test case that I'm leaving.. Soln link:-- http://www.codechef.com/viewsolution/4884039 Thnx for your help answered 23 Sep '14, 02:53 46●7 accept rate: 0%
 0 @dpraveen. I didnt understood this line "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." and how can we say that "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). " please help i read it many times but cant understand answered 01 Oct '14, 21:09 64●3●7●19 accept rate: 0%
 0 Still haven't understood the editorial. From the example with m=4 and n=2, how can you reach the first column of second row from first column of first row? I thought that you could only move diagonally if you're in the odd row. answered 10 Oct '15, 20:55 1 accept rate: 0%
 0 I am not able to understand What's wrong with this approach.Can anyone help? void path(long row,long col,long n,long m,long long& ans){ if(row>n||col>m||row<1||col<1) return; if(row==n&&col==m){ (ans=ans+1)%1000000007; return; } if(row==n&&col>t; while(t--){ long n,m; cin>>n>>m; if(n==1){ cout<

i have used dp and i dont find any problem with my code but WA here is my code , pls anyone help

# include<iostream>

using namespace std; int main() { long t,i,j,n,m,s;

cin>>t; while(t--) { s=0; cin>>n>>m;

int *ans= new int[n+1]; for(long p=0;p<=n+1;p++) ans[p]=new int[m+1];

for(i=n;i>=1;i--) { for(j=1;j<=m;j++) { if(i==n) ans[i][j]=1;

 else if(i%2!=0)
{
if(j==1)    ans[i][j]=(ans[i+1][j+1])%1000000007;
else if(j==m)   ans[i][j]=ans[i+1][j-1]%1000000007;
else {  ans[i][j]=(ans[i+1][j-1] +  ans[i+1][j+1])%1000000007; }
}

else if(i%2==0)
{
if(j==1) ans[i][j]=(ans[i+1][j]  +  ans[i+1][j+1])%1000000007;
else if(j==m)  ans[i][j]=(ans[i+1][j]  +ans[i+1][j-1])%1000000007;
else    ans[i][j]=(ans[i+1][j]  +  ans[i+1][j-1]  +ans[i+1][j+1])%1000000007;
}


} }

//for(i=1;i<=m;i++) cout<<ans[2][i]<<" "; for(i=1;i<=m;i++) { s+=(ans[1][i])%1000000007; }

cout<<s%1000000007; }

return 0; }

24225
accept rate: 25%

n <= 10^9.

(22 Sep '14, 19:27) 6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×2,559
×153
×119

question asked: 22 Sep '14, 00:14

question was seen: 6,855 times

last updated: 24 Nov '18, 21:07