Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя smartin

Inversion Count
Автор smartin, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить