Editorial for Yet Another Contest 9 P1 - Permutation Cutting - Olympiads Online Judge

Editorial for Yet Another Contest 9 P1 - Permutation Cutting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

If there is an index $i$ $i$ with $s_i + 1 \ne s_{i+1}$ $s_{i} + 1 \neq s_{i + 1}$ , then these two elements must clearly belong to different subsequences. On the other hand, it always suffices to cut the permutation in between these indexes, since the subsequences formed will each be contiguous subsequences of $t$ $t$ , and thus can be rearranged to form $t$ $t$ . So the answer is $1$ $1$ plus the number of such indexes.

Time complexity: $\mathcal{O}(N)$ $O (N)$

Subtask 2

With the same logic, the answer is $1$ $1$ plus the number of indices where $(s_i, s_{i+1})$ $(s_{i}, s_{i + 1})$ is not a contiguous subsequence of $t$ $t$ . This can be calculated fast by storing the adjacent pairs of elements of $t$ $t$ in a set, or storing the index of each element in $t$ $t$ .

Time complexity: $\mathcal{O}(N)$ $O (N)$ or $\mathcal{O}(N\log N)$ $O (N \log N)$

Comments

There are no comments at the moment.