10663 - Non-Powerful Subsets

[UFP2161]

Then the following line should be taken out:

Such a subset is named "maximal" if it is the largest subset meeting the requirements.

And change "natural numbers" to "positive integers" as "natural numbers" does not strictly define the status of 0.
Reference: http://en.wikipedia.org/wiki/Natural_number

With those changes, then I can understand why the solution is what it is. Of course, the limits should be increased to prevent simple printf programs then.

[Per]

I've mailed a "bug report" that the problem statement should be fixed.

Suddenly, the problem wasn't all that nice any longer.

[Lars Hellsten]

Wow... that sucks.

What a waste of time. I wasted more time accomplishing nothing on problems E and G than I did solving the other seven.

[Lars Hellsten]

BTW, Adrian, 18 was also the largest set I found. I used an incomplete search (of course), but I suspect that is optimal or very close to it. It is definitely much lower than 30.

[Adrian Kuegel]

I wasted more time accomplishing nothing on problems E and G than I did solving the other seven.

Did you see, that problem G was rejudged, and you got it Accepted?
But you could have won this contest (and I could have been 2nd) if problem description of E would have been correct.

[Carlos]

Hi!
First of all, sorry for the long time you've spent on thi. This was Murcia's regional contest, so they made the problems, and the descriptions.

About changing the description, I'll do it right now because I also understood the problem like you (largest instead of maximal).

And about allowing an input...that will make all accepted submissions get wrong. If we want to do it, we should do it as soon as possible. If any of you want to help making it, please mail me at:

marce at fernandonajera dot com

Thanks for your help.

[Adrian Kuegel]

And about allowing an input...that will make all accepted submissions get wrong. If we want to do it, we should do it as soon as possible. If any of you want to help making it, please mail me at:

I think this problem is anyway very easy in this form (to find only first maximal subset). So it wouldn't make the problem more difficult if an input is used. To get a printf solution, there must be another program to generate it. So in my opinion no input file is needed.

[Dreamer#1]

Please help me find out why i'm getting WA.
Can someone please verify the following input/outputs and give me some more of them incase they are all correct.

input:

Code: Select all

1 1000
100 200
200 300
300 400
400 500
500 600
600 700
700 800
800 900
900 1000

output:

Code: Select all

1 2 10 11 44 85 153 165 971
101 102 103 104 105 106 143 145 147
200 201 202 203 204 205 206 242 258
300 301 302 303 304 305 306 326 327
401 402 403 404 405 406 423 424 425
500 501 502 503 504 505 506 525 526
600 601 602 603 604 605 606 626 627 651
700 701 702 703 707 710 716 717 718 719 721
800 801 802 803 804 805 806 811 812 813 814 815
901 902 903 904 905 906 907 908 909 910 911 912 913 914

is there any tricky cases?

thanks in advance.

-regards

Dreamer

[angga888]

Your output is same compared with mine.

is there any tricky cases?

Not tricky ones, but you can try...
Input:

Code: Select all

999 999
100 1000
200 1000
300 1000
400 1000
500 1000

Output:

Code: Select all

999
101 102 103 104 105 106 143 145 147 249
200 201 202 203 204 205 206 242 258 402
300 301 302 303 304 305 306 326 327 405
401 402 403 404 405 406 423 424 425 588
500 501 502 503 504 505 506 525 526 627 638

Good luck!

[minskcity]

I'm getting TLE all the time. My programs solves ~1000 inputs/sec. Is it too slow? If yes, what algorithm should I use??

[shamim]

I don't know the algorithm u r using, but I can tell you must first store all the sequence's starting with N ( 1<=N<=1000 ).

If u r asked to print in the range 10 100, just print elements of sequence number 10, which are less than or equal to 100.

[minskcity]

Thx, got AC now.

BTW, Adrian, 18 was also the largest set I found. I used an incomplete search (of course), but I suspect that is optimal or very close to it. It is definitely much lower than 30.

That's a brave assumption. What you are saying is that it's impossible to find an arbitrary big interval with no powers. I believe it's not true.

Let's check what is the length of a power-free interval we can get between 2^(n - 1) and 2^n.
Number of powers on this interval is less then:
2^(n/2) + (squares)
2^(n/3) + (cubes)
2^(n/4) +
........
2^(1)

which is less then:

n*2(n/2)

as a result we can find a power-free interval with length of at least:
2^(n - 1)/(n*2^(n/2)) = 2^(n/2 - 1)/n - can be arbitrary big....

conclusion: for any set it is always possible to find an element to add to it.

consequently: the set can be arbitrary big.

PS: let me know if I'm wrong.

[Adrian Kuegel]

Lars didn't say that for arbitrary intervals the maximum set will be at most 18. It seems you don't know the old version of this problem. It said you should find the largest set of power-free numbers <= 1000. What the problem meant was you should find a maximal set with numbers <= 1000, but it incorrectly stated that maximal means that the set is the largest possible set, therefore most of the participants in this contest couldn't solve the problem.