# Inversion Count Problem

I am new with Graph Theory. 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.

Hey, well inversion count is a common problem, you can solve it using merge sort and BIT( binary index tree )

And also BIT Using bit

1 Like

Bro can you explain me how the Divide and Conquer algorithm is used in this problem?

Did you check out above link, there is a good explanation for divide and conquer! if you donâ€™t get it, Iâ€™ll try to explain

@dracowane I was busy understanding the code. I am able to get it, but in the last stage where the sub-arrays are merged, why we are copying the remaining elements of left sub-array? and what is meant by â€śremaining elemnts of left sub-arrayâ€ť ??

this logic is simple of merge sort, like lets take example of this array :- 1 2 5 6 3 3 3 3

at second last step

left array is 1 2 5 6 and right array is 3 3 3 3

weâ€™ll put 1 from left array to temp
temp = [1]; left = [2,5,6] and right is [3,3,3,3];
then weâ€™ll compare 2 and 3, temp = [1,2] ; left = [5,6]; right [3,3,3,3]
now next 4 iterations will be from right sub array so, temp = [1,2,3,3,3,3]
now left subarray is [5,6] and right subarray is empty, main loop will break
. weâ€™ll now add remaining elements of left subarray as they are sorted we can add at the end

2 Likes

go through this link hope it help uâ€¦happy codingâ€¦

yes thanks @dracowane I got It. Thanks For the help.

@dracowane I am pretty much understood with the concept, but wrote a peice of code, it is running on all test cases, but still giving WA.

http://ideone.com/e.js/WGc0tP

arrey, you are making one mistake. check n contraints, it 210^5 so, if array is in descending orderâ€¦ answer will be 410^10 (approx) which will not fit in long. change long to long long, got an ac with same code. http://pastebin.com/jmaM070d

1 Like

oops! Right bro! GOt AC! Learnt Divide and Conquer! Thanks a Lot!

//