insoma3 problem need help

help
,
1

Can anyone give me some hint regarding this ques

Thanks in advance…

2

You have to find the total no. of pairs (i,j) such that a[i] > a[j] and i < j. This pair is called an inversion. There are many ways to find inversions you can read about them online. Most common ways are using BIT and mergesort.

2 Likes
3

@shuvam07: This question is nothing but to count number of inversions in a given array. You can implement it using divide and conquer approach. That is let me try it to explain by taking an example

  • let input be 1 3 5 2 4 6
  • use divide and conquer approach.
  • while merging two sub arrays: 1 3 5 and 2 4 6
  • in 1st sub array pointer will be on 1 and in 2nd pointer will be on 2
  • compare 1 and 2 as 1<2 you will copy 1 to a temp array and increment pointer to 3
  • now compare 3 and 2 as 3>2 here inversions occur, that is (3,2) and (5,2) because the sub-arrays will be sorted in divide and conquer approach. now pointer in right sub array will be incremented to 4
  • now compare 3 and 4 as 3<4 no inversions ,increment pointer to 5
  • compare 5 and 4 as 5>4 again inversion occurs, that is (5,4) and that’s all because 5 is the last element in left sub array. and increment pointer to 6
  • now compare 5 and 6 as 5<6 no inversions both pointers reaches end of sub-array’s.
  • So our problem is over and total number of inversions are 3, for this input, like wise you can check to our sample input given in codechef also.

I hope you understand this logic. In addition to this I am attaching my


[1] for further clarity with comments where ever needed. If this is useful don't forget to accept and upvote my answer. still if you have any doubts try to google it as **count number of inversions in given array using divide and conquer method** and open link in geeksforgeeks because it provides with a solved example :)

 


  [1]: https://ideone.com/gneGxE
2 Likes