Advertisement blocking software were detected ;( Please add this webpage to whitelist.

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 .


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
ranit: 2015-11-23 08:29:36

There is a problem. I submitted the same code twice once give me TLE other give AC. It's really funny.

Last edit: 2015-11-23 08:29:55
Lai Manh Tuan: 2015-11-03 08:43:56

Got AC by using STL (with some optimizations).
But I hate this kind of problems. Time limit is too strict. You spend more time to optimize your code than to think of algorithms.

Keshav Reddy: 2015-11-02 22:10:45

Why does std::unordered_map give TLE?

Last edit: 2015-11-02 22:10:59
xashru: 2015-10-02 01:31:08

why does using
ios_base::sync_with_stdio(false); cin.tie(0);
give WA but omitting it gets AC?

Last edit: 2015-10-02 01:31:32
ratedx: 2015-09-25 09:04:36

@Varun Gambhir both ordered and unordered are giving tle in my case!
What is your time complexity?

kobe24: 2015-09-05 00:30:06

Last edit: 2015-09-05 00:52:55
earner: 2015-08-27 18:12:06

can anyone tell why the 10th test case is giving wrong answer?

shaky99: 2015-08-11 12:17:08

10th test case gives WA.. can any one tell why??

Last edit: 2015-08-11 12:18:07
Abhinandan Agarwal: 2015-08-04 21:52:43

Use dynamic allocation of array in case you are using binary search approach.

Bhuvnesh Jain: 2015-07-22 21:44:57

brilliant question with even brilliant test cases. knew that qsort() is slower than sort() in worst case complexity but never had test cases which led me to change qsort to sort.... but here CAUTION: use only sort or your own implementation of merge/heap sort... do not use quick sort at all...

Added by:Abhilash I
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: ERL JS NODEJS PERL 6
Resource:South western 05-06