SPOJ "It's a murder!" challenge

Question

I wrote a solution for SPOJ "It's a murder!". I'm exceeding the time limit even after n log(n) solution and fast I/O.

Given a list of numbers, I need to calculate the sum of the sum of the previously encountered numbers that are smaller than the current number. For example, given 1 5 3 6 4, the answer is

(0) + (1) + (1) + (1 + 5 + 3) + (1 + 3) = 15

My code has complexity n log(n) and is pretty much similar to how we calculate the number of inversions. The function merge in the code below merges two sorted arrays and the function merge_sort is the basic call to merge sort procedure. The array sum1 stores the cumulative sum in array1 of elements whose index is strictly less less that current index . The variable ans stores the final answer. How can I make my code more efficient ?

#include <bits/stdc++.h>
using namespace std ; 

//Declaration of global variables
int array[100000] , array1[100000] , array2[100000]   ; 
long long int sum1[100000] ;
long long int ans ; 

void merge_sort(int left , int right) ; 
void merge(int left , int mid , int right) ; 

int main()
{
    int t,counter,n,i ;

    // t is the number of testcases
    scanf("%d",&t) ;  

    for(counter=0;counter<t;counter++)
    {
        // n is the number of elements in the array
        scanf("%d",&n) ; 

        for(i=0;i<n;i++)
        {
            scanf("%d",&array[i]) ;

        }

        // ans hold the final answer and so it is initialized to 0 for every test case
        ans =0 ; 
        merge_sort(0 , n-1) ; 


        printf("%lld\n",ans );

    } 

}

void merge(int left , int mid , int right)
{
    int  index , index1 , index2 ;

     // array1 is used to store the elements from left to mid
     // array2 is used to store the elemetns from mid+1 to right
     // sum1 holds the sum of elements whose index is less than current index in array1 so that sum1[0] is always 0 .       

     // sum1 is initialised to 0
     memset(sum1,0,sizeof(sum1)) ; 

    // copying into array1 from left to mid 
    index1 = 0 ; 
    for(index=left;index<mid+1;index++)
    {
        if(index1!=0)
        {
            sum1[index1] = sum1[index1-1] + array1[index1-1] ; 
        }

        array1[index1] = array[index] ; 
        index1++ ; 
    } 

    // copying into array2 from mid+1 to right
    index2 = 0;
    for(index=mid+1;index<right+1;index++)
    {

        array2[index2] = array[index] ; 
        index2++ ; 
    }


    //merging the two arrays array1 and array2 and adding to the variable  ans array[index1] if array1[index1] < array2[index2]
    index1 = 0 ; 
    index2 = 0 ; 
    index = left ; 
    while((index1<mid-left+1)&&(index2<right-mid))
    {
        if(array1[index1]<array2[index2])
        {

            array[index] = array1[index1] ; 
            index++ ; 
            index1++ ; 
        }
        else if(array1[index1]>=array2[index2])
        {
            ans = ans + sum1[index1];
            array[index] = array2[index2] ; 
            index++ ; 
            index2++ ; 
        }

    }

    if(index1<mid-left+1)
    {
        while(index1<mid-left+1)
        {
            array[index] = array1[index1] ; 
            index++ ; 
            index1++ ; 
        }
    }
    else if(index2<right-mid)
    {
        while(index2<right-mid)
        {
            ans = ans + sum1[index1-1] + array1[index1-1];
            array[index] = array2[index2] ; 
            index++ ; 
            index2++ ; 
        }
    }
}

void merge_sort(int left , int right)
{
    // Typical merge sort procedure
    if(left==right)
    {

    }
    else
    {
        int mid = (left+right)/2 ; 
        merge_sort(left , mid) ; 
        merge_sort(mid+1 , right) ; 
        merge(left , mid , right) ; 
    }
}

Answer 1

Your main issue is this line:

 memset(sum1,0,sizeof(sum1)) ;

The whole array is being initialized to zero, even if you are only dealing with a range of one element. You really only need to initialize the first element:

sum1[0] = 0; // initialize here

