10663  NonPowerful Subsets
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10663  NonPowerful Subsets
I've been trying to find my way out of this problem for several hours now, but still can't see the light.
To me it's just a huge NPcomplete problem, far beyond the scope of computing powers, but that can't be true because 3 people solved it during the contest.
I tried brute force, by expanding possible subsets of length n with one element to get a possible subset of length n+1, but it takes about an hour to find the first length 15 solution this way. In my estimate the answer will have in the order of 30 elements. I also took an other route by gradualy increasing the value of N (the maximum number in the subset), but it takes some 20 minutes to find the 11 element solution for N=100 (14,19,33,47,52,61,66,71,80,85,90).
For a 30 element subset, there are choose(960,30) = 7.0E56 possibillities, each with 2^30 = 1.1E9 subsubsets to check...
I can't think of a suitable devide&conquer or DP strategy. Or is there a number theoretical principle at work here?
Any help or ideas are appreciated.
To me it's just a huge NPcomplete problem, far beyond the scope of computing powers, but that can't be true because 3 people solved it during the contest.
I tried brute force, by expanding possible subsets of length n with one element to get a possible subset of length n+1, but it takes about an hour to find the first length 15 solution this way. In my estimate the answer will have in the order of 30 elements. I also took an other route by gradualy increasing the value of N (the maximum number in the subset), but it takes some 20 minutes to find the 11 element solution for N=100 (14,19,33,47,52,61,66,71,80,85,90).
For a 30 element subset, there are choose(960,30) = 7.0E56 possibillities, each with 2^30 = 1.1E9 subsubsets to check...
I can't think of a suitable devide&conquer or DP strategy. Or is there a number theoretical principle at work here?
Any help or ideas are appreciated.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I have the same problem. I know that the maximum subset has at least 16 elements (I found this by considering only consecutive numbers). And (960 over 16) is already 2,1E34. Backtracking makes no sense with this huge number of possibilities.
But I am almost sure that DP is also not possible. There is a obvious DP recurrence, that a optimal sequence for n is either the optimal sequence for n1 or there is a optimal sequence for m (m<n) where I can attach n to build optimal sequence for n.
But this recurrence does not give the optimal answer.
So I think there must be some number theoretic stuff to solve this.
But I am almost sure that DP is also not possible. There is a obvious DP recurrence, that a optimal sequence for n is either the optimal sequence for n1 or there is a optimal sequence for m (m<n) where I can attach n to build optimal sequence for n.
But this recurrence does not give the optimal answer.
So I think there must be some number theoretic stuff to solve this.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Can we be sure that the optimal sequence lenghts for N and N+1 differ by at most 1, as you write? I wouldn't be surprized if a bigger difference occurs for some (big) value of N. But either way, that doesn't help us much...
I've been searching for regularities, but can't find any. For anyone interested, here are my results for N<=100. Values for unlisted N are the same as the biggest listed N smaller than N (so OS(100)=OS(90)):
Spot the loony
I've been searching for regularities, but can't find any. For anyone interested, here are my results for N<=100. Values for unlisted N are the same as the biggest listed N smaller than N (so OS(100)=OS(90)):
Code: Select all
1( 1): 1
2( 2): 1 2
6( 3): 1 5 6
10( 3): 1 2 10
11( 4): 1 2 10 11
18( 5): 1 10 11 12 18
20( 5): 1 2 18 19 20
21( 5): 1 2 17 20 21
22( 6): 2 13 15 18 20 22
23( 6): 1 6 11 17 22 23
28( 7): 1 6 11 17 22 23 28
33( 7): 1 5 6 17 23 28 33
38( 7): 1 2 18 19 20 37 38
46( 8): 1 22 23 28 43 44 45 46
50( 8): 1 21 22 23 44 45 46 50
58( 8): 1 18 19 20 37 38 39 58
59( 8): 1 2 28 43 44 45 58 59
60( 9): 1 14 28 29 30 44 45 59 60
85(10): 5 14 19 33 47 52 61 66 80 85
90(11): 14 19 33 47 52 61 66 71 80 85 90
Can the answer include the numbers more than once? The problem statement doesn't really say anything on that matter.
But by definition the set {5, 5, 5, 5} is a subset of {1, 2, 3, 4, 5, ...} since each 5 is a member of the set of natural numbers.
However, MathWorld does define a set as:
But by definition the set {5, 5, 5, 5} is a subset of {1, 2, 3, 4, 5, ...} since each 5 is a member of the set of natural numbers.
However, MathWorld does define a set as:
But of course, generally doesn't mean it is in this case.A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Well, when I read:
Then again, that's an extremely literal interpretation... and all really depends on whether it's a set or multiset..
And, why would the empty set be the correct answer? Isn't { 1 } better than { }?
I interpret it quite literally as:B is a subset of A iff every member of B is a member of A
Code: Select all
subset (set A, set B)
foreach num in set B
if num not in set A
return false
return true
And, why would the empty set be the correct answer? Isn't { 1 } better than { }?
I have never seen anyone define a set as something that can have duplicates. When duplicates are counted, they are generally called multisets, or sometimes bags. And as you say, the problem's definition of subset doesn't really make sense for multisets.
This is definitely the best "no input" problem I've seen so far!
This is definitely the best "no input" problem I've seen so far!
Yeah, since if we remove the last element from any "(N+1)sequence", we get a feasible "Nsequence".little joey wrote:Hmm. Can we be sure that the optimal sequence lenghts for N and N+1 differ by at most 1, as you write?
In case anyone is still interested, here is the continuation of joey's values for up to N=150.
Code: Select all
1( 1): 1
2( 2): 1 2
6( 3): 1 5 6
10( 3): 1 2 10
11( 4): 1 2 10 11
18( 5): 1 10 11 12 18
20( 5): 1 2 18 19 20
21( 5): 1 2 17 20 21
22( 6): 2 13 15 18 20 22
23( 6): 1 6 11 17 22 23
28( 7): 1 6 11 17 22 23 28
33( 7): 1 5 6 17 23 28 33
38( 7): 1 2 18 19 20 37 38
46( 8): 1 22 23 28 43 44 45 46
50( 8): 1 21 22 23 44 45 46 50
58( 8): 1 18 19 20 37 38 39 58
59( 8): 1 2 28 43 44 45 58 59
60( 9): 1 14 28 29 30 44 45 59 60
85(10): 5 14 19 33 47 52 61 66 80 85
90(11): 14 19 33 47 52 61 66 71 80 85 90
104(11): 14 19 28 33 38 47 52 66 85 99 104
105(11): 11 18 29 47 58 65 76 77 87 94 105
112(11): 5 18 19 37 55 56 74 92 93 111 112
113(11): 5 14 19 33 47 52 66 80 85 99 113
114(11): 2 20 22 24 46 66 68 90 92 112 114
118(12): 5 14 19 33 47 52 66 80 85 99 113 118
129(12): 1 6 41 47 70 76 82 88 111 117 123 129
135(13): 6 35 41 47 70 71 76 82 88 117 123 129 135

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I think the sample output is quite confusing:
The DP recurrence I described would produce a subset of size 4 for numbers < 20 !
It doesn't say, that this is not a maximum subset for numbers < 20.Obviously, this output is not the correct one (it is not the first subset and the numbers are less than 20), but it shows how must be printed the solution.
3 7 10 11
The DP recurrence I described would produce a subset of size 4 for numbers < 20 !

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I just got accepted using the following algo:
No comment.
Code: Select all
start with an empty set
for n=1 to 1000
add n to the set if it's powerfree and leaves the set powerfree
print the set

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
9
More specific:
1 is added
2 is added
3 is not added, 1+3 is a power
4 is not added, it's a power
5 is not added, 1+2+5 is a power
6 is not added, 1+2+6 is a power
7 is not added, 2+7 is a power
8 is not added, it's a power
9 is not added, it's a power
10 is added
11 is added
12 is not added, 1+2+10+12 is a power
etc.
More specific:
1 is added
2 is added
3 is not added, 1+3 is a power
4 is not added, it's a power
5 is not added, 1+2+5 is a power
6 is not added, 1+2+6 is a power
7 is not added, 2+7 is a power
8 is not added, it's a power
9 is not added, it's a power
10 is added
11 is added
12 is not added, 1+2+10+12 is a power
etc.
The judge solution is correct, you just misunderstood the problem statement. And (yet again) it is due to a misleading problem statementAdrian Kuegel wrote:
Incredible that the judge solution is so wrong.
By the way, how long is the sequence that is generated like this?
The longest sequence I found so far has length 18.
In mathematics there is a difference between the words maximal and largest. The second one means "with most elements". The first one means "one, that cannot be further extended". In this case what was required was really to find the lexicographically first maximal subset. The problem statement states this correctly, however, it goes on to confuse the reader using the word "largest" in an inappropriate way.
The algorithm posted above is correct.
And to other posters: multisets are not allowed and the set doesn't contain zero as an element.
Anyway this problem is tainted by the fact that it's subject to printf solutions.Adrian Kuegel wrote:
Incredible that the judge solution is so wrong.
By the way, how long is the sequence that is generated like this?
The longest sequence I found so far has length 18.
I think problem setters should avoid problems that are obviously printfable.
Ciao!!!
Claudio