[Contest][1]
[Practice][2]
Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]
DIFFICULTY
MEDIUM HARD
PREREQUISITES
Matrix Exponentiation
PROBLEM
Given a matrix, and several queries denoting the start point, tell the number of ways to stay inside the matrix only with the given number of steps.
EXPLANATION
This question requires knowledge of Matrix Exponentiation. So, I would advise you to go through this [tutorial][5], and solve questions at the end in case you don’t have a basic idea about this topic.
Now, the matrix can be considered as a graph. In this graph, a cell (A,B) is connected to some other cell
(C,D) only if 1 ≤ max( | A - C | , | B - D | ) ≤ 2.
So, you can simply make another matrix X of this graph. The dimensions of this matrix will be (N^2,N^2).
The value X(i,j) will denote the number of ways to reach i^{th} point in the input matrix to j^{th} point.
If we simply apply matrix exponentiation on this matrix for the Y steps, this should get the task done.
But, let’s examine the complexity first.
Matrix Exponentiation takes O((N^{2})^{3}Log(Y)) steps. In other words, this turns out to be O(N^{6}Log(Y)) iterations.
As N in our case is 20, and Y is 10^{14}, it turns out to be 47*6.4*10^{7} = 3*10^{9} , which will time out.
On careful observation, we will be able to notice that there is symmetry in the matrix.
Let’s consider a matrix for N=4, AND Y=1.
The number of ways corresponding to each point will be -
8 11 11 8
11 15 15 11
11 15 15 11
8 11 11 8
The really useful points are just (1/8 ^{th}*N^{2}) instead of N^{2}.
Let D = (N^{2})/8. Then, the complexity will be O(D^{3}Log(Y)).
Each of the Z queries can be then answered in O(1)
SOLUTION
Setter’s solution -
[6]
[1]: https://www.codechef.com/CODR2018/problems/KRYP3/
[2]: https://www.codechef.com/problems/KRYP3/
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
[6]: https://www.codechef.com/viewsolution/17468290