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
aniket000: 2018-01-11 19:24:05

To those using binary-search and getting WA on test case 10 , make sure to check for the following:
1)there can be multiple occurrences of the key that you are searching for, you need to count all of these.
2)while doing the check for the multiple occurences, you might have used a temporary loop variable (like 'i' ) to iterate over the surrounding region of the searchkey, make sure that you have given constraints for '' i '' as well , in this case (i >=0 && i < n*n)
i fixed this constraint and got AC in third go , :D !!

Last edit: 2018-01-11 19:24:23
rinem13: 2017-12-28 07:17:34

AC in one go! 50th

themast3r: 2017-12-21 19:23:46

Can also be solved in O(N ^ 2) using Hashing. Although O(N ^ 2 * log(N)) also gets accepted.

kmkhan_014: 2017-12-19 20:31:45

solution using lower_bound and upper_bounds works fine!!!

Last edit: 2017-12-19 20:32:20
Divyam Shah: 2017-12-11 07:07:19

For those getting WA in test case 10 - When doing binary search,count the number of times the search key occurs in the array rather than counting it as 1.

shikhars387: 2017-10-06 12:29:16

Reduced complexity from O(N^2 LogN) to O(N^2) got AC;

vengatesh15: 2017-09-05 08:56:15

use equal_range. AC after 5 TLE

dunjen_master: 2017-08-25 00:25:04

whats feynman algo...can someone provide a link where i can know abt it?

soham_12345: 2017-07-18 20:25:13

O(n^2) complexity..

aditya9125: 2017-06-18 14:12:45

Using map or unordered_map didn't work for me even after the prevailing "reserved" keyword.After having tried many approaches I come to know, this problem asks to use binary search either simply or through "equal range", I think this approach would be a finer one.

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