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

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

Киану Ривз

Если строка хорошая, то ответом является сама. Иначе, ответ равен 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$$$).

Конфеты!!!

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

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

Т.к. все числа различны, то если существует вершина степени $$$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$$$. Тогда, существует корректная последовательность ходов с заданным кол-вом выборов, тогда и только тогда:

1. $$$j < i$$$

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

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

Переберем кол-во ходов, пусть оно равно $$$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{Утверждения 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}$$$

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