bradley's blog

Inversion Count Problem
By bradley, history, 9 years ago, In English

I was doing well with SPOJ Problems, but due to some Problems, I am stuck with them. I am in the first year of my BTECH, but I am pretty much confident with the Ad-Hoc Problems. I am new with Graph Theory. I want to learn it.

Problem Link is this

Some one please make me understand the Problem. I have read about Trees, but not so much helped. Someone please be kind and answer. Thanks in Advance! :)

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

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

I don't think this has anything to do with graphs. It's a variation of merge sort. ( Divide and conquer).

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

Merge sort will do.I have also heard that this question can be done using Binary Indexed Trees.

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

    Can you please make me understand how it will be done by Merge Sort? antivenom

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

      Merge sort works by splitting the array in half, sorting those halves, and then merging them together. In that merge, whenever the current minimum element is on the second half, it will create inversions with all the remaining elements from the first half.

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

This is simple BIT problem.First add that number in BIT ( update position bit[a[i]]). For each position i you should find how many numbers left of it are bigger ( you find how many numbers are smaller or equal with BIT) and add on answer i-(that number). Also number should be long long ...

→ Reply