Также вы можете посмотреть видеоразборы задач B-D по-английски от ak2006 на его Youtube-канале!
1632A — ABC
Ответ "YES" только для малого количества строк.
Для n≥3, ответ "NO".
Пусть n≥3 и результирующая строка будет a. Чтобы в ней не было палиндромов длины больше чем 1, должны выполняться как минимум вот эти неравенства: a1≠a2, a2≠a3 и a1≠a3. Но так как у нас бинарная строка, это невозможно, поэтому ответ "NO".
Для n≤2, есть 4 строки с ответом "YES": 0, 1, 01, и 10; а также 2 строки с ответом "NO": 00 и 11.
Временная сложность: O(n)
1632B — Постройка крыши
Минимальная стоимость постройки опор — степень двойки.
Минимальная стоимость постройки опор — 2k, где k — старший бит числа n−1.
Пусть k — старший бит числа n−1. Очевидно, что в массиве высот опор точно будет два соседних элемента, у одного из которых k-ый бит будет равен 1, а у второго — 0. Из этого следует, что минимальная стоимость постройки опор не меньше 2k. Простая конструкция, в которой эта минимальная стоимость достигается — 2k−1, 2k−2, …, 0, 2k, 2k+1, …, n−1.
Временная сложность: O(n)
Бонус: посчитайте количество перестановок с минимальной стоимостью
1632C — Странная контрольная
В оптимальном решении третья операция применяется не больше одного раза.
В оптимальном решении третья операция применяется не больше одного раза, так как применение данной операции не уменьшает a и всегда делает b≤a. Это означает, что после применения третьей операции выгодно выполнять только вторую операцию до тех пор, пока a не станет равно b.
Если мы не применяем третью операцию ни разу, ответ b−a.
Предположим, что мы применили третью операцию. Перед этим мы какое-то количество раз применили первую и вторую операцию, пусть итоговые значения a и b непосредственно перед применением третьей операции будут a′ и b′ соответственно (a≤a′,b≤b′). В этом случае ответ будет равен (a′−a)+(b′−b)+((a′ | b′)−b′)+1 = a′+(a′ | b′)+(1−a−b). Это эквивалентно минимизации a′+(a′ | b′), так как (1−a−b) — константа.
Для решения этой задачи будем итерироваться по a′ от a до b. Для фиксированного a′, нам необходимо минимизировать a′ | b′, оптимальный b′ может быть найден следующим образом:
Сначала положим b′=0. Будем итерироваться по битам от старших к младшим. Тогда есть 4 случая:
- Если текущий бит a′ — 0 и b — 1, то выставляем текущий бит b′ в 1.
- Если текущий бит a′ — 0 и b — 0, то выставляем текущий бит b′ в 0.
- Если текущий бит a′ — 1 и b — 1, то выставляем текущий бит b′ в 1.
- Если текущий бит a′ — 1 и b — 0, то выставляем текущий бит b′ в 1 и останавливаемся.
Данный алгоритм работает за O(logb) и может быть ускорен до O(1) с помощью использования битовых операций.
Временная сложность: O(b) или O(blogb)
Бонус 1: решите задачу за O(logb) или быстрее.
Бонус 2: докажите что оптимально сделать a′=a или b′=b.
1632D — Новогодний концерт
Назовем отрезок [l,r] плохим, если gcd. Есть не больше n плохих отрезков.
Для фиксированного l, с возрастанием r, \gcd(a_l \ldots a_r) не возрастает.
Предположим, вы изменили a_i на большое простое число. Как это повлияет на плохие отрезки?
Для начала, прочитайте подсказки выше.
Найдем все плохие отрезки. Для фиксированного l, давайте найдем наибольшее r, такое, что \gcd(a_l \ldots a_r) \ge r - l + 1. Это можно сделать бинарным поиском и спарз таблицей / деревом отрезков. Если \gcd(a_l \ldots a_r) = r - l + 1, то отрезок [l, r] плохой.
Если мы заменим a_i на большое простое число, то все плохие отрезки, включающие i-ый элемент перестанут быть плохими, а новых плохих отрезков не появится.
Теперь задача свелась к стандартной: даны отрезки и нужно выбрать минимальное количество точек так, чтобы на каждом отрезке лежала хотя бы одна точка. Только в данном случае задача еще упрощена тем, что среди отрезков нет вложенных. Эта задача может быть решена жадным алгоритмом: в ответ возьмем правую границу самого левого отрезка, удалим все отрезки, покрытые данной точкой, и повторим операцию, пока есть хоть один отрезок.
Временная сложность: O(n \log n \log A) со спарз таблицей, где A — максимальное значение a_i.
Примечание:
Есть множество модификаций предыдущего решения, некоторые из которых используют метод двух указателей и обновляют ответ по ходу поиска плохих отрезков. Используя дерево отрезков и метод двух указателей, можно добиться временной сложности O(n (\log n + \log A)).
Также вы можете использовать тот факт, что для любого префикса существует максимум O(\log A) различных суффиксных \gcd-значений. Это наблюдение также может использоваться для поиска плохих отрезков.
1632E2 — Дистанционное дерево (сложная версия)
Оптимально добавлять рёбра типа (1, v).
Для фиксированного x, как проверить, что ответ не больше ans?
Для фиксированного x и ans, найдите максимальное расстояние между двумя вершинами для которых верно depth_v > ans.
Для каждой вершины, найдите два ребёнка с максимальной глубиной поддеревьев.
Для начала, прочитайте подсказки выше.
Пусть f_{ans} будет максимальным расстоянием между вершинами с depth_v > ans. Если для какого-то x ответ не больше ans, то ans \ge depth или \lceil \frac{f_{ans}}{2} \rceil + x \le ans, так как мы можем добавить ребро (1, u), где u будет на середине пути между двумя дальнейшими вершинами с depth_v > ans. Так как с возрастанием ans, f_ans убывает, мы можем использовать бинпоиск или два указателя.
Как посчитать f_{ans}? Найдём для каждой вершины два ребёнка с глубочайшими поддеревьями. Пусть a_v и b_v — глубины их поддеревьев (a_v \ge b_v). Если детей не хватает, то присвоим этим значениям depth_v. Если b_v > 0, то делаем f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v). А после этого переберём i от n - 2 до 0 и сделаем f_i = \max(f_i, f_{i + 1}).
Временная сложность: O(n) или O(n \log n) с бинпоиском.
Примечание: чтобы решить E1, достаточно найти f_{ans} за O(n) или O(n \log n) для каждого ans. Один способ это сделать — найти диаметр дерева после того, как были удалены все листы с depth_v \le ans (1 тоже лист).