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

## D - Unique Subsequence Editorial by evima

For convenience, let $$A_0=0,A_{N+1}=N+1$$ and we will count subsequences containing $$A_0$$ and $$A_{N+1}$$.

Assume that, for $$0 = x_0 <x_1< \cdots < x_k < x_{k+1}=N+1$$, there is a unique way to extract the subsequence $$s=(A_{x_0},A_{x_1},\cdots,A_{x_{k+1}})$$.

Then, it is necessary that the following holds for each $$0 \leq i \leq k$$:

• None of $$A_{x_i+1},A_{x_i+2},\cdots,A_{x_{i+1}-1}$$ equals $$A_{x_i}$$ or $$A_{x_{i+1}}$$.

Otherwise, there would be another way to extract the same subsequence.

On the other hand, when the above condition is satisfied, the extraction of $$s$$ is unique. We can show this from the fact that the greedy extraction of $$s$$ from the beginning of $$A$$ (making the used indices lexicographically smallest) will coincide with the greedy extraction of $$s$$ from the end of $$A$$ (making the used indices lexicographically largest).

Thus, we can find the answer by counting the sequences of indices $$x$$ satisfying the condition above. We can implement it with Binary Indexed Tree to achieve the time complexity of $$O(N \log N)$$.

posted:
last update: