Official

F - Overlaps Editorial by evima


Let us correspond the \(2N\) real numbers generated throughout the process to a permutation of \((1,2,\cdots,2N)\) while maintaining the magnitude relation. Then, all permutations occur with equal probability. Now we have a problem with a discrete setting.

For each \(i=1,2,\cdots,2N\), let us decide one by one whether \(i\) is used as the right end or the left end of an interval. If we decide to use \(i\) as the right end of an interval, there is a degree of freedom for the corresponding left end. There will be exactly \(N\) right ends. Let \(x_1,x_2,\cdots,x_N\) be the number of candidates for the corresponding left ends.

Deciding whether each \(i\) is used as a right end or a left end will determine \(x\). Here, the requirement of no overlap of \(K+1\) or more stickers means every element of \(x\) must be at most \(K\). Additionally, from the way the number of candidates for the left end changes, \(x_{i+1} \geq x_i-1\) must hold. Furthermore, \(x_N=1\) must hold.

On the other hand, for an \(x\) that satisfies all of these necessary conditions, there is a unique way to decide whether each \(i\) is a right end or a left end that corresponds to \(x\).

Thus, we are to solve the following problem.

  • Find the sum of \(\prod_{1 \leq i \leq N} x_i\) over all integer sequences \(x_1,x_2,\cdots,x_N\) that satisfy the conditions below.
    • \(1 \leq x_i \leq K\)
    • \(x_{i+1} \geq x_i-1\)
    • \(x_N=1\)

Notice the second condition and use the inclusion-exclusion principle to do the count. Assume that we have fixed \(i\)’s that do not satisfy this condition. By paying attention to repetitions of such \(i\)’s, we can decompose the sequence into several blocks. The number of ways to decide the values in each block is found as the following.

  • The sum of \(\prod_{1 \leq i \leq m} y_i\) over all sequences of length \(m\) (\(1 \leq m \leq N\)), \(K \geq y_1 > y_2 > \cdots > y_m \geq 1\), that satisfy \(y_j-2 \geq y_{j+1}\) (\(1 \leq j \leq m-1\)).

We can find it with divide-and-conquer & FFT. Specifically, we should write a function that finds the answer when the range of \(y\) is between \(l\) and \(r\) and call it recursively. Here, the function needs to return \(2 \times 2\) values, classified by whether \(l\) and \(r\) are used.

Now that we know about deciding values within each block, we just need to do DP using it. This DP can be made fast by divide-and-conquer & FFT or finding inv of polynomials. Take care of the special restriction on the final block that it must use \(1\).

The complexity will be \(O(N \log^2N + K \log^2K)\) or \(O(N \log N + K \log^2K)\).

Sample Submission (C++)

P.S. It is possible to solve this problem in \(O(N \log N)\) time. For a fixed \(K\), the answers for \(N=0,1,2,\cdots,\lceil K/2 \rceil\) are \(1,1,3,15,105\cdots\). If we consider the denominator of generating function of this sequence, it coincides with this OEIS sequence. We can prove it by induction. So we can reconstruct the sequence of answers for larger \(N\)s. (tourist’s submission inspired me. Thanks!)

Sample Submission(c++)

posted:
last update: