Editorial for Create Some Walls!

By linearity of expectation, we can compute the contribution of vertical walls and horizontal walls individually. Suppose we're considering vertical walls, the horizontal walls are completely the same.

First, let us look at the point from a different view (for computation of vertical contributions). At each point, we have a set of vertical segments. Each segment represents a room. When we have to draw a vertical wall, we basically pick a segment randomly, add its length to answer, and create a new copy of that segment, increasing room count. When we have to draw a horizontal wall, we divide some segments into two parts. So we can think of the problem like this, start with segment $[0, L]$, when you see 'V' randomly choose a segment from the set, duplicate it and add its length to answer; when you see 'H', randomly choose a segment and divide it into two random parts. The problem is still too hard, as we don't know how the segments are cut.

So we break the whole segment $[0, L]$ into infinitesimally small segments. Suppose $ds$ is such a segment. We'll find the contribution of this segment then sum (integrate) it for the whole $[0, L]$. Suppose $ds \cdot k$ is its contribution, then $L \cdot k$ will be the whole vertical wall contribution.

Now the horizontal walls for 'H' don't really have any effect on $ds$. Only the vertical wall has an effect and that effect is to add $1$ to $k$ if $ds$ or one of its duplicates were chosen in the room selection. In the language of expected value, we have to add $\frac{cnt}{rooms}$ (the probability of one of the duplicates being selected), where $cnt = $ count of $ds$'s duplicates, and $rooms = $ number of current rooms. Then what we add is $E\left[\frac{cnt}{rooms}\right] = \frac{E[cnt]}{rooms}$. So we need $E[cnt]$. But the fact is that $E[cnt]$ is actually the same as $k$. So we have the recursion $E_{new}[cnt] = E_{old}[cnt] + \frac{E_{old}[cnt]}{rooms}$, whenever we see a 'V'. And this gives us $k$.

The same can be done for horizontal walls, and we'll get the final answer.


    0% Solution Ratio