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 228 ) 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
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.

sagnik_66: 2017-06-07 11:55:21

Same question as @up79, TLE without reserve(), when using unordered_map
BTW, 2.33 secs using upper_bound/lower_bound & 2.84 secs using unordered_map

Last edit: 2017-06-07 15:57:34

Added by:Abhilash I
Date:2007-02-06
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