Approach #1: Dynamic Programming [Accepted]
Intuition and Algorithm
f[r][c][steps] be the probability of being on square
(r, c) after
steps steps. Based on how a knight moves, we have the following recursion:
where the sum is taken over the eight pairs .
Instead of using a three-dimensional array
f, we will use two two-dimensional ones
dp2, storing the result of the two most recent layers we are working on.
dp2 will represent
dp will represent
Time Complexity: where are defined as in the problem. We do work on each layer
dpof elements, and there are layers considered.
Space Complexity: , the size of
Approach #2: Matrix Exponentiation [Accepted]
The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the -th power of this matrix represents the transition of moves, and thus we can reduce the problem to a problem of matrix exponentiation.
First, there is a lot of symmetry on the board that we can exploit. Naively, there are possible states the knight can be in (assuming it is on the board). Because of symmetry through the horizontal, vertical, and diagonal axes, we can assume that the knight is in the top-left quadrant of the board, and that the column number is equal to or larger than the row number. For any square, the square that is found by reflecting about these axes to satisfy these conditions will be the canonical index of that square.
This will reduce the number of states from to approximately , which makes the following (cubic) matrix exponentiation on this matrix approximately times faster.
Now, if we know that every state becomes some linear combination of states after one move, then let's write a transition matrix of them, where the -th row of represents the linear combination of states that the -th state goes to. Then, represents a transition of moves, for which we want the sum of the -th row, where is the index of the starting square.
Time Complexity: where are defined as in the problem. There are approximately canonical states, which makes our matrix multiplication . To find the -th power of this matrix, we make matrix multiplications.
Space Complexity: . The matrix has approximately elements.
Analysis written by: @awice