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
mahabir10: 2018-03-27 23:12:09

what should be the answer for the testcase
2
4 2 -3 -3
3 3 -3 -3

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


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