# PROBLEM LINKS

Practice

Contest

# 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** * **R**^{2}) 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 **C**_{max} be enough large, and **L(r, p)** = X(r, **C**_{max}, p) / X(r, **C**_{max}-1, p). Then we can calculate the answer as **X(R, c**_{max}, 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 **C**max is enough for this problem. Therefore we obtain an **O(S * R2 + S * R * C**_{max}) 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 **E**_{1}, **E**_{2}, ..., (**|E**_{1 }| ≥ |**E**_{2} | ≥ ...). Since A is non-negative, irreducible, and aperiodic, then |**E**_{1}| **|E**_{2}| from Perron-Frobenius theorem. And Perron-Frobenius theorem says the only eigenvector whose components are all positive are those associated with the eigenvalue **E**_{1}. 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.