PROBLEM LINK:#
Author:
Kunal Khanna
Editorialist:
Pradeep Joshi
DIFFICULTY:#
medium-hard
PREREQUISITES:#
Matrix ( multiplication , exponentiation ) , Math
PROBLEM:#
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.
QUICK EXPLANATION:#
======================
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.
EXPLANATION:#
===============
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