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
|
iamfahim:
2019-11-03 19:50:54
Using STL equal_range |
|
nadstratosfer:
2019-07-24 04:56:34
Sadly, some datasets have nearly no zero-summing quadruplets, rendering a large assortment of possible optimizations useless. Most people commenting here seem to confuse optimization with not doing stupid stuff, and noone claiming to have done it in O(n^2) has runtime to prove it. I'm still bothered to find the efficient approach candide hinted to, but other than that the problem seems like a waste of time after getting the green bar. |
|
yashranjan74:
2019-06-21 11:18:25
Just use equal range in place of unordered_map. Although the complexity was better using unordered_map but equal_range get AC whereas unordered_map gave TLE. |
|
harry_shit:
2019-06-04 12:10:34
tle for O(n*n) also,using unordered map
|
|
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() |
| 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 |
RSS