dhruvmullick's blog

Triple Inversion?

By dhruvmullick, history, 9 years ago, In English

I was doing TRIPINV. The problem requires us to find triplets with ai > aj > ak for i < j < k.

I was thinking of using 2 BITs for the same, and use a (Sum) C (2), and of sum of (SameElements) C (2). But I can't maintain the order of elements this way. For instance, in A[1..6] = 3 2 1 3 2 1 My program would identify A[2],A[5],A[6] as a triplet too.

Can anyone help me out?

PS: C denotes Combination

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think that we simply need to calculate for every index j, how many indices i < j satisfy inequality ai > aj (lets denote result as A), how many indices k > j satisfy inequality aj > ak (lets denote result as B), and add to answer A·B. We can calculate A, adding numbers to BIT in decreasing order, and for calculating B we add numbers to another BIT in increasing order.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Building the 2nd BIT in the reverse order was very clever. Thank you!

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Let's use 2 BITs. First BIT T1[x] will count number of elements greater or equal than x, while second BIT T2[x] will count number of inversions i, j (i < j and A[i] > A[j]) such that A[j] >  = x, that is number of inversions with second element greater or equal to x. Then after reading a number n, we query the first bit for n + 1 and perform increase operation to the second BIT at n with that value. Finally we query second BIT for n + 1 and add that value to our final answer.

Code is very short and pretty -> C++ Code

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a similar problem on CF:

http://codeforces.com/problemset/problem/61/E

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another similar problem.

→ Reply