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.
Last edited by david
on Tue Feb 13, 2007 12:56 pm, edited 1 time in total.