Contest Duration: - (local time) (300 minutes) Back to Home

## B - 01 Inversion Expected Editorial by ecnerwala

Combinatorial derivation

Consider the Young diagram of $$S$$ like the official solution. For example, the Young diagram corresponding to $$S$$ = 1101010 is:

OOO
OOO
OO
O


Now, consider the effect of flipping a random inversion. Picking a random inversion is just picking a random cell of the Young diagram. Then, swapping the elements corresponds to deleting the all cells to its right and below, and shifting the rest inwards.

For example, if we pick the cell at (1, 2) in the example above, we should delete all cells marked with X:

OXX
OXO
OX
O


and then shift the remaining O up and left by 1:

OO
O
O
O


Importantly, we phrase this process as moving the cells down-and-right of the chosen inversion.

Now, consider the probability that we ever pick a cell that originally starts at $$(a, b)$$. Note that only cells in the top-left $$a \times b$$ rectangle can affect this cell, so it should only depend on $$a$$ and $$b$$. Let this be $$f(a, b)$$. Then, we’ll casework on which cell in this rectangle we pick first. Consider the diagram below for $$a=3$$, $$b=4$$:

OOOX...
OOOX...
XXX*...
....
....
....

• *: with probability $$\frac{1}{ab}$$, we pick this cell before anything else in the rectangle, so we do use this cell.
• O: with probability $$\frac{(a-1)(b-1)}{ab}$$, we pick something strictly up and left from it, and move this cell up to $$(a-1, b-1)$$.
• X: with probability $$\frac{a+b-2}{ab}$$, we pick something in the row or column, and then we’ll never use this cell.

Thus, for $$a > 0$$ and $$b > 0$$,

$f(a, b) = \frac{1}{ab} + \frac{(a-1)(b-1)}{ab} f(a-1, b-1)$

and $$f(0, b) = f(a, 0) = 0$$.

If we expand this out, we can see that the $$\frac{(a-1)(b-1)}{ab}$$ terms telescope, so actually

$f(a, b) = \frac{\min(a, b)}{ab} = \frac{1}{\max(a, b)}$

The expected number of operations we take is just the sum of the probabilities that we use each cell, so we can sum $$f(a,b) = \frac{1}{\max(a,b)}$$ over all cells of our Young diagram to get the answer.

posted:
last update: