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
- correct row; correct column
- correct row; wrong column
- wrong row; correct column
- 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.
I solved it without using matrix exponentiation or Markov chain…Just used some observations.
now we have to do this for every element in the matrix for k times. so we will get k states of the matrix.
a,b doesn’t matter so let’s keep them 1,1. The initial matrix will be A11 = 1 rest all elements 0.
The final answer will be the A11 element from the kth state.
This will give O(N^3). We can use a key observation to reduce it to O(N).
At any given state the matrix will always look like this. for given i=2 and j=2.
We can keep track of only a,b,c and reduce it to O(N).
My solution - CodeChef: Practical coding for everyone
1 Like