Please read the new rule regarding the restriction on the use of AI tools. ×

smartin's blog

Inversion Count
By smartin, history, 9 years ago, In English

Given a list of elements, you can remove either left or right element and add this to a new list either as first element or last element. You have to do this to form a new list such that inversions are minimized. (inversion means l [i] > l [j] for i<j). How to approach this problem efficiently?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Maintain a DP on the array segments :

DP[i][j] = Best you can do when sub-array A(i..j) is still in the old line.
Notice that we can place A[i]/A[j] in the beginning/end of the new line.
Thus, we must consider all these cases in our DP.

[DP(i)(j) = min(DP[i + 1][j] + min(a, b), DP[i][j — 1] + min(c, d)) ]

Where,
a = number of elements lesser than A[i] in [0..i-1] U [j+1..N-1]
b = number of elements greater than A[i] in [0..i-1] U [j+1..N-1]
c = number of elements lesser than A[j] in [0..i-1] U [j+1..N-1]
d = number of elements greater than A[j] in [0..i-1] U [j+1..N-1]

Implementing this would result in complexity, but we can easily optimize this to by pre-computing some stuff for each index.

→ Reply