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 VB.net|
|Resource:||South western 05-06|
brilliant question with even brilliant test cases. knew that qsort() is slower than sort() in worst case complexity but never had test cases which led me to change qsort to sort.... but here CAUTION: use only sort or your own implementation of merge/heap sort... do not use quick sort at all...
a testcase must be added with all the 4000 the same number to overflow char .... check my submissionLast edit: 2015-07-08 02:02:50
Nearly Impossible in java :(
Nice Question..don't use Long Long int !! :D
Ordered map in c++ gives TLE and unordered gives AC(after some optimisations). Finally AC. :DLast edit: 2015-06-23 21:11:36
Can anybody explain why unordered_map fails here ?
Passes in O(n^2logn). Don't use STLs.
take 2 pointer array in pair stl ....learn a lot .. thanks !!! :)
can you tell the tenth case??