Ugh. Really weak. Problem E actually still has "expected possibilities" to solve it, but I given up.
E. Travelling Salesman Problem
Solution
Not solve this problem by myself. Looked the solution above.
Code
D. 3-Coloring
Interactive problem is interesting. It's a game problem but more like a construction problem. Not very hard. But my solution is a little hard to implementation. Not sure if there is other solutions.
C. Balance the Bits
Solution
Classic bracket pairing problem. Calculate prefix sum from left to right. So if found '(' then +1, otherwise -1. Of course in the whole process, the total sum should be zero and non of prefix less than 0.
Now think about $s_i=0$. That means in $a$ and $b$, one of them +1 another one -1. We just +1 for the one which prefix sum is less than another.
Then think about $s_i=1$. This one will affect the prefix sum for both $a$ and $b$. Because $s_i=0$ will need -1. Also because two 0 in $s$ will not impact the prefix sum. So for more safety, first half of $1$, we always chose '('. And other half always ')'.
Code
Get WA once because of a small mistake. I forgot check if anything left after scanned $s$.
B. Flip the Bits
Solution
Do the operation from back to the front. Just a implementation problem.
Code
A. Déjà Vu
Solution
Implementation. Try insert to the start and end position. If both of them are palindrome, then return no. Otherwise, print the one which is not palindrome.
Code
