PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
At first, we consider the cases where C is small, for example we assume C 50. Then, the problem can be solved by using dynamic programming (DP).
In DP, we calculate the probability that each state occurs. When we focus the intersection (r, c), the states are the connection relationship among the intersections (r-1, c), (r-2, c), …, (1, c), (R, c-1), (R-1, c-1), …, (r, c-1) and (1, 1). We ignore the states that (1, 1) doesn’t connect with any other intersections. Next, our focus is moved to the intersection (r+1, c), if r = R then we move to (1, c+1). We can calculate the probabilities for the new states by using the probabilities that the roads from (r, c) to (r+1, c), and from (r+1,c-1) to (r+1, c) are destroyed. It takes O(S * R2) time for constructing the relationship among the states, and O(S * R * C) time for DP, where S is the number of states. If R = 8, then the number of states S = 6435.
Next we consider the cases having larger C. Let the answer be X(R, C, p). Then X(r, c+1, p) / X(r, c, p) converges some constant as c goes to infinity. Let Cmax be enough large, and L(r, p) = X(r, Cmax, p) / X(r, Cmax-1, p). Then we can calculate the answer as X(R, cmax, p) * L(R, p)C-Cmax for large C. If p is large, X(r, c+1, p) / X(r, c, p) converges very fast, otherwise the answer is converges to 0 very fast. So we can check that around 40–50 for Cmax is enough for this problem. Therefore we obtain an O(S * R2 + S * R * Cmax) time solution.
Of course, one question is remaining. Why X(r, c+1, p) / X(r, c, p) should converge? Let P(s, c) be the probability that the state s occurs when we focus the intersection (1, c), and let the normalized version be N(s, c) = P(s, c) / (P(1, c) + P(2, c) + … + P(S, c)). If it is shown that N(s, c) converges as c goes to infinity for all 1 ≤ s ≤ S, then it is clear that X(r, c+1, p)/ X(r, c, p) should converge. It is well-known fact that an ergodic Markov chain has a unique equilibrium distribution. (See wikipedia: Markov chain for details) In this problem has a very similar structure, therefore X(r, c+1, p) / X(r, c, p) converges.
I omit a rigorous proof, but some clues for proof are noted here. We can use Perron-Frobenius theorem. Let A be the transition matrix between set of states of two consecutive columns. Note that the number of states are different from above algorithm, because we focus only the intersection (1, c) here, then the number of reachable states is smaller. And let eigenvalues of A be E1, E2, …, (|E1 | ≥ |E2 | ≥ …). Since A is non-negative, irreducible, and aperiodic, then |E1| |E2| from Perron-Frobenius theorem. And Perron-Frobenius theorem says the only eigenvector whose components are all positive are those associated with the eigenvalue E1. Therefore N(s, c) converges to some element of the eigenvector.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.