Блог пользователя conqueror_of_Um_nik

Is this problem new?
Автор conqueror_of_Um_nik, история, 6 месяцев назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится