ICPC Online Round - Grid Shuffle - SHUFGRID

Can somebody explain to me the solution for Grid Shuffle from the ICPC Online Round 2019?

To solve this problem you need to think about what information is necessary and what is not. Combine that with a Markov chain, et voilá.

So, very noob with Markov chains, but should I be thinking in the direction of calculating a transition matrix, then try to exponentiate that to power k, something like that?

Yup, that’s the idea. But to reduce the time complexity you need to think about what “states” should be in that matrix and which ones shouldn’t.

And if you don’t already know the trick, search for “fast exponentiation”

Yeah, you mean matrix exponentiation, right? But I’m having trouble figuring out the transition matrix.

First question: does all the input you are given contribute to the answer?

Kinda understood the solution. There are three possible states: when it is in the same position, when it is in the same row or column, and when it is somewhere else. So we can create a 3x3 transition table, then exponentiate that to power k. This is correct, right?

And answer should not change regardless of where this cell is in the grid.

You got it, however I would have 4 states

  1. correct row; correct column
  2. correct row; wrong column
  3. wrong row; correct column
  4. wrong row; wrong column

The transition table would be the probability of going from each of these states to each of the other states.
As an example, the probability of going from state 1 to state 3 would be
\frac1{2n}\cdot\frac{n-1}n. To select the row has a probability of \frac1{2n} and the probability of a value not ending up in a particular position is \frac{n-1}n. To check you could add up all outgoing probabilities and check if they add up to 1 (I believe that means columns add up to 1).

Oh, now I see three states could work as well. Makes probability calculations a tiny bit harder however.

Solved it using 3 states: https://www.codechef.com/viewsolution/36221549

Thanks so much for the help!