# Counting number of inversions

This is a HackerEarth Challenge Problem.

Question:
Puchi hates to carry luggage, but unfortunately he got a job to carry the luggage of his N friends in office. Each day, one of his N friends, gives him the luggage of a particular weight to carry. You will be given the weight of luggage of each friend in the array Weight, where Weighti is the weight of luggage of ith friend carried by Puchi on ith day. It is given that all the luggages carried by Puchi are distinct in their weights. As Prateek assigned this job to Puchi, so for each day, he wants to know the number of days in future when Puchi will have to carry the luggage , having weight less than the weight of luggage of current day. Please help Prateek for the same.

Input:
The first line contains a single integer T, denoting the number of test cases. In each test case, the following input will be present: First line contains an integer N, where N represents the number of friends. Next N line contains N integers, where ith line contains ith integer, which represents Weighti.

Output:
Output exactly T lines. Each line contains N integer separated by a space, where ith integer represents the number of luggage of future, which are less than the weight of luggage of the current day.

Constraints:

Subtask 1: 1 <= T <= 30 1<= N <= 104 1<= Weighti <= 106

Subtask 2: 1 <= T <= 10 1<= N <= 105 1<= Weighti <= 106

I have used merge sort to calculate the inversions:

public class Puchi_and_Luggage {
static long invfreq[]=new long[1000001];

public static void main(String[] args) throws NumberFormatException, IOException {

while(T-->0)
{
StringBuilder ans=new StringBuilder();

int arr[]=new int[N];
int copy[]=new int[N];
for(int i=0;i<N;i++)
{
copy[i]=arr[i];
invfreq[arr[i]]=0l;
}

mergesort(arr,0,N-1);
for(int i=0;i<N;i++)
{
ans.append(invfreq[copy[i]]+" ");
}
System.out.println(ans);
}

}

private static void mergesort(int[] arr, int i, int j) {

int mid=0;

if(i<j)
{
mid=(i+j)/2;
mergesort(arr,i,mid);
mergesort(arr,mid+1,j);
merge(arr,i,mid,j);

}

}

private static void merge(int[] arr, int i, int mid, int j) {

int temp[]=new int[arr.length];
int l=i;
int r=j;
int m=mid+1;
int k=l;
long inv=0l;
while(l<=mid && m<=r)
{
if(arr[l]<=arr[m])
{
temp[k]=arr[l];
invfreq[temp[k]]+=inv;
k++;
l++;
}
else
{
temp[k]=arr[m];
k++;
m++;
inv++;

}

}
while(l<=mid){
temp[k]=arr[l];
invfreq[temp[k]]+=inv;
k++;
l++;
}
while(m<=r){
temp[k]=arr[m];
k++;
m++;
}

for(int i1=i;i1<=j;i1++){
arr[i1]=temp[i1];
//System.out.print(arr[i1]+" ");
}

}

}


But my code is giving Time Limit Exceeded for test cases with large input files.

• This post might help you. It does the counting of inversions inside the merge sort methods. – TheCoffeeCup Jul 31 '15 at 16:29

