SUMFOUR - 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 ) belongs to 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 .

(Edited: n <= 2500)


Output should be printed on a single line.


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

hide comments
praval_singhal: 2016-05-31 17:32:29

@Abhilash why have you gave n=4000 when n*n<10000000. Isn't it misleading.

candide: 2016-04-25 10:33:17

Done in PyPy. No sort, no binary sort, only arrays. ABCDEF is very similar.
@praval_singhal: you are right, input size list doesn't exceed 2500

Last edit: 2016-06-25 09:28:24
Akshay Damle: 2016-04-12 23:17:17

AC in 1 go :D Try ABCDEF before this. Using vectors for the sums and upper_bound, lower_bound works.

wh1t3_r0s3: 2016-03-22 20:25:41

getting TLE on the 9th test case? what should i do?

nonushikhar: 2016-03-11 18:11:47

hint: sort() is faster than qsort()
syntax: #include <alogrithm>
std::sort(arr,arr+n) //n is size of array arr

prateek1985: 2016-02-24 12:06:40

n^2 logn in java is giving TLE !!

Rehas Mehar Kaur Sachdeva: 2016-01-08 12:29:57

Can someone please give a hint how to optimise unordered_map based solution, no long long int used, n^2logn algorithm, no cin cout used.....

cat_got_bored: 2016-01-01 20:18:12

while doing binary search remember that the value can appear multiple times.

cat_got_bored: 2016-01-01 20:10:00

I couldn't get AC with STL map anyhow .... even with optimizations :-(
Then used only arrays,and binary search and got AC!
Didn't know STL map is this slow

Last edit: 2016-01-01 20:13:07
SHIVEK SACKLECHA: 2015-12-27 21:39:58

Dont know why but long long gives a TLE and int gives an accepted solution! Strange.

Added by:Abhilash I
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:South western 05-06