Given a M*M chessboard and a king at initially (x,y) and a number of moves N. In how many distinct ways can the king move exactly N moves such that he never leaves the chessboard.
1<=M<=20
1<=X,Y<=M
1<=N<=10^9
My solution uses symmetry reductions followed by matrix exponentiation.
Complexity (M*M/8)^3 * log n
Author:
Kunal Khanna
Editorialist:
Pradeep Joshi
medium-hard
Matrix ( multiplication , exponentiation ) , Math
Given a m*m matrix and a starting point x,y in the matrix , one can move in all adjacent 8 cells within matrix in one step. You need to calculate no. of distinct ways one can move in n steps from initial point.
======================
Using symmetry we can observe that we need to calculate moves for only few elements as elements left to principal diagonal of one fourth of matrix in my solution . By mapping relevant cells into matrix we can calculate total no. of distinct ways using matrix exponentiation .we
===============
Basic solution :
We can recurse on each adjacent 8 cells provided move is within matrix till depth of n and calculate total no. of ways .
int fun( int x , int y , int n ) {
if( x < 1 || x > m || y < 1 || y > m )
return 0 ;
else if( n == 0 ) return 1 ;
int sum = fun(x+1,y,n-1) + fun(x+1,y-1,n-1) + fun(x+1,y+1,n-1) + fun(x,y-1,n-1) + fun(x,y+1,n-1) + fun(x-1,y-1,n-1) + fun(x-1,y,n-1) + fun(x-1,y+1,n-1) ;
return sum ;
}
But above approach will give TLE as time complexity of above approach is O(8^n) , which is too much to handle.
Can we do better ?
Yes , we do . By using the fact that : “The number of paths in a graph of length N. (Exponentiate the adjency matrix of the graph to N and the value of the (i, j)th element in the exponentiated matrix is the number of paths of length N from the i’th vertex to j’th vertex).”
How to construct graph ?
Each cell of a matrix will work as node of a graph hence for matrix of size m there will be mm nodes , to represent it as an adjacency matrix we need a matrix of { mm , m*m } size . In adjacency matrix we will mark 1for each cell where one can move from it’s current node . eg. Let’s say a matrix of size ( 2X2 ) and cell { (1,1) , (1,2) , (2,1) , (2,2) } is mapped as node 1, 2 , 3 , 4 respectively . if one is currently at cell (1,1) i.e. node 1 and it can move to cell { (1,2) , (2,1) , (2,2) } which are node 2 , 3 , 4 . We will mark matrix 1 = matrix 1 = matrix 1 = 1 hence
matrix 2 = matrix 3 = matrix 4 = 1 as graph will be bi-directional .
Now calculate exponentiation of matrix n times , exponentiation can be done best in O( logn ) time but each time we need to multiply two matrix of size { mXm , mXm } , so total complexity will be ( mXm )^3( logn ) i.e (m^6(logn) ) . Answer can be calculated by summing all elements of row of node representing starting point of move . But this will also give time limit .
Can we do better ?
Yes , By using symmetry as many cells will turn into similar behaviour or answer due to symmetric property of matrix . Hence instead of considering all cells as nodes of graph we will consider only relevant cells as elements left to principal diagonal of matrix , one fourth of original matrix . We will mark our selected or relevant node by some unique numbers starting from 0 in our case . For example matrix of size 4X4 we can mark node as :
0 1 1 0
1 2 2 1
1 2 2 1
0 1 1 0
here cell (1,1) , ( 2,1) and (2,2) is marked as node 0 , 1 and 2 and rest matrix is just symmetric to it . in this way for a matrix of size( mXm ) instead of maintaining m^2 node we need to maintain only (m^2/8) nodes . Hence total complexity of problem will be reduced to (( m^2/8)^3)logn , which will be easily accepted .
Author:
Kunal Khanna
Editorialist:
Pradeep Joshi
medium-hard
Matrix ( multiplication , exponentiation ) , Math
Given a m*m matrix and a starting point x,y in the matrix, from each cell you can move to one of the adjacent 8 cells within the matrix in one step. You need to calculate the number of distinct ways one can move in n steps from an initial point.
======================
Represent the mm cells as nodes in a graph and exponentiate on the corresponding graph to get count of moves ending at each cell in the graph. To reduce time complexity, one needs to reduce size of graph from mm to m*m/8 by mapping cells which are symmetrical to each other.
===============
Basic solution :
We can recurse on each adjacent 8 cells provided the move is within matrix till depth of n and calculate total no. of ways .
int fun( int x , int y , int n ) {
if( x < 1 || x > m || y < 1 || y > m )
return 0 ;
else if( n == 0 ) return 1 ;
int sum = fun(x+1,y,n-1) + fun(x+1,y-1,n-1) + fun(x+1,y+1,n-1) + fun(x,y-1,n-1) + fun(x,y+1,n-1) + fun(x-1,y-1,n-1) + fun(x-1,y,n-1) + fun(x-1,y+1,n-1) ;
return sum ;
}
But above approach will give TLE as time complexity of above approach is O(8^n) , which is too much to handle.
Can we do better ?
Yes , we can . By using the fact that the number of nodes in the graph are M*M. (Exponentiate the adjacency matrix of the graph to N and the value of the (i, j)th element in the exponentiated matrix is the number of paths of length N from the i’th vertex to j’th vertex).
How to construct graph ?
Each cell of a matrix will work as node of a graph hence for matrix of size m there will be mm nodes , to represent it as an adjacency matrix we need a matrix of { mm , mm } size . In adjacency matrix we will mark 1 for each cell where one can move from it’s current node to that node. eg. Let’s say a matrix of size ( 2X2 ) and cell { (1,1) , (1,2) , (2,1) , (2,2) } is mapped as node 1, 2 , 3 , 4 respectively . if one is currently at cell (1,1) i.e. node 1 and it can move to cell { (1,2) , (2,1) , (2,2) } which are node 2 , 3 , 4 . We will mark matrix 1 = matrix 1 = matrix 1 = 1 hence matrix 2 = matrix 3 = matrix 4 = 1 as graph will be bi-directional . Now calculate exponentiation of matrix n times , exponentiation can be done best in O( logn ) time but each time we need to multiply two matrix of size { mXm , mXm } , so total complexity will be ( mXm )^3( logn ) i.e (m^6(logn) ) . Answer can be calculated by summing all elements of each row of node representing the ending point of move . But this will also exceed time limit .
Can we do better ?
Yes. By using symmetry as many cells will turn into similar behavior by noting symmetric property of matrix . Hence instead of considering all cells as nodes of graph we will consider only relevant cells as elements left to principal diagonal of matrix , about one fourth of original matrix.(The matrix is symmetric about X-axis, Y-axis and any principal diagonal). This is because the rest of the elements can be mapped to one of these elements. We will mark our selected or relevant nodes by some unique numbers starting from 0 in our case. For example matrix of size 4X4 we can mark node as :
0 1 1 0
1 2 2 1
1 2 2 1
0 1 1 0
here cell (1,1) , ( 2,1) and (2,2) is marked as node 0 , 1 and 2 and rest of the matrix is just symmetric to it so every other node can me mapped to one of these nodes. In this way for a matrix of size( mXm ) instead of maintaining m^2 node we need to maintain only (m^2/8) nodes . Hence total complexity of problem will be reduced to (( m^2/8)^3)logn , which will be easily accepted