Short answer: creating - and garbage collecting - N arrays of size N takes some time, even if operator new[] has been tuned for exceptional performance (as is the case for Java and C#).

int temp[]=new int[arr.length];


Long answer: a detailed treatment of all the coding/performance sins inherent in the code offered for review would fill many pages. However, I'm leaving that for someone else and instead I'll focus only on the algorithmics, in a language-agnostic way.

Throwing needlessly complicated technology at a practice problem can be educational, if only to drive the lesson home that the technology in question is in fact not a good match for the problem and that other solutions require less effort. Hence, if a problem listed under ‘merge sort’ then one ought to also solve it via merge sorting, but the first call should always be the simplest solution that promises to do the job.

In this case, that simplest solution is using a Fenwick tree to count inversions. No fuss, no muss, solution (C#) accepted with 1.19 s combined time for all test files.

const int MAX_VALUE = 1000000;

for (int t = int.Parse(Console.ReadLine().Trim()); t-- > 0; )
{
var a = new int[n];

for (int i = 0; i < n; ++i)

var fenwick = new int[1 + MAX_VALUE];
var result = new int[n];

for (int i = n - 1; i >= 0; --i)
{
int a_i = a[i], inversions = 0;

for (int j = a_i; j > 0; j -= j & -j)
inversions += fenwick[j];

for (int j = a_i; j <= MAX_VALUE; j += j & -j)
++fenwick[j];

result[i] = inversions;
}

Console.WriteLine(string.Join(" ", result));
}


Compare this to the reams of code necessary for the merge sorting approach.

According to the problem constraints, values can go ten times as high as indices (limit 10^6 instead of 10^5). This makes the Fenwick ten times as big as the biggest input array, increasing the average path lengths for the Fenwicking from not quite 9.5 to not quite 11.5. However, for small ranges such as these this inefficiency is negligible - the code is more than fast enough already.

For details on Fenwick trees see the Wikipedia article on Fenwicks and the related practice section on HackerEarth (which includes a tutorial; it's in the Data Structures section which you're supposed to work through before starting with Algorithms). As regards determining the average iteration counts for the Fenwick loops, I'd recommend doing a bit of Fenwicking with pen and paper (for a Fenwick of size 2^k it's k / 2 + 1).

As regards merge sorting: unlike Fenwicks, merge sorting does not give a flying meow about what the actual ranges of the input values are - all it does with the inputs is compare them. This makes the algorithm especially attractive when the value range diverges wildly from the value count. For example, Fenwicking 100000 longs would require sorting the inputs in order to ‘compress’ them to the range 1 to 100000, which requires O(N log N) of extra effort.

Merge sorting requires no such preprocessing, but since it destroys the original order of the values it requires extra effort for correlating the inversion counts thus found to the original inputs (e.g. the array copy[] in the original code). Also, it makes the code quite a bit more complicated than that using a Fenwick tree, and it would get hugely more complicated if the input values weren't guaranteed to be unique whereas the Fenwick couldn't care less about uniqueness.

Coding a top-down merge sort with recursive function calls - as opposed an iterative bottom-up version with nested loops - makes it more difficult to control certain aspects (e.g. optimal splitting instead of simple halving) and it makes it even more difficult to make sorted ranges end up precisely where they're needed, instead of resorting to redundant copying of values.

However, the recursive version has somewhat better cache locality and in any case it is more than fast enough for this problem, regardless of the redundant copying. In my benchmarks it took little more than twice as long as the simpler Fenwick and was only marginally slower than an iterative version (124 ms for 10^6 values recursive vs 110 ms iterative and 44 ms Fenwick). In a coding challenge it might pay to keep the differences in mind, but not for this simple practice problem.

Hence the only algorithmic fix required here is using a pre-allocated temp array large enough to hold the largest input. That's all.

Make sure your program does what it is supposed to. There are some obvious confusions. Most likely it does not fail for the reason you think.

• what confusions and reasons are you referring to? – aakansha Jul 21 '15 at 14:53
• I seem to have some problems with my reasoning as of late.. but it looks like you sort arr but print copy. – mncl Jul 23 '15 at 7:57
• Also I would recommend cleaning up todo markers. – mncl Jul 23 '15 at 7:58
• As the question says to print the number of inversions for each element so copy stores the original position of elements so that inversions are printed in order. – aakansha Jul 23 '15 at 10:59
• Apart from being not helpful in any way, this 'answer' is total nonsense. The confusion is only in the mind of mnci, who obviously couldn't even be arsed to read the problem statement and to put the most cursory effort into understanding the OP's code. Any solution that uses merge sorting for counting inversions must necessarily have a means of correlating the resulting inversion counts back to the original input positions, so that each count gets printed at the position where it belongs. The OP named the array copy[] since a copy of the input array works because of the uniqueness contraint. – DarthGizka Sep 3 '16 at 12:18
import java.io.*;
import java.util.*;

class Puchi{

public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int count=0;
int n=sc.nextInt();
int a[]=new int[n];
for(int j=0;j<n;j++){
a[j]=sc.nextInt();
}
for(int k=0;k<n;k++){
count=0;
for(int m=k+1;m<n;m++){
if(a[k]>a[m]){
count++;

}
}
System.out.print(count+" ");

}

}
}
}


output: 1 0 1 0

But when trying to submit it's getting partially accepted.

• According to the help page at codereview.stackexchange.com/help/how-to-answer, you should try to address any thing in the users code that can be improved, not post alternate answers. In this case the formatting of your code can use improvement as well, the 2 imports should be on separate lines so they are clearer. – pacmaninbw Sep 1 '16 at 14:27
• @pacmaninbw They were on separate lines. They just weren't indented, so they didn't appear with code formatting. The real problem seems to be that this is broken code (partially accepted). And this seems more like a question than an answer. – mdfst13 Sep 1 '16 at 14:57
• @mdfst13 Are you saying I should flag it? – pacmaninbw Sep 1 '16 at 15:01
• If you want. I was mostly aiming that part at the OP -- I just didn't break things up into two comments. Note that a post could be flagged for being a code dump. My point is that this went beyond just that problem. – mdfst13 Sep 1 '16 at 16:17
• JFTR: this submission got only partially accepted because it times out on non-trivial inputs. It is a straight transcription of the problem statement, O(N^2) and hence not fixable (unlike the OP's code which is O(N log N) and suffered timeouts only because of a minor mistake). – DarthGizka Sep 4 '16 at 5:04