| 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
|
||||||||||||||
|
2018-03-27 23:12:09
what should be the answer for the testcase 2 4 2 -3 -3 3 3 -3 -3 |
||||||||||||||
|
2018-01-11 19:24:05
To those using binary-search and getting WA on test case 10 , make sure to check for the following: 1)there can be multiple occurrences of the key that you are searching for, you need to count all of these. 2)while doing the check for the multiple occurences, you might have used a temporary loop variable (like 'i' ) to iterate over the surrounding region of the searchkey, make sure that you have given constraints for '' i '' as well , in this case (i >=0 && i < n*n) i fixed this constraint and got AC in third go , :D !! Last edit: 2018-01-11 19:24:23 |
||||||||||||||
|
2017-12-28 07:17:34
AC in one go! 50th |
||||||||||||||
|
2017-12-21 19:23:46
Can also be solved in O(N ^ 2) using Hashing. Although O(N ^ 2 * log(N)) also gets accepted. |
||||||||||||||
|
2017-12-19 20:31:45
solution using lower_bound and upper_bounds works fine!!! Last edit: 2017-12-19 20:32:20 |
||||||||||||||
|
2017-12-11 07:07:19 Divyam Shah
For those getting WA in test case 10 - When doing binary search,count the number of times the search key occurs in the array rather than counting it as 1. |
||||||||||||||
|
2017-10-06 12:29:16
Reduced complexity from O(N^2 LogN) to O(N^2) got AC; |
||||||||||||||
|
2017-09-05 08:56:15
use equal_range. AC after 5 TLE |
||||||||||||||
|
2017-08-25 00:25:04
whats feynman algo...can someone provide a link where i can know abt it? |
||||||||||||||
|
2017-07-18 20:25:13
O(n^2) complexity.. |
||||||||||||||
RSS