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

Post Reply
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

3506 - 4 values whose sum is 0

Post by helloneo » Tue Jul 04, 2006 4:56 pm

http://acmicpc-live-archive.uva.es/nuev ... php?p=3506

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

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

Post by david » Tue Jul 04, 2006 8:32 pm

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.

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

Post by helloneo » Wed Jul 05, 2006 10:18 am

[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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jul 11, 2006 11:07 pm

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 + b[0], and each time when you removed as the minimum element a + b[j] from the heap, you insert a + b[j+1] instead.

Post Reply

Return to “ACM ICPC Archive Board”