Editorial for WC '16 Contest 1 S4 - TP
Submitting an official solution before solving the problem yourself is a bannable offence.
Computing expected values directly can be problematic, but they can often be computed based on probabilities of events instead. For example, in the case of this problem, if we let be the probability that exactly
different houses will have been TP-ed after all
passes, then the expected number of different houses to be TP-ed is
.
Now, how can we compute these values? We can use dynamic programming. Let
be the probability that exactly
houses will have been TP-ed after
passes. For starters, we know that
, and
. From a given state
, there are only
possible transitions to consider: whether the
-th pass results in
,
, or
additional houses getting TP-ed (leading to states
,
, or
). We'll need to compute the probability of each of these
transitions occurring. For starters, there are
total possible pairs of houses, and if
houses have been TP-ed so far, then
houses have not.
In order for zero new houses to be TP-ed, both targeted houses must have already been TP-ed. The number of such houses is . Therefore, the probability of this transition is
. As a result, we add
onto
.
Similarly, there are pairs of targeted houses which would result in
new house getting TP-ed, and there are
pairs which result in
new houses getting TP-ed. In the same way, we can add
onto
, and
onto
.
Finally, once we've considered all states for and
, we'll have populated the whole
array. There are
states and only a constant number (
) of transitions from each state, meaning that the time complexity of this algorithm is
. For each
,
, so we can proceed to calculate the expected value as described initially.
This problem can also be solved in with some more advanced math. For any given house,
pairs of houses result in it getting TP-ed on any given pass. Therefore, the probability of it getting TP-ed on any given pass is
, and the probability of it not getting TP-ed is therefore
. As such, the probability of any given house not getting TP-ed at all across all
passes is
. Due to the property of linear expectation, the expected number of houses which won't get TP-ed at all is simply
times that value. Thus, the expected number of houses which will get TP-ed is
.
Comments