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
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 .
Output should be printed on a single line.
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|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: ERL JS NODEJS PERL 6 SCM chicken VB.net|
|Resource:||South western 05-06|
Damn! Finally AC! :D
O(n^2 *logn) is giving me a TLE why????? is der any better methodLast edit: 2015-03-29 10:57:10
O(n^2 log(n)) + optimization
Lot of optimization needed.
@Chandan Mittal if you have used cin and cout , try using printf and scanf
O(n^2 * log(n)) gives TLE. But why??? :(
ankit kumar sinha:
dont use long long int. gives TLE
wrong ans on test case 9
very weak test cases, it doesn't even have n up to 4000