Editorial for ICPC NAQ 2016 B - Arcade! - DMOJ: Modern Online Judge

Editorial for ICPC NAQ 2016 B - Arcade!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This (zero-player) game is an example of a Markov chain.
For background, see Grinstead and Snell, Ch. 11.
Three solution approaches:
1. Compute expected values via system of equations
2. Compute absorption probabilities
3. Simulate Markov chain for finite number of steps

Approach 1

Let $E_i$ $E_{i}$ denote the expected payout if the ball is currently at hole $i$ $i$ , and let $c_i$ $c_{i}$ denote the payout for dropping into hole $i$ $i$ . Then: $\displaystyle E_i = p_4 c_i + p_0 E_a + p_1 E_b + p_2 E_c + p_3 E_d$ $E_{i} = p_{4} c_{i} + p_{0} E_{a} + p_{1} E_{b} + p_{2} E_{c} + p_{3} E_{d}$ where $a, b, c, d$ $a, b, c, d$ are the neighbors of hole $i$ $i$ .
If $H = N(N+1)/2$ $H = N (N + 1) / 2$ is the number of holes, this gives a system of $H$ $H$ linear equations in $H$ $H$ variables, which can be solved using Gaussian elimination in $\mathcal O(H^3)$ $O (H^{3})$ .
The input constraints imply that the system is consistent and has a unique solution.
Can be derived without knowing Markov chain theory.

Approach 2

Uses Markov chain theory directly.
Model each hole as a transient state, model falling into a hole as an absorbing state. Have $H = N(N+1)/2$ $H = N (N + 1) / 2$ transient and $H$ $H$ absorbing states.
Build $H \times H$ $H \times H$ transition matrix $\mathbf Q$ $Q$ , use Gaussian elimination to compute fundamental matrix $\mathbf N = (\mathbf I-\mathbf Q)^{-1}$ $N = (I - Q)^{- 1}$ .
Compute absorption probabilities $\mathbf B = \mathbf N \mathbf R$ $B = N R$ where $\mathbf R$ $R$ is the $H \times H$ $H \times H$ diagonal matrix $\mathbf R_{i,j}$ $R_{i, j}$ of being absorbed (falling into the hole) $j$ $j$ when hovering over hole $i$ $i$ .
Compute expected value as dot product of first row of $\mathbf B$ $B$ with expected payout. (Optimize to compute only first row of $\mathbf B$ $B$ .)

Approach 3

Keep track of probability of being over hole $i$ $i$ after $k$ $k$ steps: vector of $p_{k,i}$ $p_{k, i}$ elements.
For all $i$ $i$ , compute $p_{k+1,i}$ $p_{k + 1, i}$ from $p_{k,i}$ $p_{k, i}$ by simulating the next event of ball bouncing from hole $i$ $i$ to possible neighbors.
Compute contribution to expected payout based on probability of falling into hole $i$ $i$ at step $k$ $k$ .
Stop when probability of not having been absorbed is small enough.
Caveat: if probabilities of falling into holes are very small, this could take many iterations: exploit problem constraint that the probability of not having been absorbed drops below threshold.
Mathematically equivalent to computing first row of $\mathbf N \mathbf R = (\mathbf I-\mathbf Q)^{-1} \mathbf R = (\mathbf I + \mathbf Q + \mathbf Q^2 + \dots) \mathbf R$ $N R = (I - Q)^{- 1} R = (I + Q + Q^{2} + \dots) R$ — but will time out if done using dense matrix!

Comments

There are no comments at the moment.