351E - Jeff and Permutation

Here is an alternate, simpler, solution to the one given in the editorial.

First, let's consider p_i and p_j in positions i < j. Let's first assume that |p_i| ≠ |p_j|. When will this be an inversion?

If |p_i| > |p_j|, then it is an inversion when p_i is negative, and not when p_i is positive, because  - |p_i| <  - |p_j| ≤ |p_j| < |p_i|. Thus our choice of p_j does not affect if (i, j) is an inversion.

Similarly, if |p_i| < |p_j|, then the choice of p_i does not matter.

Thus for each element p_k, we can choose its sign by looking at the count of the |p_i| < |p_k|, with i < k and i > k. If there are more with i < k, we make p_i positive, and otherwise, we make p_i negative.

But wait! What if |p_i| = |p_j|? Then whether or not (i, j) is an inversion depends on both values. Fortunately, this is not a problem, as if we do the above algorithm, if |p_i| = |p_j|, then the algorithm will make p_i ≤ p_j, so (i, j) will not be an inversion.

This is because there cannot be more elements with absolute value at most |p_i| left of i than right of i, and at the same time less elements with absolute value at most |p_i| left of j than right of j.

This algorithm can run in O(n²) time, and uses O(n) memory (with no DP at all, only greedy). With some sorting and a data structure, I believe we can improve this to time.