Educational Codeforces Round 100
Разница между ru3 и ru4, 4 символ(ов) изменены
[problem:1463A]↵

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

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

У нас имеется три колонки высотой $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$.↵
Далее эквивалентными преобразованиями получаем↵
$$↵
6x < 6 \left\lfloor\frac{d}{6}\right\rfloor↵
$$↵
$$↵
d - 6\left\lfloor\frac{d}{6}\right\rfloor < d - 6x↵
$$↵
$$↵
d \bmod 6 < d - 6x↵
$$↵
Последнее неравенство означает, что↵
если после $x$ раундов количество остатков превышает $d \bmod 6$, которое может быть только 0 или 3, то супершоты уничтожают самую маленькую колонку до того, как нам удастся убрать остатки, а значит наш ответ _NO_.↵

В противном случае должно выполняться равенство↵
$$↵
d \bmod 6 = d - 6x↵
$$↵
Здеь возможны две ситуации↵
$$↵
d - 6x = 3↵
$$↵
Поскольку после каждого раунда выполняется инвариант, о том, что суммарная длина колонок делится на $9$, то это означает, что под остатками должны быть еще $2$ ряда из $3$ единиц, которые могут быть уничтожены за один раунд. Далее у нас остаются $3$ колонки равной высоты кратной $3$. А это значит, что решение есть.↵

Вторая ситуация, когда↵
$$↵
d - 6x = 0↵
$$↵
означает, что все колонки оказались одинаковой высоты.↵
Благодаря инварианту о делимости на $9$ после каждого раунда, мы знаем, что все эти три колонки могут быть успешно уничтожены.↵

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


[problem:1463B]↵

Решение из эдиториала как-то не пришло мне в голову.↵
Вместо этого я использовал массив $b$ такой, что↵
$$↵
b_k = 2^{\lfloor\lg{a_k}\rfloor}↵
$$↵
что по-сути означает↵
$$↵
b_k = 2^{\alpha{}_k}: 2^{\alpha{}_k} \leqslant a_k < 2^{\alpha{}_k + 1}↵
$$↵
Если для любого $k$ выполняется $a_k - b_k \leqslant \frac{a}{2}$, то тогда мы можем сказать, что↵
$$↵
\sum{
(a_k - b_k)} \leqslant \sum{\frac{a_k}{2}} = \frac{S}{2}↵
$$↵
Для нашего $b_k$ это действительно так:↵
Пусть в двоичной записи $a_k = 1\text{xxxx}$, тогда $b_k = 10000$, а $\frac{a_k}{2} = 01\text{xxx}$, т.е. для любого $b_k$ мы имеем↵
$$↵
b_k \leqslant \frac{a_k}{2}↵
$$↵


[problem:1463D]↵

Посчитаем, какое минимальное количество элементов $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] == 
01.↵
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$.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский nechaev 2021-01-09 17:52:23 0 (опубликовано)
ru4 Русский nechaev 2021-01-09 17:52:03 4 Мелкая правка: 'n$$\n\sum{a_k - b_k} \leqslan' -> 'n$$\n\sum{(a_k - b_k)} \leqslan'
ru3 Русский nechaev 2021-01-09 17:47:08 1863 Problems: B and D
ru2 Русский nechaev 2021-01-07 09:58:21 2 Мелкая правка: 'вольно витееватый, ну' -> 'вольно витиеватый, ну'
ru1 Русский nechaev 2021-01-07 09:56:17 2848 edu_100_A (сохранено в черновиках)