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
Input
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 2^{28} ) that belong respectively to A, B, C and D .
(Edited: n <= 2500)
Output
Output should be printed on a single line.
Example
Input: 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 Output: 5
hide comments
Bhuvnesh Jain:
20150722 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... 

Hussein Aassem:
20150708 02:00:51
a testcase must be added with all the 4000 the same number to overflow char .... check my submission Last edit: 20150708 02:02:50 

Liquid_Science:
20150701 15:48:11
Nearly Impossible in java :( 

kshitij tripathi:
20150630 14:47:43
Nice Question..don't use Long Long int !! :D 

Varun Gambhir:
20150623 21:11:15
Ordered map in c++ gives TLE and unordered gives AC(after some optimisations). Finally AC. :D Last edit: 20150623 21:11:36 

sameer makker:
20150620 18:20:15
Can anybody explain why unordered_map fails here ?


Dhruv Mullick:
20150620 16:01:50
Optimisations needed. 

Ayur Jain:
20150620 10:55:09
Passes in O(n^2logn). Don't use STLs. 

sujit yadav:
20150619 00:31:13
take 2 pointer array in pair stl ....learn a lot .. thanks !!! :) 

bsaha205:
20150616 22:13:57
can you tell the tenth case??

Added by:  Abhilash I 
Date:  20070206 
Time limit:  1.419s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  South western 0506 