Problem: 351E - Jeff and Permutation
Abridged statement: given n ≤ 2000 integers, we can multiply some of them by - 1. Goal is to minimize number of inversions (pairs (i, j) such that i < j and ai > aj). Print the minimum number of inversions.
Solution: 30244905
This solution replaces all numbers with its absolute value first. Then for each index i this solution adds min(L, R) to answer where L = number of smaller elements to left, R = number of smaller elements to right. Why does it work?
Click here and next time read comments below the editorial before asking such question.
Well if a beautiful lady comments on my post then it was worthy. Thanks.
An idea : Elements before this position, say k, which have absolute value lesser than ak can be kept as non-inversion only if ak is positive. Such elements after this position can be non-inversion only if ak is negative. Both cannot be satisfied at the same time. So s/he chooses one (and the smaller one) to keep happy. The choices are independent, as you're looking only at absolute values, that cannot be changed by changing sings.
This is obviously not a proof (what happens to elements of greater absolute value) , and just an idea off the top of my head. But knowing you, you must have already figured this out. This is for others who haven't. :D
EDIT : I didn't see the link to the comment above. Excuse my carelessness.