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

## B - 01 Inversion Expected Editorial by evima

We focus on the Young diagram corresponding to $$S$$. The path of the Young diagram is defined as the path obtained by associating 0 and 1 with leftward and downward movements, respectively. This is denoted as $$Y(S)$$.

For example, the Young diagram corresponding to $$S=$$1101010 is as follows:

OOO
OOO
OO
O


Let $$(i,j)$$ denote the cell at the $$i$$-th row and $$j$$-th column.

Let $$f(S)$$ be the answer to the problem for $$S$$. It would be very nice if, for each cell $$(i,j)$$, there exists a weight $$w(i,j)$$ that depends only on $$i$$ and $$j$$ so that $$f(S)=\sum_{(i,j) \in Y(S)} w(i,j)$$. So, we assume that such $$w(i,j)$$ exists and consider what values it might take.

Let’s consider how $$Y(S)$$ changes by performing one operation on $$S$$.

We consider the cells that might be removed by performing one operation and call this set $$\partial Y(S)$$. As an example, $$\partial Y(S)$$ corresponding to $$S$$ mentioned above is shown with X in the diagram below.

OOX
OXX
XX
X


For $$(i,j) \in \partial Y(S)$$, there are $$i \times j$$ ways to perform an operation that removes this cell. Let $$A$$ be the area of $$Y(S)$$. $$w(i,j)$$ should satisfy the following equation:

$$\displaystyle \sum_{(i,j) \in \partial Y(S)} \frac{i \times j}{ A}w(i,j) = 1$$

Let $$g(i,j) = i \times j \times w(i,j)$$ and transform the equation. We want to satisfy the following:

$$\displaystyle \sum_{(i,j) \in \partial Y(S)} g(i,j) = A$$

Now, let’s consider $$\partial Y(S)$$. If we group the cells of $$Y(S)$$ by the value of $$i-j$$, exactly one cell in each group will be included in $$\partial Y(S)$$. In other words, if we collect the cells on the diagonal lines from top-left to bottom-right containing each cell in $$\partial Y(S)$$, those cells match $$Y(S)$$.

Thus, if $$g(i,j)=\min (i,j)$$, the above equation holds. Therefore, $$w(i,j)=1/\max(i,j)$$.

Once we understand this, we just need to sum $$w(i,j)$$ for all cells. This can be calculated in $$O(N)$$ using cumulative sums.

Therefore, this problem can be solved in $$O(N)$$.

Sample Implementation

posted:
last update: