## 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

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

### 3506 - 4 values whose sum is 0

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