Продолжаю свой виртуальный тур по давно минувшим раундам, в которых я не учавствовал. Моя сегодняшняя проблема это 1355D - Игра с массивом, решение которой я просто угадал 106629350. В ней не сложно понять как нужно строить массив так, что бы Петя всегда выигрывал при $$$S \geqslant 2N$$$. Доказать же, что это невозможно при $$$S < 2N$$$ гораздо сложнее. На мой взгляд доказательство, предоставленное DishonoredRighteous заслуживает подробного изучения.

Изначально у нас имеется массив $$$A$$$, состоящий из $$$N$$$ элементов. Этот массив дублируется $$$2K$$$ раз

и из него строится массив префиксных сумм $$$B$$$ размером $$$2KN$$$. В нем $$$b_0 = 0$$$ и $$$b_j = b_{j - 1} + a_j$$$ для любого $$$j > 0$$$. То есть $$$b_1 = a_1$$$, $$$b_2 = a_1 + a_2$$$, $$$b_3 = a_1 + a_2 + a_3$$$ и так далее.

Очевидно, что в таком массиве префиксных сумм всегда выполняется равенство $$$b_{j + N} = b_j + S$$$, a последний элемент массива $$$b_{2KN} = 2KS$$$. Заметьте также, что каждый элемент массива $$$B$$$ уникален потому, что все элементы $$$A$$$ положительны.

Теперь создадим еще один массив, уже третий, назовем его $$$C$$$, и выпишем в нем все числа от $$$1$$$ до $$$2KS$$$. Разобьем его на группы размером $$$K$$$, всего таких групп получается $$$2S$$$, и раскрасим их попеременно зеленым и синим цветом.

Соединим пунктирными линиями все пары чисел вида $$$X$$$ и $$$X + K$$$ у которых $$$X$$$ находится в зеленой группе. Таким образом у нас получилось $$$KS$$$ вилок между одним зеленым числом и одним синим числом.

Если в массиве $$$B$$$ есть хотя бы одна пара таких чисел, соединенных вилкой, то это означает, что разность префиксных сумм между ними, равна $$$K$$$. А это, в свою очередь, означает, что в зацикленном $$$A$$$ есть диапазон индексов $$$l$$$, $$$r$$$ такой, что $$$\sum{a_j[l \leqslant j < r]} = K$$$, причем ширина этого диапазона не превышает $$$N$$$ потому, что $$$K \leqslant S$$$ и сумма $$$N$$$ элементов изначального массива $$$A$$$ равняется $$$S$$$.

Что мы теперь имеем? В массиве $$$B$$$ у нас есть $$$2KN$$$ уникальных чисел в диапазоне от $$$1$$$ до $$$2KS$$$ включительно. В массиве $$$C$$$ у нас имеется $$$KS$$$ пар несовместимых префиксных сумм. Если $$$S < 2N$$$, то получается, что $$$KS < 2KN$$$, а это означает, что для всех чисел из массива $$$B$$$ просто не хватает свободных мест в массиве $$$C$$$. Отсюда вытекает, что если взять каждое число из $$$B$$$ и вычеркнуть его из массива $$$C$$$, то среди вычеркнутых чисел обязательно найдется пара, соединенная вилкой ($$$X$$$, $$$X + K$$$), что ведет нас к заключению о том, что в зацикленном массиве $$$A$$$ обязательно найдется непрерывный диапазон чисел с суммой $$$K$$$.

Весь трюк доказательства заключается в том, что оперируя только изначальным массивом $$$A$$$ размера $$$N$$$, доказать ничего не получается потому, что $$$K$$$ не обязательно делит $$$S$$$. Зато все прекрасно доказывается через принцип Дирихле при переходе к диапазону значений сумм кратному одновременно $$$S$$$ и $$$2K$$$.

Вчера решил задачу 1360G - A/B Matrix следующим образом 106287665. Хоть мое решение и компактно в реализации, его суть не очевидна и выйти на него было не просто.

Посмотрел в Editorial в надежде, что авторское решение будет проще. Stepavly предлагает подобрать смещение $$$d$$$ такое, что бы выполнялось отношение

Давайте разберемся почему вообще оно должно работать.

Первый важный факт, на который мы будем опираться, установлен равенством

смысл которого обьясняется в эдиториале.

Из него мы сразу же можем заметить, что

То есть, в качестве $$$d$$$ мы всегда можем выбрать $$$a$$$ и заполнить матрицу подобно тому, как это указано на картинке снизу

Каково же количество ячеек, заполненых единицами, или, альтернативно, суммарная площадь покрытая разноцветными прямоугольниками? Она равняется $$$n \cdot a$$$. И тут нам пригождается наше уравнение $$$n \cdot a = m \cdot b$$$ потому, что получается, что всеми этими единицами можно заполнить прямоугольник высотой $$$b$$$ и шириной $$$m$$$ как указано на следующей картинке.

Почему же наше заполнение обязательно является однородным? Доказать то, что высота каждой колонки является одинаковой можно по индукции: Пусть после добавления $$$l$$$ кирпичиков у нас имеется какое-то количество полностью заполненых строк $$$\left\lfloor\frac{l \cdot a}{m}\right\rfloor$$$ и последняя строка, в левой части которой находится какое-то количество $$$l \cdot a \bmod m$$$ заполненых ячеек. На следующей итерации мы добавляем кирпичик точно в конец незаполненой строки, потому, что его начало отстоит ровно на $$$a$$$ позиций от начала предыдущего кирпичика, а следовательно интересующее нас свойство снова сохраняется. Ну и разумеется если $$$l=n$$$, мы имеем $$$n \cdot a \bmod m = 0$$$. То есть в каждой колонке действительно будет ровно $$$b$$$ единиц.