// copying into array1 from left to mid 
index1 = 0 ;
for(index=left;index<mid+1;index++)
{
    if(index1!=0)
    {
        sum1[index1] = sum1[index1-1] + array1[index1-1] ;
    }

The rest is already assigned proper values.

Answer 2

I'm using the same basic approach - merge sorting to get the inversions handed on a platter and adding them to compute an excess - but even the simplest rendering processes a random input vector of 100,000 values in 10 milliseconds (and in C# at that). That would make it 100 ms for a worst-case input file of 10 times 100,000 values. It would be really helpful if you gave some benchmarks, to have something to compare against. I/O code and processing code should be benched separately, just in case it isn't the processing code that's slowing you down.

Also, perhaps it would be easier if you started with a simpler rendering of the algorithm, since even the simplest version of merge sort is more than fast enough for the small sizes involved here. Even if it weren't fast enough it would still give you a reference for testing optimised versions against (and a performance baseline).

For example, here's the prototype that I used for studying the algorithm (I'm prototyping and Eulering in C# using the free LINQPad, because there I get much more mileage much faster than with cumbersome, bureaucratic C++ and its cumbersome, unwieldy IDEs):

static long stair_sum (int[] v)
{
    long result = 0;
    int n = v.Length;
    var a = new int[n];
    var b = new int[n];
    var sum_from = new long[1 + n];  // for debugging and looking at things

    Array.Copy(v, a, n);

    for (int w = 1; w < n; w += w)
    {
        for (int beg = 0; beg < n; beg += w + w)
        {
            int mid = Math.Min(beg + w, n);
            int end = Math.Min(mid + w, n);

            long sum = 0;
            for (int i = mid; --i >= beg; )
                sum_from[i] = sum += a[i];

            sum_from[mid] = 0;

            for (int i = beg, j = mid, k = beg; k < end; ++k)
            {
                if (i < mid && (j >= end || a[i] < a[j]))
                {
                    b[k] = a[i++];
                }
                else
                {
                    b[k] = a[j++];

                    result -= sum_from[i];
                }
            }
        }

        var t = a;  a = b;  b = t;
    }

    long running_sum = 0;

    for (int i = 0; i < n; ++i)
    {
        result += running_sum;
        running_sum += v[i];
    }

    return result;
}

The merge sort code is the simplest and most compact rendering of the algorithm that I could find in my algorithm library (basically an unmangled and cleaned-up version of the code in the Wikipedia article on merge sort). The only additions for the stair sum thingy are the computation of the cumulative sum for the left hand run, from mid - 1 down to a given i, and of course the subtraction of the excess from the result.

As I said, this is unoptimised C# and intended for studying the algorithm. Even so it takes only 10 milliseconds for a maximum-size input vector. In C++ and with a bit of optimisation it should have a fair shot at the coveted '0.00s' timing on SPOJ.

The most marked difference to your code seems to be that I fill sum_from[] with exactly those values that I want from it, so that it can be used without additional computations. It makes the code a bit cleaner but the influence on performance should be infinitesimal; a good compiler might even be able the clean that up without your help.

But I found it extremely difficult to make any headway in studying your code, because of things like confusingly long anonymous variable names. index, index1, index2 make the code more difficult to read than i, i1, i2 or - preferrable - i, j, k or beg, mid, end. The use of global variables doesn't improve understandability either.

In any case I would strongly recommend using an iterative version of merge sort, since it helps keep things simple by avoiding the need for passing state across function boundaries.

The only real inefficiency I can see is the one first pointed out by Vaughn Cato though, i.e. clearing a huge array for each and every recursion step of the algorithm. With that gone your code should be plenty fast already.

For the proponents of O(n^2) double-loop solutions - like Dave P - here's a benchmark of the loopy code against the O(n log n) merge sort solution (still in C#) for input sizes from 10 to 100000:

       10:         7287646 in      0,3 ms ->             7287646 in      1,0 ms
      100:       641143546 in      0,0 ms ->           641143546 in      0,0 ms
     1000:     81819219824 in      1,3 ms ->         81819219824 in      0,1 ms
    10000:   8270659664159 in    123,0 ms ->       8270659664159 in      1,1 ms
   100000: 829794693613017 in 12.341,7 ms ->     829794693613017 in     10,6 ms