Official

E - Sort A[i]-i Editorial by evima


Associate the sequence \(a\) with a path on a grid. Let’s consider the condition under which (the \(k\)-th element of \(f(a)\)) \(> h\).

If we draw a diagonal line on the grid, the path will be OK if it goes right \(k\) or more times above that line.

Here is a lemma needed for the solution.

Lemma: Consider an \(N \times N\) grid and a path from \((0,0)\) to \((N,N)\). Let \(c(N,k)\) be the number of paths that go right \(k\) times above the diagonal line from \((0,0)\) to \((N,N)\). Then, \(c(N,0)=c(N,1)=\cdots=c(N,N)\).

Although we can create a clever bijection in a top-down manner, here we prove it using generating functions.

Consider the number of paths that start from \((0,0)\) and first touch the diagonal line at \((n,n)\). The generating function corresponding to the paths that pass below the diagonal line is \((1-\sqrt{1-4x})/2\), which can be seen from the generating function of the Catalan numbers. The same applies to the upper side. Here, by associating a variable \(y\) with the number of times the path goes right above the diagonal line, let’s make it a two-variable polynomial. Then, we have \((1-\sqrt{1-4x})/2\) for the lower side of the diagonal line, and \((1-\sqrt{1-4xy})/2\) for the upper side. Based on this, if we calculate \(f(x,y)=\sum c(N,k) x^N y^k\), we get:

\[ \begin{aligned} f(x,y) &= \frac{1}{1-(1-\sqrt{1-4x})/2- (1-\sqrt{1-4xy})/2} \\ &= \frac{2}{\sqrt{1-4x}+\sqrt{1-4xy}} \\ &= \frac{2(-\sqrt{1-4x}+\sqrt{1-4xy})}{-(1-4x)+(1-4xy)} \\ &= \frac{1}{1-y}\left(\frac{1-\sqrt{1-4x}}{2x} +\frac{1-\sqrt{1-4xy}}{2x} \right)\\ \end{aligned} \]

If we consider \([x^N]f(x,y)\) from this, we can see that the coefficients of \(y^0,y^1,\cdots,y^N\) are all equal, completing the proof.

Let’s apply this fact to the original problem.

We want to consider how many times the path from \((0,0)\) to \((N,M)\) went right above the line \(y=x+h\).

Consider the case \(0 \leq h \leq M-N\). Fix the points \((p,p+h)\) and \((q,q+h)\) where the path first and last touches the line \(y=x+h\). From the lemma, we know that the number of moves passing above the diagonal line between \(p\) and \(q\) is constant in the range \([0,q-p]\).

After passing through \((q,q+h)\), the path always moves above the diagonal line, so in the end, the number of times it passes above the diagonal line is evenly distributed in the range \([n-q,n-p]\).

Once we fix \(p\) and \(q\), we add \(v(p,q)\) (the number of ways to first touch the diagonal line at \(p\) and last touch it at \(q\), without going above the diagonal line between \(p\) and \(q\)) to \(ans[n-q,n-p]\). If we use the concept of cumulative sum here and let \(dif\) represent the differences between two adjacent terms of \(ans\), the above operation becomes \(dif[n-q]\mathrel{+}=v(p,q), dif[n-p+1]\mathrel{-}=v(p,q)\).

If we move \(p\) while keeping \(q\) fixed, we want to find \(\sum_{0 \leq p \leq q} v(p,q)\), but this is simply the number of paths that do not cross the diagonal line until \((q,q+h)\) and do not touch the diagonal line afterward. This can be written using products of binomial coefficients (or the sum of a constant number of them) using the same method as the calculation of Catalan numbers (the reflection method).

Let’s try moving also \(h\). Then, the desired sum will have the following form (or something slightly shifted in index):

\[ \sum_{0 \leq h \leq M-N} {2q+h \choose q} \times {N+M-h-2q \choose N-q} \]

The goal is to find this for all \(q\). This can be done in \(O(N+M)\) in total by moving \(q\) as \(0 \to N\). (The change in value when \(q\) is increased by \(1\) can be processed by a constant number of calculations.)

We have been considering \(q\), but we can do exactly the same for \(p\). This allows us to handle the case \(0 \leq h \leq M-N\).

The case \(M-N<h\) can be handled more simply. Similarly to the above, let \(p\) and \(q\) be the first and last positions where the path crosses the line \(y=x+h\). This time, we just need to count the paths classified by \(q-p\). If we fix \(q-p\) and move \(h\), the numbers will be in the form of the sum or difference of binomial coefficients. These binomial coefficients can be combined to calculate the desired value in \(O(1)\) for each \(q-p\).

The case \(h<0\) can be handled exactly the same way.

Therefore, everything can be calculated in \(O(N+M)\) time.

Sample Implementation

posted:
last update: