Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Коды были добавлены!

К некоторым задачи были добавлены челленджи(по большей части простые), которые возникли у нас при создании задач. Не стесняйтесь делиться решениями к ним и задавать любые вопросы в комментариях!

Киану Ривз

Если строка хорошая, то ответом является сама. Иначе, ответ равен 2, тогда можно вывести всю строку без последнего символа и последний символ отдельно. Сложность решения $$$O(n)$$$.

код

Числа на окружности

Будем считать, что массив отсортирован. Для начала заметим, что если $$$a_n \ge a_{n - 1} + a_{n - 2}$$$, то ответ — NO (т.к. $$$a_{n}$$$ будет не меньше суммы своих соседей). Мы утверждаем, что во всех остальных случаях ответ — YES. Одной из возможных конструкций (для уже отсортированного массива) является:

$$$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$$$

Легко заметить, что все числа кроме $$$a_n$$$ будут иметь хотя бы одного соседа не меньше их. Сложность решения $$$O(nlog(n))$$$.

код

$$$\textbf{Challenge}$$$

Решите задачу за $$$O(n)$$$ (считая, что все числа не превосходят $$$10^9$$$).

Конфеты!!!

Решение 1 (магия)

Решение 2 (дп)

Заметим, что задачу можно решить и методом динамического программирования.

Для каждого подотрезка $$$[s_l, s_{l+1}, \ldots, s_r]$$$, длина которого является целой неотрицательной степенью двойки, будем хранить пару чисел — цифру, которая останется последней и количество конфет, которое мы получим при игре на этом отрезке. Для отрезка длины $$$1$$$ эта пара равна $$$(s_l, 0)$$$.

Заметим, что существует не более $$$\log{n}$$$ различных длин отрезков, а отрезков каждой длины не более $$$n$$$. Таким образом, всего таких отрезков не более $$$n\log{n}$$$.

Теперь, решение очень похоже на построение sparse table. Будем теперь считать эти пары для отрезков в порядке возрастания их длин: сначала для отрезков длины $$$2$$$, потом $$$4$$$, и так далее. Оказывается, ответ для отрезка длины $$$2^k$$$ находится из ответов для меньших отрезков за $$$O(1)$$$! В самом деле, чтобы узнать пару (последняя цифра, количество конфет) для $$$[s_l, s_{l+1}, \ldots, s_{l + 2^k - 1}]$$$, достаточно знать, сколько конфет мы получили на отрезках $$$[s_l, s_{l+1}, \ldots, s_{l + 2^{k-1} - 1}]$$$, $$$[s_{l+2^{k-1}}, s_{l+2^{k-1} + 1}, \ldots, s_{l + 2^k - 1}]$$$, а также какие цифры $$$dig_1, dig_2$$$ остались последними на этих отрезках, тогда последняя цифра на нашем отрезке будет равна $$$(dig_1 + dig_2)\bmod 10$$$, причем если $$$dig_1 + dig_2 \ge 10$$$, то мы получаем еще одну конфету.

Таким образом, пересчет для каждого отрезка происходит за $$$O(1)$$$, что дает асимптотику $$$O(n\log{n})$$$.

код

Прибавление на дереве

Мы утверждаем, что ответ YES тогда и только когда не существует вершины со степенью 2. Ясно, что из этого следует решение к первой подзадаче $$$O(n)$$$.

Доказательство

Необходимость

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

Достаточность

Мы покажем, что некоторой последовательностью операций мы сможем прибавить $$$x$$$ на пути от некоторой вершины $$$v$$$ до листа $$$u$$$(не изменив значения других ребер). Если эта вершина лист, то утверждение очевидно. Иначе ее степень не меньше 3. Тогда, рассмотрим два листа $$$l_1$$$, $$$l_2$$$, таких что $$$l_1$$$, $$$l_2$$$, $$$u$$$ лежат в различных поддеревьях вершины $$$v$$$. Тогда сделаем следующие операции:

Прибавим $$$\frac{x}{2}$$$ на пути $$$u, l_1$$$.
Прибавим $$$\frac{x}{2}$$$ на пути $$$u, l_2$$$.
Прибавим $$$-\frac{x}{2}$$$ на пути $$$l_1, l_2$$$.

