conqueror_of_Um_nik's blog

Is this problem new?
By conqueror_of_Um_nik, history, 6 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it