Find the number of quadraples (a,b,c,d) from 4 respective arrays such that a+b+c+d=0

Question

Given four lists of numbers, calculate how many ways there are to choose one element from each to get a sum of zero.

The input is given on stdin, first the length of all lists n, then n tuples containing an element from each, like this:

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

The task on SPOJ is here.

 #include <cstdio>
 #include <algorithm>
 using namespace std;
 #define MAX 10000001

    int arx[MAX];
    int ary[MAX];

     int main(){
     int n;scanf("%d",&n);
     int tmp1[n],tmp2[n],tmp3[n],tmp4[n];
     int n2=n*n;

     for(int i=0;i<n;i++)
        scanf("%d%d%d%d",&tmp1[i],&tmp2[i],&tmp3[i],&tmp4[i]);

     int count=0;
     for(int i=0;i<n;i++)
     {
        for(int j=0;j<n;j++)
        {
        arx[count]=tmp1[i]+tmp2[j];
        ary[count]=tmp3[i]+tmp4[j];
        count++;
        }
     }

     sort(arx,arx+n2);
     sort(ary,ary+n2);

     long long sum=0;

     for(int i=0;i<n2;i++)
     {   int key=-arx[i];
         int low1=0,high1=n2-1;
         while(low1<=high1)
      {
             int mid=(low1+high1)/2;
             if(ary[mid]<key)low1=mid+1;
             else high1=mid-1;
      }

         if(low1<n2&&ary[low1]==key)
         {
           int low2=0,high2=n2-1;
           while(low2<=high2)
           {
             int mid=(low2+high2)/2;
             if(ary[mid]>key)high2=mid-1;
             else low2=mid+1;
           }

         if(high2>=0&&ary[high2]==key)
         sum+=high2-low1+1;
        }

     }
     printf("%lld",sum);
     printf("\n");
    return 0;
}

I made an array(arx[]) to store all possible a+b and an array(ary[]) to store all possible c+d; Then I used binary-search to find no of occurrences of each (-)element of arx[] in ary[]. I narrowly passed the time limit.

I suspect there's a better way to do it.

Answer 1

Well, you are going about it wrong.

As a wise man once said: If in doubt, sort.

1. Read all four lists.
2. Sort them.
3. Calculate the smallest and biggest value which can be compensated by the lists after the first m.

4. Iterate over those elements of the first list which can be compensated according to 3.

   5. Iterate over those elements of the second list which can be compensated according to 3, keeping in mind your choice for 4.

      6. Repeat step 5 for the third list, keeping in mind your choice for 5.

         7. Add the number of elements in the last list which can compensate the previous choices to the result.

---

Aside from that:

• Your indentation is very haphazard.
• using namespace std; is a good way to shoot yourself in your own foot, and makes any toolchain-change unpredictable.
• Dynamically-sized automatic arrays aren't C++, they are C99+. Try for std::vector or such.
• return 0; is implicit for main in C++.

_{My own solution, which can still easily be optimized further. Don't peek before you have it.}