Editorial for WC '18 Contest 2 S3 - Multitasking
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 wires, completely defused bombs, and partially defused bombs. A partially-defused bomb has exactly one of its wires cut.
We can do dynamic programming where is the probability that there are completely-defused bombs and partially-defused bombs after Ilsa has cut wires. Necessarily, the sum of all DP values for the same number of wires cut must equal . Note that all numbers of cut wires are equally likely before Ethan walks into the room.
We start with , and with all other DP values initialized to . When 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 wire is cut, then wires, and so on as follows:
For a given number of wires , such that we've already computed all DP values that correspond to wires being cut, we can compute the values for wires being cut by iterating over all possible states such that . For each such state, we compute the probability that the next wire cut will completely defuse a partially-defused bomb, and the probability that the next wire cut will be the first wire cut on a new bomb:
- There are wires that would complete a partially-defused bomb if cut, and uncut wires. Therefore, .
- and must sum to . Therefore, .
Then, we update two of the states for wires as follows:
- With probability , there will be one more completely-defused bomb and one fewer partially-defused bomb. Therefore, we can increase by .
- With probability , there will be one more partially-defused bomb. Therefore, we can increase by .
Let be the random variable of the number of uncut wires (and let 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 completely-defused bombs:
Let be the sum of over all possible values of . We can then state that:
The probability of being in a given state that corresponds to uncut wires is proportional to . Since all values of are equally likely without any information, the probability of being in state is simply after you know that .
Computing the table of DP values takes time, and combining them together takes time, so the total time complexity is .
Taking the second sample case as an example, there are three states in which Ethan might walk in on Ilsa: , , and , since is known to be . It must be the case that Ilsa has , , or wires remaining since with any fewer wires remaining there would have been at least completely-defused bomb. All of these values of are equally likely when Ethan walks into the room, but when he observes that no bombs have been completely defused, the chance that exactly wires remain uncut is decreased since there's a chance that one bomb would have been completely defused by that point.
The chance that cut wires belong to the same bomb (out of total bombs) is , so the chance of having wires uncut and completely-defused bombs is only the chance of having wires uncut or wires uncut. Observe that , while .
Dropping terms that equal , the answer we want to compute is:
Comments