[Community Puzzle] Nuggets numbers

https://www.codingame.com/training/hard/nuggets-numbers

Send your feedback or ask for help here!

Created by @Thib34,validated by @Oioi,@Djoums and @UncleV.
If you have any issues, feel free to ping them.

1 Like

Should be moved to easy?

2 Likes

It was medium when I approved it, which was fine imo.

Nice it is became best
:smile:

1 Like

Tho I could write a 6 lines solution in Python, it requires DP or memoization and good understanding of gcd’s properties so it’s eather a hard Medium or an easy Hard.

@pardouin: My guess is that you missed the easy (and probably more efficient) way to solve this puzzle. :frowning:

In my opinion, putting back this puzzle in medium would give players a hint about the existence of a trick.

I checked your haskell solution and you use gcd and memoization so I don’t see how it contradicts what I was saying.

1 Like

Easy or medium. LOL… I’ve got to be stupid since I’m struggling since 2 days on it. Read a lot of math algorithm but couldn’t find a solutio. Oh yeah, I’ve one but for last steps it’s too time consuming.

So I’m stuck. Somebody can help ?

I’m on the same boat. I have time issues only on the last test. I’m missing a trick I guess.

Nice puzzle, and I agree for placement in the Hard section. My brain is in fire !

Just one sad thing, 8/8 on the tests cases, but only 6/8 for the validators :face_with_raised_eyebrow:
Strange, and it will be hard to find out what’s wrong :cry:

@Thib34 is it possible to take a look to the validators 5 and 7 ?

Memoization is the key, take a look at this technique.

Hi,
Any help please i 've only 62%? i code with python

@Oioi, @Djoums.
I’m having problems with valitator 7, what should i review?

Here is validator 7

Input
15
411
366
138
930
648
969
318
189
756
414
195
360
417
573
675

Output
-1

Edit : it was the wrong one

You are wrong, it’s not validator 7, it’s the 8th test.

Validator 7
15
411
366
138
930
648
969
318
189
756
414
195
360
417
573
675

Output
-1

There is a O(1) solution for the case n=2,
I’m studying for find also the O(1) solution for the case n=3, (of course not useful for this puzzle, since it is not enough, but just for math curiosity), it seems to me that it should exists.
I have already an “almost working” formula :wink: , any math nerd that wants struggle on it?

No need for maths here. I built the sieve like a horse race.

I’m having trouble with Validator 8. Any hints would be appreciated.

You should ensure the sieve is large enough, and at the same time not too large to cause timeout.

@nicola do you have a suggestion how to dynamically find a suitable max size of the sieve to use?

No, I used a magic number here. :grin: