6
$\begingroup$

(this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM)

Suppose we have a list $S$ of $n$ integers. Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ $\in S$ such that $a+b+c=0$. That's done in $O(n^2)$, and obviously the same thing can be done for $a+b+c=d$, with $d$ an integer.

Now, I use a somewhat modified version of this problem. Someone randomly picks $n$ triplets of elements of $S$, and for each of them, computes the sum of its elements. Let's call the list of these sums $Y$. That's $n$ instances of 3SUM built on the same set.

My goal is to invert one element of $Y$., i.e. is to find one element in $Y$, along with its corresponding elements in $S$. (To solve one of the possible instances of 3SUM, no matter which one)

I'm looking for a $O(n)$ solution. If we feed this solution some particular $S$ and $Y$ ,and we want to find a particular $d$ in $Y$, it would take the solution $O(n)$ attempts to find the $d$ we're looking for, thus running in $O(n^2)$, which is the 3SUM complexity.

I tried to use randomness in my solutions, without success. Someone also advised me to have a look at FFTs, but I can't see how I could use them in this case.

The best that I can do now, is to have $Y$ built with $n^{1.5}$ triplets instead of $n$, and then I can use the birthday paradox. If I pick $O(n^{1.5})$ triplets at random, I have a constant probability to find the same triplet twice. ($n^{1.5} = \sqrt{n^3}$)

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Please provide a link to your previous question and state the relation between the current question and the previous one. I think that this is the special case of your previous question with the additional assumption |D|=n, and I fail to see how the birthday paradox can be used to obtain an O(n^{3/2})-time randomized algorithm, but I may be missing something. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 31, 2012 at 23:05
  • $\begingroup$ Done. For the birthday problem, I've edited a little more to make everything clear I hope (and right). It's maybe clearer in the balls and urns model. If you have $n$ balls in an urn, and you pick balls in this urn, you'll have to pick roughly $\sqrt{n}$ balls (with replacement) to pick the same ball twice. So in my case, if I pick $n^1.5$ triplets from the $n^3$ possible triplets (=balls) to build $Y$, I'll pick the same triplet twice with good (i.e. constant) probability with $O(n^{1.5}$ tries. $\endgroup$
    – Heinz Fiedler
    Commented Jan 31, 2012 at 23:48
  • $\begingroup$ I am confused. I thought that Y is an input to your algorithm, but I realized that you are talking about how you choose Y. If you choose Y, why don’t you just choose something trivial such as the sum of the three smallest elements in S? I think that you have some assumption about how Y must be chosen in your mind, which is not stated in the question. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 1, 2012 at 0:07
  • $\begingroup$ Someone build Y for me, that was wrong in the question, my bad. $\endgroup$
    – Heinz Fiedler
    Commented Feb 1, 2012 at 0:26
  • $\begingroup$ (1) I think that now I understand the question (but not the answer…). Thanks for editing the question. (2) I do not think that the main difference between your previous question and the current question is whether you use 3SUM or 3SUM′. The important differences are the size of set Y (previously called set D) and how this set is chosen (“randomly” is very important). $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 1, 2012 at 0:48

1 Answer 1

Reset to default
9
$\begingroup$

It's not linear time, but here at least is an $O(n^{3/2})$ randomized solution to the problem in which you are given a set of $n$ elements together with the sums of $n$ randomly-generated triples of the elements, and you have to find a triple that matches one of the given sums.

  • Pick randomly two subsets $A$ of $n^{3/4}$ elements and $B$ of $n^{1/2}$ elements. With constant probability at least one of your 3SUMs is in $A+A+B$.

  • Compute the set $A+A$ and store it in a hash table for fast lookups.

  • For each pair of a value $x$ in $B$ and a target value $z$ of one of the input 3SUMs, test whether $z-x$ is one of the stored values of $A+A$, and if so whether the resulting triple(s) of numbers $A+A+B$ that sum to $z$ are distinct from each other.

I originally thought this would work equally well for an adversarially-selected set of 3SUMs (instead of the randomly-selected set in your question), but now I'm not sure sure about that part: the expected number of 3SUMs you hit with your choice of $A+A+B$ is always constant, but maybe the adversary could fix things so that you have a high probability of hitting none of them and a small probability of hitting many at once? I'm not sure this is possible but it would take more analysis than I've done so far to be certain.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Nice algorithm! Observation: If the set Y of n sums is chosen adversarially, then it indeed fails. Suppose that S contains one exceptionally large number m, and the adversary chooses Y={2m+x: x∈S}. Then the algorithm succeeds only if A contains m, which happens with probability $1/n^{1/4}$. $\endgroup$
    – Tsuyoshi Ito
    Commented Feb 4, 2012 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.