Suggestions for optimization of code to pass TLE on SPOJ

Question

I'm trying to solve a problem which is something like this:

I'm given n numbers (1<=n<=10^5).I have to write the sum of all numbers on its left which are smaller than the current number and repeat the process for all n numbers.Then I have to find the sum of all previously obtained sum's.(Each number N,0<=N<=10^6).

For example,

1 5 3 6 4
less1 less5 less3 less6 less4
 (0) + (1) + (1)+(1+5+3)+(1+3)
  0  +  1  +  1  +  9  +  4
= 15

A trivial solution for this problem will be to run two loops and for each of the given number find sum of all the numbers less than that number and finally give the sum of those sum's as output.The time complexity is O(n^2).

I think a better O(nlogn) solution for this problem using Binary Indexed Tree(Fenwick Tree). For each number I'll add each of the number in a global array a and perform two obvious operations of BIT.I think the time complexity of this algorithm is O(nlogn) which if true is obviously better than the previous O(n^2).

I have implemented the code in C++.

#include<iostream>
#include<cstdio>

using namespace std;

#define max 1000001

long int a[max];

void add(long int v,int idx){
while(idx<max){
    a[idx] += v;
    idx += (idx & -idx);
}
}

long int sum(int idx){
long int s=0;
while(idx>0){
    s += a[idx];
    idx -= (idx & -idx);
}
return s;
 }

 int main()
 {
int t;
scanf("%d",&t);
for(int w=0;w<t;w++){
    int n;
    scanf("%d",&n);

    for(int i=0;i<max;i++)
        a[i]=0;

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

    long long res=0;

    for(int i=0;i<n;i++){
        if(arr[i]!=0){
           add(arr[i],arr[i]);
           res += (sum(arr[i]-1));
                     }  
    }

    printf("%lld\n",res);
}

return 0;
}

I have two questions:

First, am I doing it correct? / Is my logic correct?

Second, if I'm right about the time complexity to be O(nlogn) then why does it run slow? Can you help me with any further optimizations?

Got Accepted with 1.41 seconds.At same time I have updated my finally accepted code.Any suggestion for optimization ?

Based on the comments I tried my own function for faster I/O but still it's not going my way.This is my function for fast I/O :

 inline int read(){
char c=getchar_unlocked();
int n=0;
while(!(c>='0' && c<='9'))
    c=getchar_unlocked();

while(c>='0' && c<='9'){
    n=n*10 + (c-'0');
    c=getchar_unlocked();   
}
return n;
 }

This is the link to the problem :

http://www.spoj.pl/problems/DCEPC206/

If there is anyone who is abled to solve it,please let me know. Thanks.

Answer 1

I think your approach is a good one. I've played around with this a wee bit and haven't come up with anything generally better than what you have.

There are a couple of bugs in your code though. There are a few places suffering from integer overflow. You should change to:

long long a[max];

and

long long sum(int idx){
long long s=0;

The more apparent bug is that you're summing numbers which are less than or equal to the current number. To fix this issue, you could add a second global array for tracking the count of each value:

int b[max];
...
...
    for(int i=0;i<max;i++)
        a[i]=b[i]=0;
    ...
    ...
        res += (sum(idx)-(++b[idx]*val));

There may be a more efficient way to fix that bug, but overall it still seems like a fast solution.

Answer 2

Here is another approach: the problem is similar to counting inversions, except you have to sum the elements responsible for generating inversions. We can solve this using merge sort. Modify the merge function like this:

merge(left, middle, right, array)
  temp = new array
  k = 0, i = left, j = middle + 1

  while i <= middle and j <= right
    if array[i] < array[j]
      temp[k++] = array[i]
      // array[i] is also smaller than all array[j+1], ..., array[right]
      globalSum += array[i] * (right - j + 1)
    else
      // same as the classical function

Intuitively, I would say a recursive mergesort is slower than a BIT solution, but who knows? Give it a try.

Edit: This gets AC:

    #include<stdio.h>
#include <iostream>

using namespace std;

#define max 100001

int n;
long long res = 0;

int temp[max];
int arr[max];
void merge(int left, int m, int right)
{
    int k = 0;
    int i = left, j = m + 1;
    while (i <= m && j <= right)
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i];
            res += (long long)(right - j + 1) * arr[i++];
        }
        else
            temp[k++] = arr[j++];

    while (j <= right)
        temp[k++] = arr[j++];
    while (i <= m)
        temp[k++] = arr[i++];

    for (int i = 0; i < k; ++i)
        arr[left + i] = temp[i];
}

void sort(int left, int right)
{
    if (left < right)
    {
        int m = left + (right - left) / 2;
        sort(left, m);
        sort(m + 1, right);
        merge(left, m, right);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    for(int w=0;w<t;w++)
    {
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);

        res=0;
        sort(0, n - 1);

        printf("%lld\n",res);
    }

    return 0;
}