Suggestions for optimizing the code for passing TLE on SPOJ

Question

I am trying to solve a problem that looks something like this:

I have been given n numbers (1 <= n <= 10 ^ 5). I need to write down the sum of all the numbers on the left that are less than the current number and repeat the process for all n numbers. Then I must find the sum of all previously received amounts. (Each number is N, 0 <= N <= 10 ^ 6).

For instance,

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 to this problem will be to start two cycles and for each given number to find the sum of all numbers less than this number, and finally, give the sum of these sums as an output. The complexity of time is O (n ^ 2).

I think the best O (nlogn) solution for this problem is using a binary indexed tree (Fenwick Tree). For each number, I will add each of the numbers to the global array a and perform two obvious BIT operations. I believe that the time complexity of this algorithm is O (nlogn), which, if true, is obviously better than the previous O (n ^ 2).

I 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 right? / Is my logic correct?

Secondly, if I'm right about O (nlogn) time complexity, then why is it running slowly? Can you help me with further optimizations?

Retrieved from 1.41 seconds. At the same time, I updated my final accepted code. Any suggestion for optimization?

Based on the comments, I tried my own function for faster I / O, but still it won't do me any good. This is my function for quick 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 decided to solve it, let me know. Thanks.

Answer 1

I think your approach is good. I played with this a bit, and did not come up with anything better than what you have.

There are several errors in your code. There are several places suffering from integer overflow. You must change to:

 long long a[max]; 

and

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

A more obvious mistake is that you add numbers that are less than or equal to the current number. To fix this problem, you can add a second global array to track the amount 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 this error, but overall it still seems like a quick fix.

Answer 2

Here's another approach: the problem is similar to counting inversions, except that you have to summarize the elements responsible for generating inversions. We can solve this using merge sort. Change the merge function as follows:

 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 that a recursive merge 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; }