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

Автор mochow, 11 лет назад, По-английски

There is this classical problem of counting number of inversions in an array.

Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. 

This problem can be found here.

I found this problem on CF where we need to find number of such triples (i,j,k) such that i<j<k and A[i]>A[j]>A[k].

I solved both of the problems using BIT.

For the second problem, I counted number of numbers greater than A[i] at its left (left[i]) and number of numbers less than A[i] at its right (right[i]). So the output is summation of right[i]*left[i] for all i from 0 to n-1.

Now I have a question, what if the problem is counting inversions of length N? It means we need to find number of such combinations (i,j,k,...) such that i<j<k<... and A[i]>A[j]>A[k]>...

What should be a generalized solution for this problem?

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

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

You're just finding the number of decreasing/increasing sub-sequences of length N which is a known problem on spoj

it can be solved using dp, let dp[i][j] means the number of increasing sub-sequences of length j that ends in i so we have to formula to compute the dp:

dp[i][j] = sum for each index k such that k < i and A[k] < A[i] (dp[k][j - 1])

this is O(N2 * K). however, using BIT/segment tree can be done in O(N * KlogN)

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

There are also solution using mergesort.

Problem in OJ: Timus

Solutions:

Mergesort

BIT

Policy based data structures