3506 - 4 values whose sum is 0

[helloneo]

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3506

hello..~
does anybody have an idea ..?
I've been thinking of it all day but can get out of TLE ..

[david]

The official solution is to compute all sums of elements of A and B, all sums of elements of C and D, sort them and then find, in linear time with the total size of both vectors, pairs of sum zero. The running time is O(n^2 log n).
However, the time constraints at SWERC were too tight, so if you use vectors instead of arrays you will get TLE. I did exactly that during the contest and, thinking an O(n^2) expected solution was intended, started using hash tables and tweaking parameters until I got AC at the 11th time or so, just before the end of the contest... It never crossed my mind that the reason I kept getting TLE was using vectors instead of arrays, although in hindsight I should have thought about that.

By the way, I really wonder how Adrian Kuegel managed to get the problem solved at the live archive with such low memory spent.

[helloneo]

[quote="david"]The official solution is to compute all sums of elements of A and B, all sums of elements of C and D, sort them and then find, in linear time with the total size of both vectors, pairs of sum zero. The running time is O(n^2 log n).
However, the time constraints at SWERC were too tight, so if you use vectors instead of arrays you will get TLE. I did exactly that during the contest and, thinking an O(n^2) expected solution was intended, started using hash tables and tweaking parameters until I got AC at the 11th time or so, just before the end of the contest... It never crossed my mind that the reason I kept getting TLE was using vectors instead of arrays, although in hindsight I should have thought about that.

By the way, I really wonder how Adrian K

[Adrian Kuegel]

I create the values of pairs of the first two lists and the second two lists in sorted order "on the fly" during the step of the algorithm where we find pairs of values from those combined lists which sum to zero.
When you have two sorted lists a[0..n-1] and b[0..n-1] and want to create the pairs of values in sorted order, you can use a heap with n elements. First, you insert all Elements a[i] + b[0], and each time when you removed as the minimum element a[i] + b[j] from the heap, you insert a[i] + b[j+1] instead.