# KRYP3 - Editorial

[Contest]
[Practice]

Author: [Shivam Garg]
Tester: [Shiv Dhingra]

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], 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 -

``````


: https://www.codechef.com/CODR2018/problems/KRYP3/
: https://www.codechef.com/problems/KRYP3/
: http://codechef.com/users/shivamg_isc
: http://codechef.com/users/lucifer2709
: https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
: https://www.codechef.com/viewsolution/17468290``````
3 Likes

Couldn’t figure it out during the contest :’(