Hi everybody!↵
↵
I recently was in a programming contest. There were 20 tasks, and one of them was as follows:↵
↵
In resume, you have C chairs and P pairs of chairs are given. The pairs $P(i,j)$ denote the probability of changing from chair $i$ to chair $j$. You are sitting in one of these chairs, and every second you have to move to another one.↵
↵
Then you have Q queries, each with two integers $C_i, s$ , where $C_i$ is the initial chair you are seated and you have to tell the chair that has the highest probability of being seated in after $s$ seconds (after $s$ changes).↵
↵
$1 \leq C_i \leq 50$↵
↵
$1 \leq s \leq 100000000$↵
↵
At first, I thought this was a simple problem, solvable using matrix exponentiation. First creating a matrix $M$, where $M_ij = P(i,j)$. The answer should be in the $C_i$ row of the resulting matrix $M^{ S}$, but the problem has the next important requirement:↵
↵
You have to output the probability as an irreducible fraction. Worst of all, you have to output ONLY the very last digits of numerator and denominator...↵
↵
For example: 15/23 -> 5/3, 19/33 -> 9/3↵
↵
I tried using Java BigInteger, doing reductions with gcd, but it was way too slow.↵
↵
This is a very interesting requirement (yet a very tough one too, at least for me). Any help will be very appreciated :) ↵
↵
(The contest has already ended, I'm not cheating, and I struggled a lot of hours with this tasks :( )
↵
I recently was in a programming contest. There were 20 tasks, and one of them was as follows:↵
↵
In resume, you have C chairs and P pairs of chairs are given. The pairs $P(i,j)$ denote the probability of changing from chair $i$ to chair $j$. You are sitting in one of these chairs, and every second you have to move to another one.↵
↵
Then you have Q queries, each with two integers $C_i, s$ , where $C_i$ is the initial chair you are seated and you have to tell the chair that has the highest probability of being seated in after $s$ seconds (after $s$ changes).↵
↵
$1 \leq C_i \leq 50$↵
↵
$1 \leq s \leq 100000000$↵
↵
At first, I thought this was a simple problem, solvable using matrix exponentiation. First creating a matrix $M$, where $M_ij = P(i,j)$. The answer should be in the $C_i$ row of the resulting matrix $M^{ S}$, but the problem has the next important requirement:↵
↵
You have to output the probability as an irreducible fraction. Worst of all, you have to output ONLY the very last digits of numerator and denominator...↵
↵
For example: 15/23 -> 5/3, 19/33 -> 9/3↵
↵
I tried using Java BigInteger, doing reductions with gcd, but it was way too slow.↵
↵
This is a very interesting requirement (yet a very tough one too, at least for me). Any help will be very appreciated :) ↵
↵
(The contest has already ended, I'm not cheating, and I struggled a lot of hours with this tasks :( )
