Editorial for WC '18 Contest 2 S3 - Multitasking


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.

At any given point in the bomb defusing process, Ilsa has cut i wires, completely defused a bombs, and partially defused b bombs. A partially-defused bomb has exactly one of its wires cut.

We can do dynamic programming where DP[a][b] is the probability that there are a completely-defused bombs and b partially-defused bombs after Ilsa has cut 2a+b wires. Necessarily, the sum of all DP values for the same number of wires cut must equal 1. Note that all numbers of cut wires i are equally likely before Ethan walks into the room.

We start with DP[0][0] = 1, and with all other DP values initialized to 0. When 0 wires have been cut, it must be the case that no bombs are either completely or partially defused. We can then iteratively compute the DP value for all states where 1 wire is cut, then 2 wires, and so on as follows:

For a given number of wires i, such that we've already computed all DP values that correspond to i wires being cut, we can compute the values for i+1 wires being cut by iterating over all possible states (a, b) such that 2a+b = i. For each such state, we compute the probability p that the next wire cut will completely defuse a partially-defused bomb, and the probability q that the next wire cut will be the first wire cut on a new bomb:

  • There are b wires that would complete a partially-defused bomb if cut, and 2N-i uncut wires. Therefore, p = \frac{b}{2N-i}.
  • p and q must sum to 1. Therefore, q = 1-p.

Then, we update two of the states for i+1 wires as follows:

  • With probability p, there will be one more completely-defused bomb and one fewer partially-defused bomb. Therefore, we can increase DP[a+1][b-1] by DP[a][b] \times p.
  • With probability q, there will be one more partially-defused bomb. Therefore, we can increase DP[a][b+1] by DP[a][b] \times q.

Let U be the random variable of the number of uncut wires (and let u be a specific number of uncut wires). The answer we actually want to compute is the expected number of uncut wires, given that we know that there are K completely-defused bombs:

\displaystyle E[U \mid a = K] = 1 \times P(U = 1 \mid a = K) + \dots + 2N \times P(U = 2N \mid a = K)

Let S[K] be the sum of DP[K][b] over all possible values of b. We can then state that:

\displaystyle P(U = u \mid a = K) = \frac{DP[K][2N-2K-u]}{S[K]}

The probability of being in a given state (a, b) that corresponds to u uncut wires is proportional to DP[a][b]. Since all values of u are equally likely without any information, the probability of being in state (a, b) is simply \frac{DP[a][b]}{S[K]} after you know that a = K.

Computing the table of DP values takes \mathcal O(N^2) time, and combining them together takes \mathcal O(N) time, so the total time complexity is \mathcal O(N^2).

Taking the second sample case as an example, there are three states in which Ethan might walk in on Ilsa: (0, 0), (0, 1), and (0, 2), since a is known to be 0. It must be the case that Ilsa has 2, 3, or 4 wires remaining since with any fewer wires remaining there would have been at least 1 completely-defused bomb. All of these values of u are equally likely when Ethan walks into the room, but when he observes that no bombs have been completely defused, the chance that exactly 2 wires remain uncut is decreased since there's a chance that one bomb would have been completely defused by that point.

The chance that 2 cut wires belong to the same bomb (out of 2 total bombs) is \frac 1 3, so the chance of having 2 wires uncut and 0 completely-defused bombs is only \frac 2 3 the chance of having 3 wires uncut or 4 wires uncut. Observe that DP[0][2] = \frac 2 3, while DP[0][0] = DP[0][1] = 1.

\displaystyle \begin{align*}
P(U = 4 \mid a = 0) &= \frac{DP[0][0]}{S[K]} = \frac{1}{8/3} = \frac 3 8 \\
P(U = 3 \mid a = 0) &= \frac{DP[0][1]}{S[K]} = \frac{1}{8/3} = \frac 3 8 \\
P(U = 2 \mid a = 0) &= \frac{DP[0][2]}{S[K]} = \frac{2/3}{8/3} = \frac 2 8
\end{align*}

Dropping terms that equal 0, the answer we want to compute is:

\displaystyle \begin{align*}
E[U \mid a = 2] &= 2 \times P(U = 2 \mid a = 0) + 3 \times P(U = 3 \mid a = 0) + 4 \times P(U = 4 \mid a = 0) \\
&= \left(2 \times \frac 2 8\right) + \left(3 \times \frac 3 8\right) + \left(4 \times \frac 3 8\right) \\
&= \frac{25}{8} = 3.125
\end{align*}


Comments

There are no comments at the moment.