A. Двоичная строка

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

• Либо |b - c| > 1
• Либо b = 0, c = 0, и при этом a ≠ 0 и d ≠ 0

Для остальных случаев будем решать в два этапа: Сначала соберем минимальную строку, которая будет удовлетворять условиям на строки 01 и 10, а затем допишем после первого встреченного нуля a - 1 ноль, а после первой встреченной единицы d - 1 единицу. Очевидно, что условия на 01 и 10 от таких действий не испортятся.

B. Поезд и туннель

Разобьем весь поезд на отрезки вагонов без света. Будем идти по каждой группе из таких вагонов, и в том вагоне, на котором суммарная длина вагонов становится не меньше h, будем включать свет. Очевидно, что данная стратегия дает наименьший результат. Также нужно не забыть включить свет в первом и последнем вагонах: при въезде в туннель и выезде из него, соответственно, эти вагоны образуют темный момент времени.

C. Красивое разбиение

Первый элемент массива входит либо в M₁, либо в M₂. Не умаляя общности, будем считать, что он входит в M₁. Тогда a[1] делится на gcd(M₁), то есть gcd(M₁) — делитель a[1].

Переберем все делители a[1] (их не больше 1344 для чисел до 10⁹). Рассматривая текущий делитель d, возьмем все элементы массива, делящиеся на d, в M₁ (так как от этого gcd(M₁) не станет меньше d, а чем меньше элементов в M₂, тем gcd(M₂) больше), а все остальные элементы в M₂ и обновим ответ величиной min(gcd(M₁), gcd(M₂)). Заметим, что мы можем пренебречь тем, что M₂ будет пустым, считая в этом случае gcd для него равным бесконечности, поскольку все элементы в таком случае делятся на d, то и gcd(M₂) будет не меньше d.

Асимптотика решения — O(sqrt(a[1]) + d(a[1])·n), где d(a[1]) ≤ 1344.

D. Подготовка задач

Для начала решим задачу, если нет запросов на изменение времен. Из массива t_i сгенерируем новый массив cnt_j, в котором будем хранить количество задач, на которые необходимо потратить j минут, а также предподсчитаем массив его префиксных сумм. Тогда количество времени, которое потратит каждый друг, если их всего k, можно посчитать за O(MAX / k), где MAX — максимальное необходимое на задачу время (просто перебрав, на какие задачи потребуется 1, 2, ... MAX / k минут). Как известно, суммарное время работы такого алгоритма для всех k от 1 до MAX равно O(MAXlog(MAX)).

Теперь посмотрим, что происходит, когда время, необходимое на задачу, изменяется с t на t + 1. Ответы поменяются только для k являющихся делителями t. Поскольку максимальное количество делителей у чисел до 5·10⁵ равно 200, то можно просто их все перебрать за время пропорциональное их количеству и обновить ответ только для них.

Аналогично, если время изменяется с t на t - 1, то ответы меняются для чисел, которые являются делителями t - 1.

E. Похожее метро

В задаче требовалось найти наибольшую по размеру пару изоморфных друг другу связных поддеревьев данных деревьев. Будем решать эту задачу методом динамического программирования.

Посчитаем для пары ориентированных ребер (u₁, v₁) в первом дереве и (u₂, v₂) во втором дереве значение dp[u₁][v₁][u₂][v₂], равное размеру наибольшей пары изоморфных поддеревьев, если вершина u₁ перейдет в вершину u₂, а вершины v₁ и v₂ обязательно не войдут в выбранные поддеревья. Кроме того, разрешим v_i быть равной какой-нибудь фиктивной вершине -1, это будет значить, что удаленного поддерева v_i нет, и можно использовать для общего поддерева все вершины. Если мы посчитаем такую величину, ответом будет максимум по всем парам вершин u₁, u₂ величины dp[u₁][-1][u₂][-1].

Чтобы посчитать dp[u₁][v₁][u₂][v₂], нужно каким-то образом сопоставить поддеревья u₁ и u₂ друг другу. Заметим, что если e₁ — сын вершины u₁, отличный от v₁, то поддерево e₁ содержит меньше вершин, чем поддерево u₁, при подвешивании дерева за v₁. Для сыновей e₁ вершины u₁ и e₂ вершины u₂ мы по предположению индукции уже посчитали dp[e₁][u₁][e₂][u₂], так что мы знаем, сколько вершин можно добавить в искомое поддерево, если вершине e₁ в нем будет соответствовать e₂. Если у вершины u₁ — k сыновей, у u₂ — m сыновей, то мы получаем матрицу a_i, j размера k·m, в которой нужно выбрать несколько ячеек с максимальной суммой, при условии, что в каждом столбце и в каждой строке выбрано не больше одной ячейки. Это стандартная задача о назначении, которая решается Венгерским алгоритмом.

Итоговая сложность решения — O(n⁵), n² способов выбрать пару ребер в двух деревьях и O(n³) — время работы Венгерского алгоритма. Для оптимизации можно не решать задачу о назначении для одинаковых (изоморфных) пар деревьев несколько раз, а запомнить ответ.