| Submit | All submissions | Best solutions | Back to list |
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
|
||||||||||||||
|
2021-10-15 13:43:23
Hi,You must be here in comment sectopn after getting so many TLES. The reason for TLE is not your logic instead its STL. Dont use any Stl library like Map,unorderd_map,vector,lower_bound. Implement your own functions. I got 3≈4 TLES due to STL the implement My own functions and used simple array[] and AC. |
||||||||||||||
|
2021-05-13 20:51:42 4444
Got TLE for: [1] unorder_map [2] arrays with lower_bound, upper_bound AC after using arrays and equal_range. |
||||||||||||||
|
2020-11-20 16:54:17
Use arrays and then binary search, STL implementation gives TLE |
||||||||||||||
|
2020-10-08 06:16:31
after this try abcdef problem on spoj |
||||||||||||||
|
2020-09-16 09:30:15
Getting TLE only, I have used MIM + (map, unordered map with good hash fxn, binary search, C++ lower_bound & upper_bound on vector after sorting it). Still getting TLE. Anyone suggest something or any other technique. |
||||||||||||||
|
2020-08-01 05:41:36
if you do ABCDEF problem first ...its is a piece of cake for you ...same logic; |
||||||||||||||
|
2020-06-07 12:58:36
upper bound and lower bound can help :) |
||||||||||||||
|
2020-06-04 14:20:26
Can anyone tell me why map.find() isn't working although its complexity is log(n) too, and why using vectors get AC but not with Map function?? |
||||||||||||||
|
2020-06-04 07:30:55
(n square)log(n) is working |
||||||||||||||
|
2020-05-04 13:35:26
STL maps gave TLE. Use array and sort instead. |
||||||||||||||
RSS