10663 - Non-Powerful Subsets

[little joey]

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.

[Adrian Kuegel]

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]

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]

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]

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]

Well, when I read:

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]

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]

If multiset is allowed, then {1,1,1,1} (sums to 4) is a subset of {1}, so {1} is not a solution.

[Per]

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

[Adrian Kuegel]

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]

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.

[Adrian Kuegel]

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]

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.

[misof]

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]

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.

Anyway this problem is tainted by the fact that it's subject to printf solutions.
I think problem setters should avoid problems that are obviously printf-able.

Ciao!!!

Claudio