Исследование улик

Автор задачи: Александр Гордеев, разработчик: Даниил Орешников

По условию был дан массив, и требовалось для некоторых элементов найти, где остановится указатель, стартующий с них. Указатель двигался влево на числа $$$\leqslant$$$ текущего, но мог сделать не более $$$k$$$ перемещений на равное число.

Первую подгруппу можно было решить любым перебором. В подгруппах с третьей по четвертую работала аккуратно написанная симуляция процесса. Для простоты можно было найти ответ для каждого элемента массива, после чего вывести ответы для тех элементах, которые запрашивались в тесте.

В пятой подгруппе запрещены перемещения между равными числами, таким образом указатель всегда перемещается на строго меньшее число. В таком случае ответ легко найти. Посмотрим на $$$a_i$$$. Если $$$a_{i-1} < a_i$$$, то $$$\mathtt{answer}[i] = \mathtt{answer}[i - 1]$$$, так как указатель смещается на $$$1$$$ влево, а дальше повторяет тот же путь. Если же $$$a_{i-1} \geqslant a_i$$$, то $$$\mathtt{answer}[i] = i$$$, так как указатель вообще не двигается.

Чтобы получить полное решение, улучшим решение предыдущей подгруппы. Будем поддерживать количество шагов между одинаковыми числами на пути от $$$i$$$ до $$$\mathtt{answer}[i]$$$. Основная идея такая же, как и была раньше. Однако, если $$$a_{i-1} = a_i$$$, указатель по пути сделает на один шаг между равными числами больше, чем если бы он стартовал с $$$a_{i-1}$$$. Если с учетом этого количество шагов между равными числами стало больше $$$k$$$, начнем с ответа $$$\mathtt{answer}[i] = \mathtt{answer}[i - 1]$$$, и будем увеличивать его, пока не «избавимся» от лишнего последнего шага по одинаковым числами. Получаем решение за время $$$\mathcal{O}(n)$$$ методом двух указателей.