Is this problem new?

Revision en1, by conqueror_of_Um_nik, 2025-11-08 14:59:40

You are given a permutation $$$p$$$ of $$$[1, 2, \ldots, n]$$$. It is guaranteed that $$$n$$$ is even.

You can perform the following operation on it:

  • Select a subsequence (say $$$t$$$) of length $$$2k$$$ (where $$$k$$$ does not need to be the same across operations) such that either
$$$ \max(t_1, t_2, \ldots, t_k) \lt \min(t_{k+1}, t_{k+2}, \ldots, t_{2k}), $$$
$$$ or $$$
$$$ \min(t_1, t_2, \ldots, t_k) \gt \max(t_{k+1}, t_{k+2}, \ldots, t_{2k}). $$$
  • Then, remove every element of $$$t$$$ from $$$p$$$. You want to make $$$p$$$ empty using the minimum number of operations.

Is this problem new, if not could you kindly share the link?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English conqueror_of_Um_nik 2025-11-08 14:59:40 690 Initial revision (published)