PROBLEM LINK:Practice DIFFICULTY: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. Assume that you are currently at a state which can be represented as a coloumn vector. Now let us come back on our problem. Explanation from SetterWe can form a basic dp. DP[n][j]=DP[n1][j1] + DP[n1][j] + DP[n1][j+1] if, n is odd, DP[n][j]=DP[n1][j1] + DP[n1][j+1] if, n is even We have to solve for large N. If we have say, DP[n][a]=DP[n1][a_1] + DP[n1][a_2] ... + DP[n1][a_n], we build a matrix in which DP[a][a_i] is 1 for all i. The sum of all elements in (N1)'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, matrixeven and matrixodd. Our answer is multiplication of these matrices one after the other alternately. So, we find the (N/2)'th power of multiply (matrixeven, matrixodd) and multiply with matrixeven 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 PraveenYou 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".
asked 22 Sep '14, 00:14

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] answered 22 Sep '14, 00:43
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)

This is the explanation from the setter. It would be incorporated into the editorial. We can form a basic dp. DP[n][j]=DP[n1][j1] + DP[n1][j] + DP[n1][j+1] if, n is odd, DP[n][j]=DP[n1][j1] + DP[n1][j+1] if, n is even We have to solve for large N. If we have say, DP[n][a]=DP[n1][a_1] + DP[n1][a_2] ... + DP[n1][a_n], we build a matrix in which DP[a][a_i] is 1 for all i. The sum of all elements in (N1)'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, matrixeven and matrixodd. Our answer is multiplication of these matrices one after the other alternately. So, we find the (N/2)'th power of multiply (matrixeven, matrixodd) and multiply with matrixeven 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

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

@dpraveen. I didnt understood this line "We have to solve for large N. If we have say, DP[n][a]=DP[n1][a_1] + DP[n1][a_2] ... + DP[n1][a_n], we build a matrix in which DP[a][a_i] is 1 for all i. The sum of all elements in (N1)'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

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

I am not able to understand What's wrong with this approach.Can anyone help?
} int main() { long t; cin>>t; while(t){ long n,m; cin>>n>>m; if(n==1){ cout<<m<<"\n"; continue; } long long ans=0; path(1,1,n,m,ans); cout<<(ans)%1000000007<<"\n"; ans=0; } return 0; } answered 24 Nov '18, 21:05

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;
} } //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; } answered 22 Sep '14, 05:46

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[n1][a_1] + DP[n1][a_2] ... + DP[n1][a_n], we build a matrix in which DP[a][a_i] is 1 for all i. The sum of all elements in (N1)'th power of this matrix will give us the answer.
How does it gives the answer ?