Why does this solution work?

Revision en1, by SirirNicheBirirDokan, 2017-09-11 21:11:12

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?

Tags #problem, correct solution, why, godblessamerica

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SirirNicheBirirDokan 2017-09-11 21:11:12 548 Initial revision (published)