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.

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! :slight_smile:

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

check this link for merge sort answer Mergesort_inversioncount

And also BIT Using bit

1 Like

@bradleyhttp://rameshchandranitk.blogspot.in/2015/06/count-number-of-inversion.html
go through this link hope it help u…happy coding…

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

Ok, let me read it! :slight_smile:

@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

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

@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! :stuck_out_tongue: Right bro! GOt AC! Learnt Divide and Conquer! Thanks a Lot!