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

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 constuction that reaches it is $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

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

Note: there is also a different solution which uses the fact that there $$$O(log A)$$$ different suffix gcd values for a fixed prefix.

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

Try to solve the problem for a fixed answer.