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

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

hide comments
2015-08-11 12:17:08 shaky99
10th test case gives WA.. can any one tell why??

Last edit: 2015-08-11 12:18:07
2015-08-04 21:52:43 Abhinandan Agarwal
Use dynamic allocation of array in case you are using binary search approach.
2015-07-22 21:44:57 Bhuvnesh Jain
brilliant question with even brilliant test cases. knew that qsort() is slower than sort() in worst case complexity but never had test cases which led me to change qsort to sort.... but here CAUTION: use only sort or your own implementation of merge/heap sort... do not use quick sort at all...
2015-07-08 02:00:51 Hussein Aassem
a testcase must be added with all the 4000 the same number to overflow char .... check my submission

Last edit: 2015-07-08 02:02:50
2015-07-01 15:48:11 Liquid_Science
Nearly Impossible in java :(
2015-06-30 14:47:43 kshitij tripathi
Nice Question..don't use Long Long int !! :D
2015-06-23 21:11:15 Varun Gambhir
Ordered map in c++ gives TLE and unordered gives AC(after some optimisations). Finally AC. :D

Last edit: 2015-06-23 21:11:36
2015-06-20 18:20:15 sameer makker
Can anybody explain why unordered_map fails here ?
Got a lot of TLEs, finally got AC. But still not sure why those solutions failed !
2015-06-20 16:01:50 Dhruv Mullick
Optimisations needed.
2015-06-20 10:55:09 Ayur Jain
Passes in O(n^2logn). Don't use STLs.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.