Таким образом, мы получили, что мы прибавили $$$x$$$ на пути $$$u, v$$$, что и требовалось.

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

solve($$$v$$$):

если у $$$v$$$ нет потомков, то просто выходим.

иначе, для каждого потомка $$$u$$$ находим лист в поддереве $$$u$$$ — обозначим его как $$$w$$$. Тогда, прибавим $$$a_{uv}$$$ на пути $$$vw$$$ и пересчитаем необходимые числа на ребрах на пути $$$vw$$$(т.е. для любого ребра $$$e$$$ на пути сделаем $$$a_e -= a_{uv}$$$), после чего вызываем solve($$$u$$$).

Итак, мы привели алгоритм, который для любой расстановки получает ее из нулевой. Таким образом, достаточность доказана.

Т.к. все числа различны, то если существует вершина степени $$$2$$$, то во второй подзадаче ответ NO. В противном случае построение также следует из доказательства. Действительно, если мы умеем прибавлять на пути до листа, то мы умеем прибавлять и на одном ребре. Для этого рассмотрим некоторое ребро $$$uv$$$ и допустим мы хотим прибавить $$$x$$$ на этом ребре. Найдем некоторый лист в поддереве вершины $$$u$$$, которое не содержит вершину $$$v$$$, обозначим его как $$$l$$$. Если $$$l = u$$$, то просто прибавим $$$x$$$ на пути $$$uv$$$. Иначе, прибавим $$$x$$$ на пути $$$vl$$$ и $$$-x$$$ на пути $$$ul$$$. Ясно, что в результате этих двух операций мы прибавим $$$x$$$ на ребре $$$uv$$$ и ничего не изменим на других ребрах. Тогда, просто прибавим на каждом ребре то число, которое мы хотим получить в конце.

Наконец, поговорим о реализации. Для того чтобы прибавлять на пути до листа нам достаточно уметь находить лист в некотором поддереве. Это можно делать каждый раз наивно за $$$O(n)$$$, тогда сложность решения $$$O(n^2)$$$. Если предпосчитать лист для каждого из поддеревьев и, например, подвесить вершину за любой из листов, то все операции можно выполнять за $$$O(1)$$$ и сложность решения составит $$$O(n)$$$, но это не требовалось.

$$$\textbf{Challenge}$$$

Решите задачу, если числа необязательно различны и четны, но операции все еще должны быть с целыми $$$x$$$(сейчас может случиться так, что существует последовательность операций с рациональными $$$x$$$, но не с целыми).

код для 1 подзадачи код для 2 подзадачи

Подсчитайте пары

Давайте немного преобразуем равенство. Т.к. $$$a_i - a_j \not\equiv 0$$$ $$$mod$$$ $$$p$$$, то равенство из условия равносильно:

$$$(a_i - a_j)(a_i + a_j)(a^2_{i} + a^2_{j}) \equiv (a_i - a_j)k \Leftrightarrow a^4_{i} - a^4_{j} \equiv ka_i - ka_j \Leftrightarrow a^4_{i} - ka_i \equiv a^4_{j} - ka_j$$$.

Таким образом, нам необходимо посчитать количество пар одинаковых чисел в массиве $$$b_i = (a^4_{i} - ka_i)$$$ $$$mod$$$ $$$p$$$. Это легко сделать, например, с помощью map. Сложность $$$O(n)$$$ или $$$O(nlog(n))$$$.

код

$$$\textbf{Challenge}$$$

Решите задачу, если среди чисел могут быть одинаковые.

Красота массива

Для решения исходной задачи научимся эффективно решать следующую подзадачу:

Для заданного $$$x$$$ сколько существует подпоследовательностей длины $$$k$$$, красота которых не меньше $$$x$$$? Если ответ для $$$x$$$ — $$$p_x$$$, то ответом на исходную задачу является $$$p_1 + p_2 + \ldots + p_{max(a)}$$$, где через $$$max(a)$$$ обозначен максимум в массиве $$$a$$$. Перейдем к решению подзадачи.

