Counting number of inversions

Question

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 Weight_i is the weight of luggage of i^th friend carried by Puchi on i^th 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 i^th line contains i^th integer, which represents Weight_i.

Output:
Output exactly T lines. Each line contains N integer separated by a space, where i^th 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 <= 10⁴ 1<= Weight_i <= 10⁶

Subtask 2: 1 <= T <= 10 1<= N <= 10⁵ 1<= Weight_i <= 10⁶

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 {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));     
        int T=Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
          int N=Integer.parseInt(br.readLine().trim());
          StringBuilder ans=new StringBuilder();

          int arr[]=new int[N];
          int copy[]=new int[N];
          for(int i=0;i<N;i++)
          {
              arr[i]=Integer.parseInt(br.readLine().trim());
              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.

Answer 1

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; )
{
    int n = int.Parse(Console.ReadLine().Trim());
    var a = new int[n];

    for (int i = 0; i < n; ++i)
        a[i] = int.Parse(Console.ReadLine().Trim());

    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.

Answer 2

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.

Answer 3

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.