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
d_sm:
20200309 07:36:55
accepted in one submission , make lhs and rhs two array and then sort ,and search for each lhs the upper and lower bound in rhs..... 

fardin_abir:
20200227 19:30:05
holding the meet in the middle concept, first tried with unordered map but got TLE, then tried with two pointers and got AC 

bhavikag:
20200131 12:39:10
Has anybody done this in java?


apurv_19:
20191226 12:52:53
ABCDEF...a similar problem to this one...


iamfahim:
20191103 19:50:54
Using STL equal_range 

nadstratosfer:
20190724 04:56:34
Sadly, some datasets have nearly no zerosumming quadruplets, rendering a large assortment of possible optimizations useless. Most people commenting here seem to confuse optimization with not doing stupid stuff, and noone claiming to have done it in O(n^2) has runtime to prove it. I'm still bothered to find the efficient approach candide hinted to, but other than that the problem seems like a waste of time after getting the green bar. 

yashranjan74:
20190621 11:18:25
Just use equal range in place of unordered_map. Although the complexity was better using unordered_map but equal_range get AC whereas unordered_map gave TLE. 

harry_shit:
20190604 12:10:34
tle for O(n*n) also,using unordered map


hetp111:
20190601 09:02:24
How did 1st ranker got it in 0.01sec? mine took 2+sec with O(n*n*log(n))... Last edit: 20190601 09:04:09 

abhinav_jain02:
20190518 08:28:58
Note that equal elements in a list are considered to be distinct 
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 