Codeforces Round #723 Kill Anton Solution (Java/C++)

Solution:

Let consider how Anton fix the DNS. We found that: for minimum cost, every time, Anton just fixing one character. For example, fix NNOTA to ANTON. The first stage is NNOTA -> ANNOT, which fixed first character. The second stage is ANNOT -> ANNOT (No change, because second character is already same). the third stage is ANNOT -> ANTNO.
So, generally, we try to make character as far as possible. So that each stage will take most effort.

Now let us consider the case which only have two different characters. For example, N and A.
In case AANNNNN, of course the answer is NNNNNAA.
In case ANANNNN, also the answer should be NNNNNAA. Furthermore, for ANNANNN, the answer should be NNNNNAA. Not AANNNNN.
Last case is NNAANN, we found AANNNN, NNNNAA and ANNNNA have same cost.
So, if we only consider A. We found that: if we want Anton to take the most effort to restore A, then we should put all the A to the left or right side.

Let us consider N then. We found there is nothing need to think. Because after A back to original position, N will also be restored. So, the effort is 0.

Now we consider three characters. For example, N, A and T.
For ATATNNN. We put the all the A to right side first and get TTNNNAA. And we found that we can swap T to make more effort. So, we get NNNTTAA.
Why?
Consider Anton's process for TTNNNAA: TTNNNAA -> ATTNNNA -> ATATNNN. So, for restore, this process can ignore T and N.
For force Anton consider T and N, after push A to right side, for remain part TTNNN, do the same process again. And the NNNTT will get highest effort. And combine with A, we get NNNTTAA.

So, the solution is: 1. we push one of the characters to the most left or right side. 2. for remained characters, do the operation 1 again.

The solution above should work. But too complex to implement it. Based on the solution above, we can find that, in the answer the same characters must be consecutive. For example, NNNAATTTO. But will not like NATONAT.
So, we can enumerate the permutation of the four letters with $A_4^4$. And calculate the cost of each one. And select the max one as answer.

Code:

Java

C++

Complaints:

The DNA is made by four characters: ANOT? So, this problem is made by NATO?