# KRYP3 - Editorial

[Contest][1]
[Practice][2]

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

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``````
3 Likes

Couldn’t figure it out during the contest :’(
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}