Author |
Topic: The Sums of a Set (Read 3827 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Re: The Sums of a Set
« Reply #25 on: Dec 14th, 2003, 5:12am » |
 Quote  Modify
|
Ahhh...
Let f(x) = [sum]s in S xs, and compute f2(x) = [sum]k=22n bkxk with FFT in O(nlog n) time. Then simply read off { k | bk != 0 }.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The Sums of a Set
« Reply #26 on: Dec 15th, 2003, 7:13am » |
Quote Modify
|
on Dec 12th, 2003, 6:02am, James Fingas wrote:So here is a listing of the best times so far:
my interesting solution: O(n log n)
Barukh's solution: O(mn)
my trivial solution: O(m[sup2] log m)
Which of these is best will depend on the relative sizes of m and n. My guess is that an answer running in O(m[sup2]) is possible. |
|
I would like to add that the O(m2) solution may be preferable also in case n - m << n: just compute the numbers in the range [2...2n] that are not in the output.
on Dec 14th, 2003, 5:12am, Eigenray wrote:
Perfect! If this is what James had in mind for his O(n log n) solution, than the connection with another thread is clear.
Very nice problem, Dudidu! 
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #27 on: Dec 15th, 2003, 7:57am » |
Quote Modify
|
on Dec 15th, 2003, 7:13am, Barukh wrote:
I would like to add that the O(m2) solution may be preferable also in case n - m << n: just compute the numbers in the range [2...2n] that are not in the output. |
|
I don't see how this is particularly easy ... a number x is in the set if an integer i can be found so that i and x-i are both in S. The number x is not in the set if no such integer i can be found. At first I envisioned generating the complement to S, but this doesn't help you find which x are not in the result.
Quote:| Perfect! If this is what James had in mind for his O(n log n) solution, than the connection with another thread is clear. |
|
That is exactly what I was thinking of, but a general O(m[sup2]) solution still seems to be lacking. The trivial way to get rid of duplications in O(m[sup2] + n) time is to put the resulting numbers in an array then read out which positions in the array are filled.
I think I see how to eliminate the need to search through the array (which is the part that takes O(n) time). Do the following:
input array s (size m)
array R (holds resulting numbers, size n)
list L (lists places in the array that have been used)
for i = 1 to m {
for j = i+1 to m {
L.add( s[i] + s[j] )
R[ s[i] + s[j] ] = 1
}
}
#now print out the resulting numbers. The are m(m-1)/2 list entries.
while L.count > 0 {
if R[ L.first ] > 0 {
R[ L.first ] = 0
print L.first
}
L.removeFirst
}
This way you only look through the numbers you generated, and you only print out one copy of each, all in O(m[sup2]) time, using O(n + m[sup2]) memory.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: The Sums of a Set
« Reply #28 on: Dec 16th, 2003, 12:00am » |
Quote Modify
|
James,
one can slightly improve upon your code,
let the R's be filled with zeroes.
for i = 1 to m
{
for j = i+1 to m
{
if(R[s[i]+s[j]] != 1)
{
output s[i] + s[j]
R[ s[i] + s[j] ] = 1
}
}
}
|
| « Last Edit: Dec 16th, 2003, 12:01am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #29 on: Dec 16th, 2003, 6:35am » |
Quote Modify
|
Very good. That's probably the best we'll be able to do.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #30 on: Dec 16th, 2003, 6:40am » |
Quote Modify
|
Everybody hi,
You got it all ! Bravo ! 
Quote:| You didn't happen to get the idea for this question from another thread, did you? |
|
James, now (I think) I understand why you asked my that question (you already known the answer when you wrote it...).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The Sums of a Set
« Reply #31 on: Dec 16th, 2003, 11:15pm » |
Quote Modify
|
on Dec 15th, 2003, 7:57am, James Fingas wrote:| I don't see how this is particularly easy ... a number x is in the set if an integer i can be found so that i and x-i are both in S. The number x is not in the set if no such integer i can be found. |
|
Let me elaborate on this. What got me to think about this was the following simple observation: if |S| = n (i.e. S contains every number in the range [1..n]), then the result may be printed immediately, without any computation. Is this something we can use if just a few elements are missing in S?
Let W(s) be the number of ways in which s [le] 2n may be written as a sum of two natural numbers [le] n. It is obvious that for s [le] n, W(s) = W(2(n+1)-s) = [smiley=lfloor.gif] s/2[smiley=rfloor.gif], so it is available at the start. Now, if m’ = n – m << n, just do the following:
1. For every x [notin] S, decrement W(x+y) for every y.
2. Output every s for which W(s) > 0.
Example: let S = {1,…,n} \ {1, n-1}. Because W(2) = W(3) = W(2n-1) = 1, the first step of the above procedure will eliminate these three numbers, and all others will be printed. This way we have complexity O(nm’), that may be better than O(n log n).
This procedure may be further improved by observing that it is sufficient to look only at numbers s, for which W(s) [le] m’. This reduces the complexity to O(m’2 + n).
P.S. Does it make any sense? I've just returned from my trip to the US, being under the effect of jet leg. 
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #32 on: Dec 17th, 2003, 5:06am » |
Quote Modify
|
Barukh,
That looks like it would work. That'll teach me to be skeptical!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print