Inversion Count Problem

graph
union-find

#1

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:


#2

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


#3

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


#4

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


#5

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


#6

Ok, let me read it! :slight_smile:


#7

@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” ??


#8

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


#9

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


#10

@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


#11

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


#12

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