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
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 = ; 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
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.
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. Inversion count - Pastebin.com
oops! Right bro! GOt AC! Learnt Divide and Conquer! Thanks a Lot!