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
hetp111: 2019-06-01 09:02:24

How did 1st ranker got it in 0.01sec? mine took 2+sec with O(n*n*log(n))...

Last edit: 2019-06-01 09:04:09
abhinav_jain02: 2019-05-18 08:28:58

Note that equal elements in a list are considered to be distinct

mikroz: 2019-04-13 13:19:50

gp_hash_table

sagar_june97p: 2019-04-12 20:07:25

unordered_map got me TLE, however equal_range passed.

prudhvi_495: 2019-04-07 13:20:45

Last edit: 2019-04-14 08:06:25
syed_tanveer: 2019-04-03 12:40:58

AC in first go using upper_bound() and lower_bound()

Rahul Kathuria: 2019-04-03 03:44:13

Easy peasy :P AC in 1st go!
No need of equal range, hint :- just use vector with int data type and brute force(double pointer) in n^2 :)

divik544: 2019-03-27 15:51:02

1. Do not remove duplicates.
2. Use unordered_map with reserve
Mine passed in 2.34 s

y17prashant: 2019-03-22 02:30:56

use vectors , array gave a RE.......fast io worked here .....Hint- Complexity O(n^2*log(k))........Simple one

Last edit: 2019-03-22 02:33:16
alphacoder101: 2019-02-06 05:31:00

This is what happened for me:
Using map got TLE
Using unordered_map got TLE
Using unordered_map with reserved got TLE
Using Vectors wit h lower and upper_bound got TLE
Using arrays with lower and upper_bound got TLE
Using arrays with equal_range got accepted.

Many got AC with bounds and unordered_map. But they didnt work for me.


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