Hasnaine_'s blog

Sherlock and Inversion (with merge sort tree)
By Hasnaine_, history, 6 years ago, In English

Problem Link: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/sherlock-and-inversions/description/

The problem is about counting the number of inversion in a particular range(from L to R).

My approach: I used Mo's Algorithm here. And to calculate the add and remove function I used Merge Sort Tree. I was pretty sure it will pass the dataset of 5s. But somehow it gave TLE. Maybe miscalculated the complexity.

There is few solution available in the internet where I saw every of them solved it using Binary Indexed Tree. So, my question here is, if the problem will be solved using Merge Sort Tree or not after any kind of optimization. Or should I definitely use BIT. And if i do have to use BIT, then why?

My code: https://ideone.com/wPb0AC (You can skip the code though)

  • Vote: I like it
  • -5
  • Vote: I do not like it

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

Operations on mergesort tree are O(log2N) (with a generally not bad constant). Using Mo's, total complexity becomes O(N3 / 2log2N), so with N, Q = 105 you can expect  8.7 × 109 operations, which is quite unlikely to get AC :(

→ Reply