Набор задач в онлайн-трансляции незначительно отличается от набора задач на основном раунде, задачи следуют в порядке, в котором они фигурируют в основном раунде.

524A - Возможно, вы знаете этих людей?

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

Тонкий момент №1: несмотря на то, пар друзей во вводе не более 100, самих людей может быть до 200, и можно ошибиться в выставлении размеров массивов.

Тонкий момент №2: нужно аккуратно сравнивать вещественные числа. Если написать нечто вроде common / degree >= k / 100.0, то в силу специфики вычислений с вещественными числами, результат такой проверки может быть недетерминирован (если в какую-то из частей внесётся незначительная погрешность). Поэтому, надо либо сравнивать с точностью до некоторого eps, либо выполнять проверку в целых числах: common * 100 >= degree * k.

524B - Фото на память - 2 (round version)

Переберём высоту итоговой фотографии. При фиксированной высоте нам требуется минимизировать суммарную ширину всех прямоугольников. Таким образом, для каждого прямоугольника нужно выбрать такое из двух его положений, которое, во-первых, подходит по высоте, а во-вторых, имеет меньшую возможную ширину.

529B - Фото на память - 2 (online mirror version)

В версии для онлайн-трансляции условие было незначительно изменено — разрешается, чтобы не более n / 2 людей лежали на фотографии. Это слегка усложняет решение. Введём терминологию: людей, у которых w ≤ h, будем называть высокими, а остальных людей — широкими. Зафиксируем итоговую высоту фотографии H. Далее, следует небольшой разбор случаев.

• Если высокий человек влезает под высоту H, то мы его оставляем именно в таком состоянии.
• Если высокий человек не влезает под высоту H, то мы обязаны его положить, увеличиваем счётчик таких людей на 1.
• Если широкий человек влезает под высоту H, но не влезает, будучи положенным, то ставим его.
• Если широкий человек влезает под высоту H обоими способами, то сначала ставим его, а в отдельный массив выписываем величину, на которую уменьшится ответ, если этого человека всё-таки положить: w - h.
• Если же кто-то не влезает ни одним из двух способов, то подобное значение H недопустимо.

Теперь у нас есть какое-то количество людей, которые обязательно должны лечь (из второго пункта), причём, если их слишком много, а именно, больше, чем n / 2, то подобное значение H недопустимо.

За вычетом людей из второго пункта у нас осталось некоторое количество вакантных лежачих мест — распределяем их по людям из четвёртого пункта в порядке уменьшения величины (w — h). Считаем площадь фотографии, выбираем минимум по всем H.

524C - Искусство обращения с бакноматом

Предполагаемое решение имеет сложность или . Для каждой возможной суммы денег x = t·a_i (1 ≤ t ≤ k) выпишем пару (x, t) в массив, здесь t — количество купюр, которым такую сумму можно достичь. Отсортируем этот массив. Тогда чтобы ответить на один запрос, переберём первое слагаемое в сумме, а второе либо найдём бинарным поиском, либо воспользуемся методом двух указателей, чтобы найти парное слагаемое за амортизированное время O(1). Проверим, что получилось не более k купюр в сумме, улучшим ответ, если надо.

524D - Социальная сеть

Будем жадно действовать следующим образом. Идём по запросам в порядке поступления. Каждый очередной запрос пытаемся сопоставить новому человеку. Разумеется, это не всегда возможно сделать — если у нас уже есть M активных людей на сайте, то мы обязаны сопоставить очередной запрос кому-то из них. Возникает вопрос — кому именно?

Можно показать, что выгоднее всего сопоставить этот запрос самому недавнему из активных людей. Действительно, подобное “критическое” (по количеству людей) состояние можно задать вектором из M чисел — временами с момента последнего запроса каждого из людей в убывающем порядке. Тогда если сейчас состояние — (a₁, a₂, ..., a_M), то мы можем перейти в одно из M новых состояний (a₁, a₂, ..., a_M - 1, 0), (a₁, a₂, ..., a_M - 2, a_M, 0), ... , (a₂, a₃, ..., a_M, 0), в зависимости от того, к кому мы подцепим очередной запрос. Видно, что самый первый вектор покомпонентно больше, чем любой из оставшихся, а это значит, что он выгоднее всех остальных (т. к. чем больше число на определённой позиции в векторе, тем скорее может исчезнуть этот человек, и тем больше у нас остаётся свободы для последующих действий).

