SirirNicheBirirDokan's blog

Why does this solution work?
By SirirNicheBirirDokan, history, 7 years ago, In English

Problem: 351E - Джефф и перестановка

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Click here and next time read comments below the editorial before asking such question.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply