problem https://www.codechef.com/problems/INSOMA3
Can anyone explain easy approach to solve this problem in detail by giving examples?
hi @pandey_96
see the problem is with that heights that are after their desired position(i.e. their position in the sorted array) and no of disorder pairs is the difference of these two indexes. so, if we know the actual position of every index in sorted array then we are done!
example : 1 5 6 2 3
let’s sort it : 1 2 3 5 6
therefore the positions in original array are : (1 4 5 2 3) i.e. (position of 1, position of 5, …).
original array : 1 2 3 4 5
in sorted array : 1 4 5 2 3
therefore disorder position is at position 4 and position 5(because all other position has greater index)
answer = (4 - 2) + (5 - 3)
if you have doubt please feel free to ask 
1 Like