WW2 - editorial

editorial
, , ,
1

PROBLEM LINK:

[Practice][1]
[Contest][2]
Author: [Lalit Kundu][3]
Tester: [Tasnim Imran Sunny][4]
Editorialist: [Devendra Agarwal][5]

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][6]
[Tester’s solution][7]
[1]: http://www.codechef.com/problems/WW2
[2]: http://www.codechef.com/COOK50/problems/WW2
[3]: http://www.codechef.com/users/darkshadows
[4]: http://www.codechef.com/users/rustinpiece
[5]: http://www.codechef.com/users/devuy11
[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/WW2.cpp
[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/WW2.cpp

4 Likes
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.

1 Like
3

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

4

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

5

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)

6

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 ?

7

That is your homework to figure out. Actually you can find that using my above answer using setter’s approach.

8

i have used dp
and i dont find any problem with my code but WA
here is my code , pls anyone help
#include
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;
}

9

n <= 10^9.

10

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

11

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

12

@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

13

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.

14

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 ?

15

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