[Community Puzzle] Nuggets numbers

Puzzles
#22

I am sorry for such a question. I solved that with 100%, but cannot see solutions of others.

If I see a specific language, I see grayed out items with lock icons.
How I can see that? I think my solution is very far from the best and want to compare.

Thanks.

#23

At first I put an arbitrary limit of 2000 iterations, that solved the problem, but it didn’t let me sleep that night :smiley:
Then I put on a nice solution: said “a” the smallest number, you can just stop search as soon as you find “a” consecutive numbers that are not a solution. This stop the search just when needed, no computation waste at all. Pretty satisfied now :wink:

2 Likes
#24

If you solved it in javascript, you will see other javascript solutions; if you solved it in python3, you will see other python3 solutions.

If you solved it in a less common language and you are the first one to use it, you’ll see your own code only before another same language solution appears.

#25

I could never get my original algorithm to pass validator 8, no matter how I tried to tweak its magic numbers, so I went back to the drawing board and came up with a new algorithm. It is simpler, way faster and completely without any magic numbers. :slight_smile: (It’s published in Perl and Python.) Thanks to @geppoz for the idea to know when to stop searching.

#26

I tried really hard to figure this out, and it took 2 days. I finally got it by realizing, maybe if I knew what was possible, I could determine the impossible.
I think this is memoization - My degree isn’t in CS, so I don’t know a ton of algorithms etc…

1 Like
#29

I cheated and used a*b - a - b + 1 as the sieve size, where a,b are any two pairwise coprime numbers in the list. Any number above that can be served with just size a and b, by so clearly can be made with the full set of sizes. The cheat part is that it’s possible to have a set of 3+ numbers be coprime with no two of them being pairwise coprime…but that case did not arise in the tests or validators.

1 Like
#30

I don’t understand the problem. Why is the limit 3 with boxes of 2 and 5? Wouldn’t 11 be impossible too (and higher)? And then, why isn’t 7 the answer for boxes of 6 and 8? Why is there no maximum then?

This problem poorly explained.

#31

11 is not impossible … it is 1 box of 5 and 3 boxes of 2

and as said in statement it is impossible to serve odd number so the maximum in “infinite odd” . answer should be “The maximal number of nuggets that is impossible to get” and infinite is bigger than 7 …

1 Like
#32

Ok thanks, I get it now. Although I still think the problem could be made a lot clearer.

#33

Out of curiosity, what is your O(1) solution for n=2? I can’t find it.

#34

For n=2 the solution is:
(a−1)·b−a
and it exists only if a and b are coprime.

#35

That’s strange,

My program doesn’t pass the tests because of a time-out issue but is validated when I submit it !!!

#36

Not strange at all because tests are different from validators most of the time.

#38

:wave: Hi to all and thanks @Thib34 and (@Oioi, @Djoums and @UncleV as Validators) for this Puzzle …
→ after many tries/hours and different languages tested, i finally got 100% … in Objective-C …
→ this is only with your help from this forum,
→ specially about the 7th Validator (i stopped my main loop too early) !
=> so happy today … Thanks to you all :+1: !
Bye, have :sun_with_face: sun, :dark_sunglasses: fun and :keyboard: CodinGames …
and Good luck for all about the next CodinGame Fall Challenge next Monday :raised_hand: !