Считаем, что массив отсортирован. Заметим, что мы должны учесть подпоследовательность $$$p_1 < p_2, \ldots < p_k$$$, если и только если:

$$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$.

Будем решать задачу с помощью динамического программирования. Для начала медленное решение:

$$$dp[last][cnt]$$$ — кол-во подпоследовательностей длины $$$cnt$$$, которые заканчиваются в $$$a_{last}$$$. Перейти мы можем из состояний $$$last' < last, cnt' = cnt - 1$$$, таких что $$$a_{last} \ge a_{last'} + x$$$. Для того чтобы соптимизировать это заметим, что подходящие $$$last'$$$ образуют некоторый префикс массива. Тогда, зная нужные префиксы и префиксные суммы для предыдущего слоя, мы можем делать переходы за $$$O(1)$$$. Нужные префиксы могут быть подсчитаны с помощью двух указателей(т.к. очевидно, что длины префиксов не убывают). Таким образом, получили решение подзадачи за $$$O(nk)$$$.

Таким образом, мы уже умеем решать задачу за $$$O(max(a)nk)$$$. А теперь магия:

Если $$$x > \frac{max(a)}{k - 1}$$$, то $$$p_x = 0$$$. Действительно, если $$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$, то:

$$$a_n \ge a_{p_k} \ge a_{p_{k-1}} + x \ge a_{p_{k-2}} + 2x \ldots \ge a_{p_1} + (k - 1)x \ge (k - 1)x$$$. Откуда, $$$(k - 1)x \le a_n \Leftrightarrow x \le \frac{a_n}{k - 1}$$$.

Таким образом, имеет смысл запускать наше дп только для $$$x \le \frac{max(a)}{k - 1}$$$. Получили решение за $$$O(\frac{max(a)}{k - 1}nk) = O(max(a)n)$$$, т.к. $$$\frac{k}{k - 1} \le 2$$$.

код

$$$\textbf{Challenge}$$$

За сколько вы умеете решать задачу, если бы нужно было вывести ответ для всех $$$2 \le k \le n$$$?

Сделайте равными

Будем считать, что массив отсортирован. Пусть $$$x$$$ это итоговое число, которое мы получим. Тогда $$$x \ge a_n$$$. При этом, если обозначить через $$$bits[c]$$$ — кол-во 1 в двоичной записи числа $$$c$$$, то для получения $$$x$$$ из $$$a_i$$$ мы потратим не менее $$$bits[x - a_i]$$$ ходов(это следует из того факта, что минимальное кол-во степеней двойки, которые в сумме равняется числу соответствует его двоичной записи). Пусть $$$t = x - a_n$$$, тогда $$$x - a_i = t + a_n - a_i$$$. Таким образом мы пришли к равносильной задаче:

Минимизировать сумму $$$bits[t + a_n - a_1] + bits[t + a_n - a_2] + \ldots + bits[t + a_n - a_n]$$$, где $$$t$$$ некоторое неотрицательное целое число. Далее, для удобства, обозначим $$$b_i = a_n - a_i$$$.

Будем решать эту задачу с помощью дп — значение, которое мы хотим минизимировать это сумма $$$bits[t + b_i]$$$, взятая лишь до $$$(k - 1)$$$ — ого бита. Тогда, пусть мы хотим выставить $$$k$$$-ый бит. Попытаемся понять, какая информация нам важна из предыдущих значений. Представим, что мы складываем $$$t$$$ и $$$b_i$$$ в столбик. Понятно, что для того чтобы понять $$$k$$$-ый бит в числе $$$t + b_i$$$ нам достаточно знать $$$k$$$-ый бит в числе $$$t$$$ и был ли у нас перенос из прошлого разряда. Более того, зная эту информацию для прошлого бита, мы можем получить ее для следующего(перенос в новом бите будет тогда и только когда $$$bit_k[b_i]$$$ + $$$bit_k[t]$$$ + $$$(был ли перенос) \ge 2$$$). Но мы должны хранить информацию о переносах для всех чисел $$$t + b_i$$$ и на первый взгляд для одного бита мы получаем $$$2^n$$$ различных состояний дп. Для уменьшения кол-ва состояний заметим ключевой факт:

Пусть $$$t' = t$$$ $$$mod$$$ $$$2^k$$$, $$$c' = c$$$ $$$mod$$$ $$$2^k$$$. Тогда, в числе $$$t + c$$$ перенос в $$$k$$$-ый бит будет тогда и только когда $$$t' + c' \ge 2^k$$$. Действительно, перенос соответствует тому, что сумма "обрезанных" чисел не меньше $$$2^k$$$.

Пользуясь этим фактом мы понимаем, что если отсортировать числа $$$b_i' = b_i$$$ $$$mod$$$ $$$2^k$$$, то перенос в $$$k$$$-ый бит будет для некоторого суффикса $$$b_i'$$$. Таким образом, получили $$$n + 1$$$ различных состояний для одного бита, что уже приемлемо. Осталось понять каким образом делать переходы для всех чисел одновременно. Для этого заметим, что сами числа $$$b_i$$$ нам уже не важны, а нам важно был ли перенос и значение $$$k$$$-ого бита в $$$b_i$$$. Тогда, переход сводится к тому, чтобы посчитать кол-во чисел с $$$1$$$ или $$$0$$$ в $$$k$$$-ом бите на некотором отрезке в массиве отсортированном по $$$b_i'$$$. Это может быть сделано за $$$O(1)$$$, если предварительно посчитать префиксные суммы(для лучшего понимания ознакомьтесь с кодом). Таким образом, мы научились решать задачу за $$$nlog(n)F$$$, где $$$F$$$ это бит до которого мы будем писать дп. Осталось показать(или поверить :)), что нет смысла рассматривать достаточно большое $$$F$$$.

Не очень длинное доказательство

Таким образом, мы можем честно сказать, что сложность решения $$$O(nlog(n)log(max(a))$$$.

код

$$$\textbf{Challenge}$$$

Можете ли вы решить задачу за $$$O(nlog(max(a))$$$?

Задача от Red Pandы.

Будем считать(как и в 3 задачах до этого), что массив отсортирован. Также наша операция равносильна тому, что мы выбираем некоторое $$$1 \le i \le k$$$ и добавляем к $$$a_i$$$ $$$k - 1$$$, а от всех остальных $$$a_i$$$ отнимаем 1. Нам понадобится сделать несколько утверждений:

$$$\textbf{Утверждение 1}$$$

Разность $$$a_i - a_j$$$ $$$mod$$$ $$$k$$$ не меняется для любых $$$i, j$$$. Более того, за один ход $$$a_i$$$ сдвигается на $$$1$$$ $$$mod$$$ $$$k$$$.

$$$\textbf{Утверждение 2}$$$

Если мы сделали две различные последовательности ходов длины $$$i$$$ и $$$j$$$, где $$$i < k$$$, $$$j < k$$$, то полученные конфигурации совпадают тогда и только когда $$$i = j$$$ и совпадают(как мультимножества) номера выбранных цветов(т.е. порядки могут отличаться, но кол-во раз сколько мы выбрали каждый цвет должны совпадать).

Доказательство

Т.к. в обратную сторону утверждение очевидно, то будем считать, что полученные конфигурации равны и покажем совпадение мультимножеств. Обозначим кол-ва шариков, полученные для первой последовательности как $$$b_t$$$, а для второй как $$$c_t$$$. Т.к. $$$b_t \equiv b_t - i$$$ $$$mod$$$ $$$k$$$, $$$c_t \equiv a_t - j$$$ $$$mod$$$ $$$k$$$, то $$$i = j$$$. Тогда, заметим, что $$$b_t = a_t - i + k \cdot addB[t]$$$, где $$$addB[t]$$$ — сколько раз мы выбирали цвет $$$t$$$. Таким образом, мы получаем, что $$$addB[t] = addC[t]$$$ для любого $$$1 \le t \le k$$$, что и требовалось.

$$$\textbf{Утверждение 3}$$$

Если найдется такое $$$i$$$, что $$$a_{i + 1} < i$$$, то мы не сможем сделать больше $$$i - 1$$$ ходов.

Доказательство

Т.к. на каждом ходе мы выбираем один цвет, то за $$$i$$$ ходов найдется цвет среди $$$1 \ldots i + 1$$$, который мы не выбирали. Но тогда, кол-во шариков в нем будет меньше чем $$$i - i = 0$$$, что запрещено.

Назовем минимальный индекс $$$i$$$ из Утверждения 3(если он существует) критическим.

$$$\textbf{Утверждение 4}$$$

Пусть критический индекс равен $$$i$$$. Предположим, что мы решили сделать $$$j < k$$$ ходов и зафиксировали кол-во выборов каждого из шариков — $$$add[t]$$$. Ясно, что $$$add[t] \ge 0, add[1] + add[2] + \ldots add[k] = j$$$. Тогда, существует корректная последовательность ходов с заданным кол-вом выборов, тогда и только тогда:

$$$j < i$$$
Если $$$a_t < j$$$, то $$$add[t] > 0$$$.

Не очень длинное доказательство

Доказательство

Необходимость

Из Утверждения 3 $$$j < i$$$. Если $$$a_t < j$$$, то мы хотя бы один раз за $$$j$$$ ходов должны выбрать цвет $$$t$$$, т.е. условие 2 также необходимо.

Достаточность

Будем строить последовательность жадно: на очередном ходу будем выбирать такой цвет $$$t$$$, что $$$add[t] > 0$$$ и $$$a_t$$$ минимально(при выборе цвета мы меняем $$$a_i$$$ соответствующим способом и уменьшаем $$$add[t]$$$ на 1). Покажем, что эта последовательность корректна. Ясно, что она может быть некорректна только в том случае, если мы получим $$$a_p < 0$$$ в некоторый момент. Пусть $$$x$$$ — номер первого хода после которого мы получили, что найдется $$$a_p < 0$$$(мы будем считать что $$$p$$$ это номер в исходном отсортированном массиве $$$a$$$). Заметим, что т.к. $$$j < i < k$$$, то если мы хоть раз выбрали цвет, то кол-во шариков в нем не станет отрицательным(т.к. оно будет не меньше $$$k - j$$$). Таким образом(т.к. $$$x$$$ это первый ход), то $$$a_p = x - 1$$$. Значит, $$$a_p < j$$$, поэтому $$$add[p] > 0$$$. Таким образом, получается, что мы просто не успели выбрать цвет $$$p$$$, откуда мы получаем, что в исходном массиве было как минимум $$$x$$$ цветов $$$v$$$, таких что $$$a_v \le a_p$$$, т.е. $$$p \ge x + 1$$$. Значит, $$$a_{x+1} \le a_p = x - 1 < x$$$ — противоречие, т.к. $$$i$$$ это критический индекс. Значит, жадный алгоритм действительно работает и достаточность доказана.

Эти утверждения уже позволяют нам решать в случае существования критического индекса:

Переберем кол-во ходов, пусть оно равно $$$x$$$. Тогда, по утверждению 4 мы знаем, что если $$$a_p < x$$$, то $$$add[p] > 0$$$, иначе на $$$add[p]$$$ нет ограничений(за исключением очевидного $$$add[p] \ge 0$$$). Итак, мы приходим к тому, что необходимо посчитать кол-во решений уравнения:

$$$add[1] + \ldots + add[k] = x$$$, где фиксированные $$$num$$$ чисел должны быть положительны. По утверждению 2 и 4 каждому корректному набору из $$$add$$$ можно поставить в соответствие ровно одну итоговую конфигурацию, что нам и нужно посчитать.

Это известная задача(шарики и перегородки), ответ на нее равен $$$C^{x - num + k - 1}_{k - 1}$$$

Просуммировав ответ для всех подходящих $$$x$$$ получим ответ.

Будем называть конфигурацию $$$\textbf{критической}$$$, если в ней есть критический элемент (другими словами, если для какого-то $$$i < k-1$$$ по крайней мере $$$i+2$$$ элемента конфигурации не превосходят $$$i$$$).

Для решения задачи, когда критического индекса нет нам поможет:

$$$\textbf{Утверждение 5}$$$

Если конфигурация не критическая, то конфигурация $$$b_i$$$ достижима тогда и только тогда, когда, $$$a_i - b_i \equiv a_j - b_j$$$ $$$mod$$$ $$$k$$$ и $$$b_i \ge 0$$$, $$$a_1 + \ldots a_k = b_1 + \ldots b_k$$$.

Длинное доказательство

Доказательство

То, что эти условия необходимы, очевидно с $$$\textbf{утверждения 1}$$$. Покажем, что если конфигурация $$$b_i$$$ удовлетворяет таким условиям, то мы можем ее получить.

Для начала, будем действовать с конца. "Обратная операция" в нашем случае состоит в том, чтобы взять $$$b_i \ge k-1$$$, отнять от него $$$k-1$$$ и прибавить к всем остальным $$$b_j$$$ единицу. Если мы сможем получить новую конфигурацию, то из нее за одну операцию мы сможем получить и конфигурацию $$$b$$$.

Теперь попробуем сделать так, чтобы все $$$b_i$$$ находились на каком-то отрезке $$$[S, S + k - 1]$$$. Пусть в данный момент наибольшее число — $$$b_{max}$$$, а наименьшее — $$$b_{min}$$$. Если $$$b_{max} \ge b_{min} + k$$$, то применим к $$$b_{max}$$$ обратную операцию — все числа станут не менее $$$b_{min} + 1$$$. Таким образом, каждое применение обратной операции в случае, если разница максимума и минимума превышает $$$k-1$$$, увеличивает минимальное значение массива по крайней мере на единицу. Поскольку минимальный элемент не превышает суммы всех элементов, которая является постоянной, этот процесс будет конечным. Таким образом, можно считать, что по выполнению череды обратных операций все $$$b_i$$$ находятся на каком-то отрезке $$$[S, S + k - 1]$$$.

Так как критического индекса нет, то $$$a_i \ge i-1$$$ для всех $$$i$$$. Тогда прибавим $$$k-1$$$ к $$$a_1$$$ и отнимем $$$1$$$ от остальных $$$a_j$$$. Покажем, что полученная конфигурация также не критическая. Предположим, что она критическая: тогда для какого-то $$$i<k-1$$$ в новой конфигурации по крайней мере $$$i+2$$$ чисел не превосходят $$$i$$$. Для $$$i = k-2$$$ это неверно, ведь $$$a_1 /ge k-1$$$. Для $$$i<k-2$$$ это неверно, так как до этого не более $$$i+2$$$ чисел не превышали $$$i+1$$$, и если эти числа вообще были, то среди них было $$$a_1$$$. После выполнения операции только эти числа могли оказаться не больше $$$i$$$, но $$$a_1$$$ оказалось больше $$$i$$$ и потому выпадает из списка кандидатов. Поэтому чисел, не превышающих $$$i$$$, не более $$$i+1$$$.

Заметим, что остатки всех чисел уменьшились на $$$1$$$ по модулю $$$k$$$. Поскольку мы показали, что операция такого $$$\textit{сдвига}$$$ оставляет некритическую конфигурацию некритической, можем сделать несколько таких сдвигов, пока не получим $$$a_1 \equiv b_1 \bmod k$$$. Отсюда будет следовать и $$$a_i \equiv b_i$$$ $$$mod$$$ $$$k$$$ для всех $$$i$$$.

Теперь покажем, как мы можем провернуть такую операцию: если конфигурация не критическая и $$$a_{max} > a_{min}+k$$$, перекинуть $$$k$$$ с $$$a_{max}$$$ в $$$a_{min}$$$. Для простоты все еще считаем, что массив отсортирован, то есть что $$$a_i \ge i-1$$$ и что $$$a_k > a_1 + k$$$. Тогда сделаем последовательность операций: прибавим к $$$a_i$$$ $$$k-1$$$ и отнимем от остальных $$$a_j$$$ по единице по очереди для $$$i = 1, \ldots, k-1$$$. Сейчас будем иметь конфигурацию: $$$a_1 + 1, a_2 + 1, \ldots, a_{k-1}+1, a_k - (k-1)$$$. Теперь опять прибавим $$$k-1$$$ к $$$a_1$$$ и отнимем по единице от остальных, получим $$$a_1+k, a_2, a_3, \ldots, a_{k-1}, a_k-k$$$. Можно легко понять, что она не критическая. Действительно, для каждого $$$i<k-1$$$ не более $$$i+1$$$ числа в старой конфигурации не превосходили $$$i$$$. Заметим, что $$$a_k$$$ не входил в их число. $$$k-2$$$ числа массива не изменились, $$$a_1+k$$$ точно не входит в их число сейчас, а $$$a_k-k>a_1$$$, поэтому количество чисел, не превосходящих $$$i$$$, не могло увеличиться.

Таким образом, мы можем перекидывать $$$k$$$ от максимального элемента к минимальному, если разность между ними составляет не менее $$$k+1$$$, и конфигурация будет оставаться не критической.

Теперь, будем так делать, пока возможно. Этот процесс должен прекратиться, так как сумма квадратов элементов конфигурации с каждой операцией уменьшается: $$$a_1^2 + a_k^2 > (a_1+k)^2 + (a_k-k)^2 \iff 2k(a_k-a_1) > 2k^2 \iff a_k - a_1 > k$$$, что верно по предположению. Таким образом, в какой-то момент мы получим конфигурацию, умещающуюся на отрезке $$$[T, T+k]$$$.

Заметим, что для новых $$$a_i$$$ и $$$b_i$$$ выполняется $$$a_i \equiv b_i \bmod k$$$, $$$S\le b_i\le S + k-1$$$, $$$T\le a_i \le T + k$$$, $$$a_1 + a_2 + \ldots a_k = b_1 + b_2 + \ldots b_k$$$. Покажем, что из этих условий следует $$$a_i = b_i$$$ для всех $$$i$$$. Действительно, в случае $$$S\le T$$$ мы получаем $$$b_i \le S+k-1 \le T+k-1 \le a_i+k-1$$$, но $$$a_i \equiv b_i$$$ $$$mod$$$ $$$k$$$, поэтому $$$b_i \le a_i$$$ для каждого $$$i$$$. Вместе с условием на равность сумм, это дает $$$a_i = b_i$$$ для всех $$$i$$$. Аналогично, если $$$S > T$$$, $$$a_i \le T+k \le S+k-1 \le b_i + k-1$$$, откуда аналогично $$$a_i = b_i$$$ для всех $$$i$$$.

Таким образом, операциями с $$$a$$$ и обратными операциями с $$$b$$$ мы получили одинаковую конфигурацию. Следовательно, с $$$a$$$ можно получить $$$b$$$, утверждение доказано.

Теперь покажем, как посчитать число конфигураций, удовлетворяющих условиям $$$\textbf{Утверждения 5}$$$.

$$$b_1, b_2, \ldots, b_k$$$ должны давать остатки $$$(a_1+t) \bmod k, (a_2+t) \bmod k, \ldots, (a_k+t) \bmod k$$$ для какого-то $$$t$$$. Конфигурации с такими остатками получаются следующим образом: оставшиеся $$$a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k$$$ делятся на группы по $$$k$$$ и распределяются по $$$k$$$ элементам произвольным образом. Таким образом, для заданного $$$t$$$ количество конфигураций будет равно $$$C^{\frac{a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k}{k} + k-1}_{k-1}$$$. Сумма $$$a_1 + a_2 + \ldots + a_k - (a_1+t)\bmod k - (a_2+t)\bmod k - \ldots - (a_k+t) \bmod k$$$ может пересчитываться для $$$t = 0, 1, \ldots , k-1$$$ за $$$O(1)$$$, если предподсчитать количество каждых остатков среди $$$a_1, a_2, \ldots, a_k$$$.

Таким образом, итоговая сложность для каждого из случаев $$$O(n + k)$$$.

код

$$$\textbf{Challenge}$$$

Найти все опечатки в доказательствах.

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

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

Киану Ривз

Числа на окружности

Конфеты!!!

Прибавление на дереве

Необходимость

Достаточность

Подсчитайте пары

Красота массива

Сделайте равными