1463A - Dungeon

Очередная простая задача над которой я слишком долго думал. Опишу здесь ход своих мыслей: довольно витиеватый, нужно заметить.

Начнем с того, что перефразируем задачу:

У нас имеется три колонки высотой $$$a$$$, $$$b$$$ и $$$c$$$. На каждом ходу, номер которого не делится на $$$7$$$ без остатка, мы срезаем любую из колонок сверху на единицу. Если же номер хода делится на $$$7$$$, то мы срезаем единицу в нижней части каждой из колонок. Ни одна из них не должна быть пустой перед проведением такой операции.

Наша задача: свести в ноль все колонки на ходе кратном $$$7$$$.

Разобьем весь процесс на раунды. В каждом раунде есть $$$6$$$ ходов, когда мы срезаем единицу, и $$$1$$$ ход, когда мы срезаем тройку (супершот). В сумме за раунд мы удаляем $$$9$$$ единиц. Значит общее количество раундов $$$k = \frac{a + b + c}{9}$$$

Высота самой низкой колонки $$$h = \min(a, b, c)$$$. Все три колонки содержат $$$3h$$$ единиц вплоть до уровня $$$h$$$. Поверх этого уровня находятся неудобные остатки $$$d = a + b + c - 3h$$$, которые нужно как-то удалить за количество ходов не превышающее $$$h$$$. При этом понятно, что $$$3$$$ делит $$$d$$$ потому, что $$$3$$$ делит $$$a + b + c$$$.

В каждом раунде мы сможем удалять только $$$6$$$ единиц из этих остатков. Значит, для почти полного удаления остатков нам нужно $$$\left\lfloor\frac{d}{6}\right\rfloor$$$ раундов.

Проведем $$$x = min(h, \left\lfloor\frac{d}{6}\right\rfloor)$$$ раундов.

В случае, когда супершоты съедают все колонки до того как мы избавимся от остатков, имеем $$$h < \left\lfloor\frac{d}{6}\right\rfloor$$$ и, соответсвтенно, $$$x = h$$$. Далее эквивалентными преобразованиями получаем

Последнее неравенство означает, что если после $$$x$$$ раундов количество остатков превышает $$$d \bmod 6$$$, которое может быть только 0 или 3, то супершоты уничтожают самую маленькую колонку до того, как нам удастся убрать остатки, а значит наш ответ NO.

В противном случае должно выполняться равенство

Здеь возможны две ситуации

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

Вторая ситуация, когда

означает, что все колонки оказались одинаковой высоты. Благодаря инварианту о делимости на $$$9$$$ после каждого раунда, мы знаем, что все эти три колонки могут быть успешно уничтожены.

Таким образом решение существует, если $$$a + b + c$$$ делится на $$$9$$$ и если $$$d - \min(h, \left\lfloor\frac{d}{6}\right\rfloor) \leqslant 3$$$.

1463B - Find The Array

Решение из эдиториала как-то не пришло мне в голову. Вместо этого я использовал массив $$$b$$$ такой, что

что по-сути означает

Если для любого $$$k$$$ выполняется $$$a_k - b_k \leqslant \frac{a}{2}$$$, то тогда мы можем сказать, что

Для нашего $$$b_k$$$ это действительно так: Пусть в двоичной записи $$$a_k = 1\text{xxxx}$$$, тогда $$$b_k = 10000$$$, а $$$\frac{a_k}{2} = 01\text{xxx}$$$, т.е. для любого $$$b_k$$$ мы имеем

1463D - Pairs

Посчитаем, какое минимальное количество элементов $$$b_k$$$ должно быть младшим в паре и назовем его $$$x_\min$$$. Также посчитаем минимальное количество элементов $$$b_k$$$, которые должны быть старшими в паре и назовем его $$$y_\min$$$. Тогда очевидно, что $$$x_\max = n - y_\min$$$. Значит ответом будет $$$x_\max - x_\min + 1$$$.

Остается теперь только вычислить $$$x_\min$$$ и $$$y_\min$$$. Делать это мы будем следующим образом:

В массиве $$$A = [1 .. 2n]$$$, нумеруемом начиная с 1, пометим все позиции занятые $$$b_k$$$. Далее применим следующее dp:

count_A[0] = 0; // Количество занятых позиций, где A[k] == 1.
vacant_count[0] = 0; // Количество незанятых позиций (A[k] == 0), не связаных ни в какой паре.
x_min[0] = 0;
// Далее в цикле по k <-- 1 .. n:
count_A[k] = count_A[k - 1] + A[k];
// Элемент становится младшим в паре только если он не может стать старшим
x_min[k] = x_min[k - 1] + (A[k] && vacant_count[k - 1] == 0 ? 1 : 0);
// k - count_A[k] - количество незанятых позиций.
// count_A[k] - min_x[k] - количество занятых позиций, являющихся старшими в паре
vacant_count[k] = (k - count_A[k]) - (count_A[k] - x_min[k]);

Аналогичным образом мы можем рассчитать $$$y_\min$$$.