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
wille_25: 2020-08-01 05:41:36

if you do ABCDEF problem first ...its is a piece of cake for you ...same logic;

overthinker_72: 2020-06-07 12:58:36

upper bound and lower bound can help :)

shivamojha99: 2020-06-04 14:20:26

Can anyone tell me why map.find() isn't working although its complexity is log(n) too, and why using vectors get AC but not with Map function??

sandeep48: 2020-06-04 07:30:55

(n square)log(n) is working

brokeboy: 2020-05-04 13:35:26

STL maps gave TLE. Use array and sort instead.

kkkrr: 2020-04-21 23:12:31

It can be solved using hashing. Instead of using STL try implementing your own hash map:)

manish_thakur: 2020-04-01 16:01:14

Since you have come to comments for help, use equal_range in c++

d_sm: 2020-03-09 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: 2020-02-27 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: 2020-01-31 12:39:10

Has anybody done this in java?

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