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

Count number of arrays with k-inversions
Автор aakarshmadhavan, история, 6 лет назад, По-английски

I'm trying to come up with a recursive solution for this problem but I haven't been able to so far. Any advice/pointers here?

I tried 0-1 knapsack style but there is an issue with backtracking the array.

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

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

It appears that the statement is actually asking for the number of permutations of 1... n with k inversions. If In(t) is the number of permutations of size n with t inversions, then . This recurrence can be calculated in O(nt) using prefix sums on In.

→ Ответить