Codeforces Round #728 (Div. 2) ABC Solutions (Java/C++)

A. Pretty Permutations

Solution:

Obviously, only the two neighbors need to exchange positions with each other.
For the case where n is an odd number, only the last three bits need to be exchanged with each other.

Code:

Java

C++

B. Pleasant Pairs

Solution:

Sort the original array a.
Then for any value, we can enumerate the a from small to large. We stop the enumeration when the product greater than 2n (i+j always less than 2n).
So, the time complexity is around $\frac{n}{a_1}+\frac{n}{a_2}+\frac{n}{a_3}+...\frac{n}{a_n}$.

Code:

Java

C++

C. Great Graphs

Solution:

To minimalize the positive value, we try to reuse the path which the cost is positive. So, the positive path looks like this:

Then, to minimalize the negative path, we can build it based on the positive path:

Code:

Java

C++