Would anybody help me understand the case where my logic is not holding true?
Make ‘k’ , ‘s1’, ‘s2’, ‘ans’ as long variable. Might help you
Used long long…check the macros.
Issue isn’t with the size of output, I guess this logic fails for certain cases hence the WA.But I can’t seem to work out the fail case.
I used unsigned long, was absolutely sufficient.
The solutions is this:
x = ( v * (K+1) * K + w * K * (K-1) ) / 2
v = number of inversions in the number sequence
w = number of non-inversions in the number sequence (and two equal A_i, A_j are not non-inversions)
Runtime of my algorithm (in C) was 0.02sec
The important fact is that inversions turn into non-inversions when the sequence is repeated. Then the formula can easily be derived.