779A - Перераспределение учеников

Автор задачи: MikeMirzayanov

Для решения данной задачи воспользуемся массивом cnt[]. Проитерируемся по первому массиву с успеваемостями, и если очередная успеваемость равна x, увеличим cnt[x] на единицу. Аналогичным образом, проитерируемся по второму массиву, и если очередная успеваемость равна y, уменьшим cnt[y] на единицу.

Если после этого хотя бы один из элементов массива cnt нечетный, ответом будет  - 1 (это означает, что учеников с такой успеваемостью нечетное количество и их никак не удастся разделить пополам). Если же все элементы массива четны, то ответом будет сумма абсолютных величин массива cnt, делённых пополам, причем итоговую сумму тоже нужно разделить пополам, так как каждый обмен при таком нахождении ответа будет посчитан дважды.

779B - Странное округление

Автор задачи: MikeMirzayanov

Для решения данной задачи нам нужно добиться того, чтобы в числе n в конце было k нулей, а перед ними хотя бы одна ненулевая цифра. Будем рассматривать число n как строку и пройдем по ней, начиная с конца (то есть с самого младшего разряда). Пусть cnt равно количеству цифр, которые мы уже рассмотрели. Если очередной символ строки не равен нулю, увеличим ответ на единицу. Если cnt стало равно k и мы рассмотрели не все цифры в строке n — выводим ответ.

В противном случае, нужно удалить из строки все символы, кроме одного, который равен нулю (если таковых несколько, то нужно оставить ровно один из них). Таковой символ обязательно найдется, так как гарантируется, что ответ существует.

779C - Нечестные продавцы

Авторы задачи: MikeMirzayanov и fcspartakm

Для решения данной задачи нужно отсортировать все товары по возрастанию величин a_i - b_i. Затем нужно проитерироваться по отсортированному массиву. Для очередного товара x, если мы еще не купили k товаров сейчас или после скидок товар x будет стоит не больше, чем сейчас, нужно купить его по цене a_x, в противном случае, нужно купить товар x по цене b_x.

778A - Игра на строке

Автор задачи: FireZi

В задаче нужно понять, в какой последний момент времени строка t будет такой, что из нее можно получить p вычеркиванием букв. Если в данный момент из строки t можно получить строку p вычеркиванием букв, то и в любой момент до этого это также можно было сделать. Поэтому решение — двоичный поиск по числу ходов, которые сделала Настя. Нужно для фиксированного момента времени m проверять, может ли p быть получена из t. Надо сделать m вычеркиваний Насти и проверить, что p подпоследовательность этой строки.

778B - Побитовая формула

Автор задачи: burakov28

Заметим, что задача по битам независима: изменение только значение i-го бита влияет только i-е биты других переменных. А сумма значений переменных больше, чем больше переменных имеют единицу на i-й позиции.

Будем решать задачу для i-го бита, то есть узнаем чему должен быть равен i-й бит загаданного числа. Для этого переберем оба значения и просимулируем программу, заданную во входном файле. Выберем то из двух значений, которое дает больше переменных, на которых стоит единица на i-й позиции. При равенстве выберем минимальное значение, то есть 0.

778C - Петрович --- полиглот

Авторы задачи: niyaznigmatul и YakutovDmitriy

При удалении буквы с индексом p бор меняется так, что все ребра из вершины на глубине p склеиваются в одно, как это видно на картинке из пояснения к примеру. После того, как ребра склеиваются, из нескольких поддеревьев получается их объединение.

Заметим известный интересный факт: если для всех вершин дерева v, пробежаться по всем поддеревьям детей v, кроме самого большого, то это будет работать за суммарно.

Пусть s_x — размер поддерева с корнем в вершине x. Рассмотрим ребенка v с самым большим поддеревом — h_v, то есть s_u ≤ s_hv для всех u — детей v. Если u — ребенок v, и поддерево с корнем в u не самое большое среди детей v, то .

1. Пусть . Тогда и следовательно .

