Only a few strings have the answer "YES".

For $$$n \ge 3$$$, the answer is "NO".

Let $$$n \ge 3$$$ and the resulting string be $$$a$$$. For there to be no palindromes of length greater than $$$1$$$, at least all of these inequalities must be true: $$$a_1 \neq a_2$$$, $$$a_2 \neq a_3$$$, and $$$a_1 \neq a_3$$$. Since our string is binary, that is not possible, so the answer is "NO".

For $$$n \le 2$$$, there are 4 strings that have the answer "YES": $$$0$$$, $$$1$$$, $$$01$$$, and $$$10$$$; as well as 2 strings that have the answer "NO": $$$00$$$ and $$$11$$$.

Complexity: $$$O(n)$$$

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

Минимальная стоимость постройки опор — $$$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)$$$

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

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

В оптимальном решении третья операция применяется не больше одного раза, так как применение данной операции не уменьшает $$$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$$$.

Назовем отрезок $$$[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$$$-значений. Это наблюдение также может использоватся для поиска плохих отрезков.

It is optimal to add edges of the form $$$(1, v)$$$.

Try to check if for a fixed $$$x$$$ the answer is at most $$$ans$$$.

For a fixed $$$x$$$ and answer $$$ans$$$, find the distance between nodes that have $$$depth_v > ans$$$.

For each node, find two children with the deepest subtrees.

Read the hints above.

Let $$$f_{ans}$$$ be the maximum distance between two nodes that have $$$depth_v > ans$$$. If for some $$$x$$$ the answer is at most $$$ans$$$, then either $$$ans \ge depth$$$ or $$$\lceil \frac{f_{ans}}{2} \rceil + x \le ans$$$, since we can add an edge $$$(1, u)$$$ where $$$u$$$ is in the middle of the path connecting the two farthest nodes with $$$depth_v > ans$$$. Since $$$f_ans$$$ decreases as $$$ans$$$ increases, we can use binary search. Also note that we can use two pointers and increase $$$ans$$$ as we increase $$$x$$$.

How to calculate $$$f_{ans}$$$? Let's find for each node its two children with the deepest subtrees. Let $$$a_v$$$ and $$$b_v$$$ be the depths of their subtrees ($$$a_v \ge b_v$$$). If there are not enough children, set this values to $$$depth_v$$$. If $$$b_v > 0$$$, do $$$f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$$$. After this, iterate $$$i$$$ from $$$n - 2$$$ to $$$0$$$ and do $$$f_i = \max(f_i, f_{i + 1})$$$.

Complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ with binary search.