A puzzle courtesy of Mohan Paturi:

Given a set S of

*n*numbers, the 3SUM problem asks whether there exist*a*,*b*,*c*∈*S*such that*a*+*b*+*c*=0. It is generally believed that this should take around*n*^{2}time.But let's assume |

*S*+*S*| =*t*≪*n*^{2}. Show that the problem can be solved in O(*t*lg^{2}*n*) time.Any ideas for a better bound?

## 9 comments:

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.

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?

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

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

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

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.

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

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.

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)...

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.

Post a Comment