## 10663 - Non-Powerful Subsets

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 10663 - Non-Powerful 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 NP-complete 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 sub-subsets 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 n-1 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.

little joey
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)):

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
``````
Spot the loony

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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:
A set is a finite or infinite collection of objects in which order has no significance, and multiplicity is generally also ignored.
But of course, generally doesn't mean it is in this case.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I don't think so. According to mathworld a subset is a portion of a set, so {5,5,5,5} is not a subset of {1,2,3,4,5,...}. And if that were true the answer to this problem would be the empty set (and it's not, I just verified).

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
B is a subset of A iff every member of B is a member of A
I interpret it quite literally as:

Code: Select all

``````subset (set A, set B)
foreach num in set B
if num not in set A
return false
return true``````
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 { }?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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!

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
If multiset is allowed, then {1,1,1,1} (sums to 4) is a subset of {1}, so {1} is not a solution.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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?
Yeah, since if we remove the last element from any "(N+1)-sequence", we get a feasible "N-sequence".

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:
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
It doesn't say, that this is not a maximum subset for numbers < 20.
The DP recurrence I described would produce a subset of size 4 for numbers < 20 !

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I just got accepted using the following algo:

Code: Select all

``````start with an empty set
for n=1 to 1000
add n to the set if it's power-free and leaves the set power-free
print the set
``````
No comment.

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

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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
9

More specific:
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
12 is not added, 1+2+10+12 is a power
etc.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.
The judge solution is correct, you just misunderstood the problem statement. And (yet again) it is due to a misleading problem statement

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.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova