2013
11-12

4 Values whose Sum is 0

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .

For each input file, your program has to write the number quadruplets whose sum is zero.

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


5


Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

//* @author: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
int a=Integer.parseInt(s);
int[] t1=new int[a];
int[] t2=new int[a];
int[] t3=new int[a];
int[] t4=new int[a];
int[] t5=new int[a*a];
int[] t6=new int[a*a];
int abl=0,cdl=0;
String[] ss;
for(int i=0;i< a;i++)
{
t1[i]=Integer.parseInt(ss[0]);
t2[i]=Integer.parseInt(ss[1]);
t3[i]=Integer.parseInt(ss[2]);
t4[i]=Integer.parseInt(ss[3]);
}
for(int i=0;i< a;i++)
for(int j=0;j< a;j++)
{
t5[abl++]=t1[i]+t2[j];
t6[cdl++]=t3[i]+t4[j];
}
Arrays.sort(t5);
Arrays.sort(t6);
int l1=0,l2=cdl-1,ans=0,k,m;
while(l1< abl&&l2>-1)
{
if(t5[l1]+t6[l2]==0){
k=0;
m=0;
for(int i=l1;i< abl;i++)
if(t5[l1]!=t5[i]) break;
else k++;
l1+=k;
for(int i=l2;i>-1;i--)
if(t6[l2]!=t6[i]) break;
else m++;
l2-=m;
ans+=k*m;
}
else if(t5[l1]+t6[l2]>0) l2--;
else l1++;
}
System.out.println(ans);
}
}