3506 - 4 values whose sum is 0

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

3506 - 4 values whose sum is 0

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 ..
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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.
david
Learning poster

Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

[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
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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.