CODEWITHSUNDEEP
algorithmmergesort
noob
noob

Reputation: 85

Number of big inversions in an array

I am working on a problem:

Given an array, A[1,2,...,n], the problem is to count the number of big-inversion pairs. A big-inversion is a pair of indices, (i, j) such that: 2.i < j and A[i] > 2.A[j].

We need to solve this in O(nlogn) time. I have been stuck on this for a while now and have no clues on how to respect the index (2i < j) constraint. If I use something like merge-sort, then, by the sorting of the two halves, I will lose information of which indices in the first half, satisfy, 2i < j and I always end up having O(n^2) time in the merge step. I was also thinking to maybe modify the array like double the indices and then merge the two halves according to their indices but have no progress with that too. I would really appreciate if someone could give ideas. Thanks!

Upvotes: 1

Views: 401

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23945

I'm not sure about divide and conquer, but we could start at index n / 2 and iterate down. As we iterate, insert the elements that satisfy their index being greater than 2*i into an order-statistic tree. Each such element would be inserted once as the tree grows. Report for each element at index i how many elements in the tree are lower than A[i] / 2.

Upvotes: 2

Related Questions