Ответ "YES" только для малого количества строк.

Для $$$n \ge 3$$$, ответ "NO".

Пусть $$$n \ge 3$$$ и результирующая строка будет $$$a$$$. Чтобы в ней не было палиндромов длины больше чем 1, должны выполняться как минимум вот эти неравенства: $$$a_1 \neq a_2$$$, $$$a_2 \neq a_3$$$ и $$$a_1 \neq a_3$$$. Но так как у нас бинарная строка, это невозможно, поэтому ответ "NO".

Для $$$n \le 2$$$, есть 4 строки с ответом "YES": $$$0$$$, $$$1$$$, $$$01$$$, и $$$10$$$; а также 2 строки с ответом "NO": $$$00$$$ и $$$11$$$.

Временная сложность: $$$O(n)$$$

• Код на C++.
• Код на Python.

Минимальная стоимость постройки опор — степень двойки.

Минимальная стоимость постройки опор — $$$2 ^ k$$$, где $$$k$$$ — старший бит числа $$$n - 1$$$.

Пусть $$$k$$$ — старший бит числа $$$n - 1$$$. Очевидно, что в массиве высот опор точно будет два соседних элемента, у одного из которых $$$k$$$-ый бит будет равен $$$1$$$, а у второго — $$$0$$$. Из этого следует, что минимальная стоимость постройки опор не меньше $$$2 ^ k$$$. Простая конструкция, в которой эта минимальная стоимость достигается — $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

Временная сложность: $$$O(n)$$$

Бонус: посчитайте количество перестановок с минимальной стоимостью

• Код на C++.
• Код на Python.

В оптимальном решении третья операция применяется не больше одного раза.

В оптимальном решении третья операция применяется не больше одного раза, так как применение данной операции не уменьшает $$$a$$$ и всегда делает $$$b \le a$$$. Это означает, что после применения третьей операции выгодно выполнять только вторую операцию до тех пор, пока $$$a$$$ не станет равно $$$b$$$.

Если мы не применяем третью операцию ни разу, ответ $$$b - a$$$.

Предположим, что мы применили третью операцию. Перед этим мы какое-то количество раз применили первую и вторую операцию, пусть итоговые значения $$$a$$$ и $$$b$$$ непосредственно перед применением третьей операции будут $$$a'$$$ и $$$b'$$$ соответственно $$$(a \le a', b \le 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(\log b)$$$ и может быть ускорен до $$$O(1)$$$ с помощью использования битовых операций.

Временная сложность: $$$O(b)$$$ или $$$O(b \log b)$$$

Бонус 1: решите задачу за $$$O(\log b)$$$ или быстрее.

Бонус 2: докажите что оптимально сделать $$$a' = a$$$ или $$$b' = b$$$.

• Код на C++ с временной сложностью $$$O(b \log b)$$$.
• Код на C++ с временной сложностью $$$O(b)$$$.
• Код на Python с временной сложностью $$$O(b \log b)$$$.

Назовем отрезок $$$[l, r]$$$ плохим, если $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. Есть не больше $$$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$$$-значений. Это наблюдение также может использоваться для поиска плохих отрезков.

• Код на C++, использующий дерево отрезков и бинарный поиск с временной сложностью $$$O(n \log n (\log n + \log A))$$$.
• Код на C++, использующий спарс таблицу и метод двух указателей с временной сложностью $$$O(n \log n \log A))$$$.
• Код на Python, использующий дерево отрезков и метод двух указателей с временной сложностью $$$O(n (\log n + \log A))$$$.

Оптимально добавлять рёбра типа $$$(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$$$ тоже лист).

• Код на C++ для E1 с временной сложностью $$$O(n ^ 2)$$$.
• Код на Python для E1 с временной сложностью $$$O(n ^ 2)$$$.
• Код на C++ для E2 с временной сложностью $$$O(n)$$$.
• Код на Python для E2 с временной сложностью $$$O(n)$$$.