Значит, нам требуется моделировать процесс, поддерживая в некоторой структуре данных множество активных людей с временами их активности. В качестве подобной структуры можно воспользоваться любой структурой, реализующей интерфейс очереди с приоритетом (priority_queue, set, дерево отрезков или что-либо ещё). Итоговая сложность решения — .

524E - Ладьи и прямоугольники

Поймём, что означает тот факт, что какая-то клетка прямоугольника не побита ладьёй. Это значит, что существует строка прямоугольника, не содержащая ладью, и существует столбец прямоугольника, не содержащий ладью. Не очень ясно, как проверять это утверждение, поэтому проверим обратное к нему — мы только что показали, что прямоугольник является покрытым, если либо в каждой строке стоит ладья, либо в каждом столбце стоит ладья.

Эти утверждения можно проверять по отдельности. Как проверить для набора прямоугольников, что в каждой строке находится отмеченная точка? Это можно сделать за один проход вертикальной сканирующей прямой. Пусть мы идём слева направо и прошли через правую границу прямоугольника, расположенного в строках с a-й по b-ю, левая граница которого находится в столбце x. Тогда если обозначить за last[i] позицию последней ладьи, встреченной в строке номер i, то критерий для прямоугольника выглядит следующим образом: . Это значит, что для хранения величины last можно воспользоваться деревом отрезков. Аналогично проверяем для столбцов. Выходит решение, отвечающее на все запросы off-line за время O((q + k)log(n + m)).

524F - И снова правильная скобочная последовательность

Общая идея заключается в том, что скобочные последовательности можно рассматривать как последовательности балансов префиксов, т. е. как последовательности чисел (a_i), где a_i + 1 = a_i ± 1.

Посчитаем количество открывающихся скобок A и закрывающихся скобок B в исходной строке. Заметим, что если A >  = B, то строку всегда можно исправить, дописав A - B закрывающихся скобок в конец, и циклически сдвинув строку в точку минимума баланса, а если A ≤ B, то строку аналогично можно исправить, дописав B - A открывающихся скобок в начало. Очевидно, что меньшим количеством скобок не обойтись. Таким образом, мы уже знаем величину ответа, теперь нужно понять, как он устроен.

Будем считать, что мы сначала производим циклический сдвиг, а потом только добавляем скобки. Пусть, для определённости, мы дописываем x закрывающихся скобок. Сформулируем два несложных утверждения:

• Если путём дописывания в определённые x мест закрывающейся скобки, строку можно сделать правильной скобочной последовательностью, то её также можно сделать правильной дописывая x закрывающихся скобок просто в конец.
• Из всех строк, которые можно получить дописыванием в произвольные x мест закрывающейся скобки, минимальной является та, в которой скобки дописываются в конец.

Каждое из этих утверждений несложно проверить, а в совокупности они нам дают тот факт, что в оптимальном ответе мы дописываем закрывающиеся скобки в конец строки. Значит, нам надо рассмотреть множество таких циклических сдвигов строки, что они превращаются в правильную скобочную последовательность при приписывании в конец x = A - B закрывающихся скобок (т. е. просто не имеют нигде отрицательного баланса), и выбрать из них лексикографически минимальный. Сравнение циклических сдвигов строки можно проводить либо при помощи суффиксного массива, либо же, так как нам требуется только найти минимальный сдвиг из определённого множества, можно сравнивать сдвиги между собой при помощи бинарного поиска и хеширования.

Аналогично делается случай, когда A ≤ B, с единственным отличием, что открывающиеся скобки дописываются в начало.

Таким образом, выходит решение за сложность .