Распределение пряности

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

Первые подгруппы расчитаны на частные решения.

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

В четвертой подгруппе работает решение через динамическое программирование, но мы сразу приведем решение для четвертой и пятой подгрупп, подводящее к полному решению. Упорядочим $$$a_i$$$ по неубыванию и для каждого направления $$$a_i$$$ найдем такое минимальное $$$j_i > i$$$, что $$$a_{j_i} - a_i > k$$$. Тогда все направления с $$$i$$$ по $$$j_i - 1$$$ обязаны быть выданы разным студентам.

Утверждается, что ответ в таком случае равен $$$\max\limits_{i=1}^n j_i - i$$$, то есть максимальной длине такого отрезка. Опять же, оценка понятна: если в каждом таком отрезке все направления достались разным студентам, то количество студентов не меньше длины максимального из отрезков. Пример же строится жадно или конструктивно. Например, если мы определили, что студентов в ответе будет $$$m$$$, достаточно выдать направление $$$a_i$$$ студенту с номером $$$i \bmod m + 1$$$. Тогда любые два направления у одного студента отличаются хотя бы на $$$a_{i+m} - a_i$$$, что больше $$$k$$$ по нашему выбору $$$m$$$.

В четвертой подгруппе для вычисления такого $$$m$$$ можно было просто суммировать $$$\mathtt{cnt}[x] + \mathtt{cnt}[x + 1] + \mathtt{cnt}[x + 2]$$$, перебирая все возможные $$$x$$$ (где $$$\mathtt{cnt}$$$ — количество вхождений числа в последовательность $$$a_i$$$). В пятой же было достаточно для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ находить $$$j_i$$$ за время $$$\mathcal{O}(n)$$$.

Полное решение же отличается только применением методов двух указателей: если $$$i_1 \le i_2$$$, то и $$$j_{i_1} \le j_{i_2}$$$ по логике задачи. Тогда можно двумя указателями найти $$$j_i$$$ для каждого $$$i$$$ в сумме за $$$\mathcal{O}(n)$$$ времени.