Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Westicles,validated by @pluieciel,@CeliTop and @jk_java.

If you have any issues, feel free to ping them.

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Westicles,validated by @pluieciel,@CeliTop and @jk_java.

If you have any issues, feel free to ping them.

I donât know American roulette. Per the description, 0 ought to be a number. Is â00â considered as a number too?

Yes, so 38 in all.

I published the fastest C++ code I came up with (6M runs), and am curious to see faster random implementations.

I ran 100,000 iterations in Python.

How is it an easy puzzle? Cannot solve with normal formulas, as well as Bernoulliâs formula do not work for this.

No formulas required, just use brute force monkey method

2 Likes

If you donât want to go with a Monte Carlo solution, try to recursively solve the sub-problem âpick exactly k different numbersâ .

The recursive relation is not hard to find and doesnât require much knowledge.

If itâs too slow you might want to memoize it.

You can also expess the result with a double summation formula but itâs harder to find.

2 Likes

Yeah, the math is pretty interesting. It is easy to work out a recursive approach (which leads you to independently rediscovering Stirling numbers), and the real math guys would probably just crank out the simple equation with inclusion/exclusion.

But the only way it fits in easy is the brute force monkey method.

1 Like

7 1-stars now! Iâm afraid our esteemed math professors on the continent are stumped by this one!

lol really? Thatâs nuts. Itâs kinda clear what youâre being asked to do, hence the easy approach is fairly obvious.

1 Like

I like the brute-force approach.

But strictly speaking, throwing the dice a million times to know the probability of some combinations does not prove this % result is correct. At least the author has to put together a mathematical calculation to prove that the experimental results are theoretically correct.

1 Like

As you can see, there is a python implementation using inclusion/exclusion in the solution.

Do you know why almost all who solved this puzzle are from top players here? You are talking about the monkey method, but how many years youâve been programming before you find out about this method? I thought that Easy puzzles are for newbies, like me, who just started learning about all of this. Because there is no explanation for this puzzle and no clear way for me to solve it, so 1 star

Actually, within the âeasyâ puzzles, you have different difficulties. Donât hesitate to ask for something which could help training you. But every puzzle categorized as âeasyâ can be solved with paper and pen, that is why there are in this category.

Medium puzzles need more complex approach, and sometimes dedicated algorithms or difficult mathematical formulas to solve. As it is not the case for this one, it is in easy.

Donât forget : being stuck on a problem is not a reason to be mad, but a way to improve your skills. Try something different, learn on the internet, and you will laugh at your difficulties in a short amount of time.

3 Likes

Thank you for the explanation. Iâm not mad, just curious. Also, wanted to explain why there are so many 1 stars. I think, there would be less 1 stars if there will be some hints about the solution (links on youtube where someone digs into a theme that is related to the puzzle or some other links to have a clue about the solution)

Maybe because of flock behaviourâŚ

1 Like

I have no idea who gives you poor ratings but it might not be who youâre thinking about.

If I remember well, the day I solved this one, there were only good ratings, included mine (and probably Nicolaâs who solved it before me).

I think math oriented puzzles tend to receive mixed review, some people think that âCG is not project Eulerâ and it probably explains part of the bad ratings.

That and the fact that some people donât think it fits the easy category.

3 Likes

No worries, I taunted the fr with it on cheloniangall and got 4 1-stars in 10 minutes. Kind of deserved it

I keep getting time out error using recursion.

Any help/guide with algorithm optimization?

Iâm pretty sure Iâm missing something obvious, but canât quite get it.