Monday, June 21, 2010

3SUM Puzzle

A puzzle courtesy of Mohan Paturi:


Given a set S of n numbers, the 3SUM problem asks whether there exist a,b,cS such that a+b+c=0. It is generally believed that this should take around n2 time.

But let's assume |S+S| = tn2. Show that the problem can be solved in O(t lg2n) time.

Any ideas for a better bound?

9 comments:

Anonymous said...

For each element x in S+S, query for the existence of -x in S in O(log n) time for a O(t log n) algorithm.

Mihai said...

Well, you can test membership in O(1) by a hash table, but the point is: how do you generate S+S in subquadratic time?

Anonymous said...

FFT, work module random U = O(t), repeat O( log t ) times. No?

No clue how to improve the running time. --S

ilyaraz said...

Could you please give a hint? Does your algorithm obtain the set S+S explicitely?

Mihai said...

I don't obtain S+S explicitly. That's actually a good problem. Does anybody have any idea?

The solution I know is what Sariel says. Use linear hashing to a domain of p=2*t (modular hashing works, but multiply-shift is better). Then compute the set (S+S) mod p using FFT in time O(t*lg t).

Now you can look up each value in -S in this set (S+S) mod p. If a value is not in, you know it's not part of a solution. Repeat O(lg n) times and only the true solutions remain.

Anonymous said...

Can someone explain how FFT can be used to compute (S+S) mod p?

Mihai said...

FFT can multiply two polynomials of degree d in time O(d lg d). If you have a set S mod p, make a polynomial of degree p, where x^i has coefficient 1 if i is in S mod p, and 0 otherwise.

Multiplying the polynomials, you obtain a nonzero coefficient only for values x that can be written as a+b, with a and b in S. You take all nonzero coefficients of the result modulo p, and that precisely (S+S)mod p.

Andreja said...

Hello, I am Andreja Ilic from Serbia. If I understood right, we can divide number in three groups: zeros, positive and negative. The most complex case is - take two positive numbers and one negative number.

We can solve this in the following way: For fixed negative number -z, we are going to check for every positive number x is there -z + x in positive numbers. So if we sort numbers, when we move from x to bigger one, the number -z + x also moves right. And this is O(n^2)...

Andreja said...

Hello, I am Andreja Ilic from Serbia. If I understood right, we can divide number in three groups: zeros, positive and negative. The most complex case is - take two positive numbers and one negative number.

We can solve this in the following way: For fixed negative number -z, we are going to check for every positive number x is there -z + x in positive numbers. So if we sort numbers, when we move from x to bigger one, the number -z + x also moves right.