Problem A
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$$$}.
Problem B
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.
Problem C
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$$$.
Problem D
It is optimal to apply the third operation at most once.
Note: there is also a different solution which uses the fact that there at most $$$O(log A)$$$ different prefix gcd values.
Problem E
It is optimal to add edges of the form $$$(1, v)$$$.
Try to solve the problem for a fixed answer.
