You are not logged in. Please login at www.codechef.com to post your questions!

×

WW2 - editorial

PROBLEM LINK:

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

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.

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:

Author's solution Tester's solution

This question is marked "community wiki".

asked 22 Sep '14, 00:14

devuy11's gravatar image

4★devuy11 ♦♦
56273842
accept rate: 0%

edited 24 Sep '14, 13:27

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) adecemberguy2★

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.

link

answered 22 Sep '14, 00:43

deepansh90's gravatar image

2★deepansh90
313
accept rate: 0%

Please see my answers below containing setter's and mine explanation.

(22 Sep '14, 00:49) dpraveen ♦♦4★

@deepansh90 : Please look at that section again. I hope that i made it clear.

(24 Sep '14, 13:28) devuy11 ♦♦4★

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).

link

answered 22 Sep '14, 00:48

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

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)

link

answered 22 Sep '14, 00:50

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 22 Sep '14, 00:52

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) deepansh902★

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) dpraveen ♦♦4★

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

link

answered 23 Sep '14, 02:53

itachiuchia's gravatar image

2★itachiuchia
467
accept rate: 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

link

answered 01 Oct '14, 21:09

baljitsingh's gravatar image

3★baljitsingh
643719
accept rate: 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.

link

answered 10 Oct '15, 20:55

ninjascript's gravatar image

3★ninjascript
1
accept rate: 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<m) { (ans=ans+1)%1000000007; }

for(long i=col;i<=m;i++)
{
    //odd
    if(row%2!=0)
    {
            path(row+1,i+1,n,m,ans);
            path(row+1,i-1,n,m,ans);

        }

    else{

            path(row+1,i+1,n,m,ans);
            path(row+1,i-1,n,m,ans);
            path(row+1,i,n,m,ans);
        }
}

}

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; }

link

answered 24 Nov '18, 21:05

menka_1234's gravatar image

1★menka_1234
11
accept rate: 0%

edited 24 Nov '18, 21:07

-2

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; }

link

answered 22 Sep '14, 05:46

gchandel6's gravatar image

4★gchandel6
24225
accept rate: 25%

n <= 10^9.

(22 Sep '14, 19:27) na2a6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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