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 (6)
| 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.net/problemset/problem/61/E

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

Yet another similar problem.

→ Reply
»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

You can use two segment tree for solving it in O(nlogn), for tracking the number of elements smaller to the right and larger to the left of any particular element then basically you have to add all the left[i]*right[i]

→ Reply