3506 - 4 values whose sum is 0

Let's talk about algorithms!

Moderator: Board moderators

3506 - 4 values whose sum is 0

Postby helloneo » Tue Jul 04, 2006 4:56 pm

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

Postby 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.
david
Learning poster
 
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Postby 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
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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


Return to Algorithms

Who is online

Users browsing this forum: No registered users and 1 guest