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.
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:
- Compute expected values via system of equations
- Compute absorption probabilities
- Simulate Markov chain for finite number of steps
Approach 1
- Let
denote the expected payout if the ball is currently at hole
, and let
denote the payout for dropping into hole
. Then:
where
are the neighbors of hole
.
- If
is the number of holes, this gives a system of
linear equations in
variables, which can be solved using Gaussian elimination in
.
- 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
transient and
absorbing states.
- Build
transition matrix
, use Gaussian elimination to compute fundamental matrix
.
- Compute absorption probabilities
where
is the
diagonal matrix
of being absorbed (falling into the hole)
when hovering over hole
.
- Compute expected value as dot product of first row of
with expected payout. (Optimize to compute only first row of
.)
Approach 3
- Keep track of probability of being over hole
after
steps: vector of
elements.
- For all
, compute
from
by simulating the next event of ball bouncing from hole
to possible neighbors.
- Compute contribution to expected payout based on probability of falling into hole
at step
.
- 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
— but will time out if done using dense matrix!
Comments