2. А если же , то мы знаем, что s_u + s_hv < s_v, и из этого следует, что .

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

Решение:
1, Перебрать число p
2. Перебрать все вершины v на глубине p
3. Объединить все поддеревья пробежавшись по всем поддеревьям кроме самого большого.

Как объединить поддеревья? Метод первый. Найдем самое большое поддерево, оно уже построено. Попробуем к нему добавить какое-нибудь другое поддерево. Для этого обойдем маленькое поддерево, параллельно проходясь по большому и добавляя вершины, которых в большом нет. Тем самым мы объединим все поддеревья с корнями в детях вершины v и узнаем размер объединения. Далее, надо вернуть все на место. Для этого во время объединения запомним все ячейки памяти, которые изменились, и их старые значения. После объединения, можно в обратном порядке восстановить старые значения.

Можно ли сделать объединение без отката? Метод второй. Возьмем все поддеревья кроме самого большого. Построим их объединение в новой памяти. После чего, имея теперь два поддерева: самое большое и объединение всех кроме самого большого, можно найти размер объединения этих двух поддеревьев ничего не изменяя, просто пробежавшись по одному из них, параллельно изучив есть ли такие же вершины во втором. После чего ту новую память, куда мы положили объединение, можно будет переиспользовать.

778D - Перекладывание паркета

Автор задачи: pashka

Пусть ширина прямоугольника четная (если нет — повернем). Приведем обе конфигурации к такому виду, что все плитки лежат горизонтально. После этого, поскольку все ходы обратимы, нужно просто развернуть последовательность ходов для второй конфигурации.

Как получить конфигурацию в которой все плитки лежат горизонтально. Пойдем сверху вниз, слева направо, и будем выставлять все плитки в правильное положение. Пусть плитка стоит неправильно. Тогда попробуем повернуть ее в правильное положение. Если это не получается, потому что соседняя плитка ориентирована по-другому, перейдем рекурсивно к ней. Таким образом, получится "лесенка", которая не может идти дальше, чем на n плиток вниз. В конце этой лесенки будет две плитки, ориентированные одинаково. Производя операции снизу вверх, выставим верхнюю плитку в горизонтальное положение.

778E - Продажа чисел

Авторы задачи: niyaznigmatul и VArtem

Поскольку ответ на задачу считается независимо по каждому разряду во всех числах, будем использовать динамическое программирование. Обозначим dp_k, C за максимальную возможную стоимость цифр, где k — количество рассмотренных младших разрядов, а C — множество чисел, в которых произошел перенос. Этой информации достаточно, чтобы выбрать, какую цифру поставить в текущем разряде A, и пересчитать переносы в следующий разряд и значение ДП.

Ключевой идеей является то, что возможных множеств чисел не 2ⁿ, а не более n + 1. Пусть мы рассмотрели k младших разрядов A и B_i. Рассмотрим все суффиксы чисел B_i длины k, отсортируем их по убыванию лексикографически. Из-за того, что ко всем этим суффиксам в результате добавится одно и то же число, свойство <<иметь перенос>> монотонно: если в числе B_x произойдет перенос, то перенос произойдет и во всех больших числах. Отсюда множество всех чисел, в которых будет перенос в текущем разряде, образует префикс длины m (0 ≤ m ≤ n) этого отсортированного списка. Таким образом, количество состояний ДП сократилось до O(n·|A|). Отсортировать все суффиксы чисел B_i можно с помощью цифровой сортировки за O(n·max |B_i|), приписывая каждый раз слева очередную цифру и пересчитывая порядок.

Осталось реализовать вычисление переходов в ДП за O(1). Для этого нужно поддерживать суммарную стоимость всех цифр в этом разряде, а также количество чисел с переносом в следующий разряд. При добавлении очередного числа с переносом эти величины несложно пересчитываются. После того, как все цифры в A обработаны, нужно обработать оставшиеся цифры в B_i (если такие есть) и взять наилучший ответ. Время работы: .