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
TP: 2016-07-14 11:41:57

Don't use long long . It costs me 2 TLE .

mkfeuhrer: 2016-07-10 22:03:37

nice problem!! only stl ie sort upper bound and lower bound gave TLE ! got AC using two pointer approach after O(n*n) sum calculations!

Anuj Arora: 2016-07-10 17:35:18

AC in one shot :D

Shubham Gupta: 2016-07-06 23:55:06

If getting TLE with std::lower_bound and std::upper_bound, then try using std::equal_range!
long long is not required.
O(n^2logn) passing!

priyanshu_02: 2016-06-24 00:54:02

Don't use binary search or stl bound functions.
Instead use two pointers technique to find frequencies .
Passes without optimisations.

Last edit: 2016-06-24 01:08:15
kartikay singh: 2016-06-22 12:50:39

@praval_singhal
It's not misleading...actually it is (4n *4n)... :-)

Last edit: 2016-06-22 12:52:24
begin_88: 2016-06-11 13:54:51

getting tle even after using int, vectors, lb, ub, check for same values...

praval_singhal: 2016-05-31 17:32:29

@Abhilash why have you gave n=4000 when n*n<10000000. Isn't it misleading.

candide: 2016-04-25 10:33:17

Done in PyPy. No sort, no binary sort, only arrays. ABCDEF is very similar.
@praval_singhal: you are right, input size list doesn't exceed 2500

Last edit: 2016-06-25 09:28:24
Akshay Damle: 2016-04-12 23:17:17

AC in 1 go :D Try ABCDEF before this. Using vectors for the sums and upper_bound, lower_bound works.


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 NODEJS PERL 6 VB.net
Resource:South western 05-06