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$$$.

Let's call a segment $$$[l, r]$$$ bad if $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. There at most $$$n$$$ bad segments.

For a fixed $$$l$$$, as $$$r$$$ increases, $$$\gcd(a_l \ldots a_r)$$$ decreases.

Suppose you change $$$a_i$$$ into a big prime. How does this affect the bad segments?

Read the hints above.

Let's find all of the bad segments. For a fixed $$$l$$$, let's find the largest $$$r$$$ that has $$$\gcd(a_l \ldots a_r) \ge r - l + 1$$$. This can be done with binary search and a sparse table / segment tree. If $$$\gcd(a_l \ldots a_r) = r - l + 1$$$, then the segment $$$[l, r]$$$ is bad.

If we change $$$a_i$$$ into a big prime, no new bad segments will appear. And all bad segments that have $$$i$$$ inside of them will disappear.

Notice that for two bad segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$, if $$$l_1 < l_2$$$, then $$$r_1 < r_2$$$. In other words, they can not be nested. Let's sort the segments by $$$r$$$ and loop over $$$k$$$ — the length of the prefix. As soon as we encounter some segment with $$$r = k$$$, we add one to the current answer and then remove all segments with $$$l \le k$$$. Since our segments are not nested, this is easy to do.

Complexity: $$$O(n \log n \log A)$$$ with a sparse table, where $$$A$$$ is the maximum value of $$$a_i$$$.

Notes:

There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity $$$O(n (\log n + \log A))$$$.

You can also use the fact that for a prefix, there at most $$$O(\log A)$$$ different suffix $$$\gcd$$$ values. This leads to another way to find the bad segments.

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.