Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here is the problem:

I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements).
So I have one element $X$. I want to know if I can get $X$ making the sum of one element of $S_1$, one of $S_2$ and one of $S_3$.

Say for example $N = 4$ and $S_1 = \{ 1, 3,-1, 5\}$, $S_2 = \{ 4, 0, 2, 1 \}$, $S_3 = \{ 5, 1, 0, 6\}$.

Then

  1. $X = 11$ returnss YES because picking $3$ in $S_1$, $2$ in $S_2$ and $6$ in $S_3$, we can make the sum $3 + 2 + 6 = 11$,

  2. $X = 10$ returns YES ($5 + 0 + 5$)

  3. $X = 1$ returns YES ($ 1 + 0 + 0 $) or ($ -1 + 2 + 0$ )

  4. $X = 20$ returns false

If I sum all the possibilities, clearly we get an $O(n^3)$ algorithm.

As mentioned in the title, the question is if there is an $O(n^2)$ algorithm for this problem.

share|improve this question
    
I tried sum all numbers in S1 and S2, and search the number that i want ( S1+S2 - X ) in S3, but still a n³ –  Shermano Jul 3 '13 at 19:08
    
sorry my poor english –  Shermano Jul 3 '13 at 19:09
    
That's, um, sort of right... –  Noam D. Elkies Jul 3 '13 at 19:12
    
sorry ?? i don't get it –  Shermano Jul 3 '13 at 19:18
2  
It's easy to do in $O(n^2)$, but is this a homework question? –  Brendan McKay Jul 3 '13 at 20:38
show 3 more comments

1 Answer

up vote 6 down vote accepted

First sort $S_2$ and $S_3$.

Divide into $n$ subproblems: for each $a\in S_1$, look for $b\in S_2,c\in S_3$ such that $b+c=X-a$. Let's do one such subproblem in $O(n)$ time.

Let $b_j$ be the $j$-th element of $S_2$ and $c_k$ be the $k$-th element of $S_3$. The idea is that for $j=1,2,\ldots,n$ you find the smallest $k$ such that $b_j+c_k\ge X-a$. For each $j$ find $k$ by starting at the previous value, not by searching from the end. As $j$ increases, $k$ stays the same or decreases, so you only need to move $k$ at most $n$ times in total.

share|improve this answer
    
thx bro, really thanx –  Shermano Jul 4 '13 at 3:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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