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$$$, $$$10$$$}, and 2 strings that have the answer "NO": {$$$00$$$, $$$11$$$}.

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

The cost of construction is a power of two.

The cost of construction is $$$2 ^ k$$$, where $$$k$$$ is the highest set bit in $$$n - 1$$$. .

Let $$$k$$$ be the highest set bit in $$$n - 1$$$. There will always be a pair of adjacent elements where one of them has the $$$k$$$-th bit set and the other one doesn't, so the cost is at least $$$2^k$$$. A simple construction that reaches it is $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

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

Bonus: count the number of permutations with the minimum cost.

It is optimal to apply the third operation at most once.

???

Bonus 1: solve the problem in $$$O(\log b)$$$ or faster.

Bonus 2: prove that is optimal to have either $$$a' = a$$$ or $$$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?

Greedy

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$$$, which is simple, since our segments are not nested.

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 solve the problem for a fixed answer.