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!

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

@bradleyâ€¦ALGORITHM AND CODE: Count Number of Inversion

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

@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.

@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 2*10^5 so, if array is in descending orderâ€¦ answer will be 4*10^10 (approx) which will not fit in long. change long to long long, got an ac with same code. Inversion count - Pastebin.com

1 Like

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