Let's say you have a 20-sided die. You start rolling that die and have to roll it a few dozen times before you finally roll all 20 values. You wonder, how many rolls do I need before I get a 50% chance of seeing all 20 values? And how many rolls of an
n-sided die do I need to roll before I roll all
After some research, you find out that a formula exists for calculating the chance of rolling all
n values after
P(r, n) = n! * S(r, n) / n**r
S(a, b) denotes Stirling numbers of the second kind, the number of ways to partition a set of n objects (each roll) into k non-empty subsets (each side).
You also find the OEIS sequence, which we'll call
R(n), that corresponds to the smallest
P(r, n) is at least 50%. The challenge is to calculate the
nth term of this sequence as fast as possible.
- Given an
n, find the smallest
P(r, n)is greater than or equal to
- Your code should theoretically handle any non-negative integer
nas input, but we will only be testing your code in the range of
1 <= n <= 1000000.
- For scoring, we will be take the total time required to run
- We will check if your solutions are correct by running our version of
R(n)on your output to see if
P(your_output, n) >= 0.5and
P(your_output - 1, n) < 0.5, i.e. that your output is actually the smallest
rfor a given
- You may use any definition for
S(a, b)in your solution. Wikipedia has several definitions that may be helpful here.
- You may use built-ins in your solutions, including those that calculate
S(a, b), or even those that calculate
- You can hardcode up to 1000 values of
R(n)and a million Stirling numbers, though neither of these are hard limits, and can be changed if you can make a convincing argument for raising or lowering them.
- You don't need to check every possible
rwe're looking for, but you do need to find the smallest
rand not just any
P(r, n) >= 0.5.
- Your program must use a language that is freely runnable on Windows 10.
The specifications of the computer that will test your solutions are
i7 4790k, 8 GB RAM. Thanks to @DJMcMayhem for providing his computer for the testing. Feel free to add your own unofficial timing for reference, but the official timing will be provided later once DJ can test it.
n R(n) 1 1 2 2 3 5 4 7 5 10 6 13 20 67 # our 20-sided die 52 225 # how many cards from a huge uniformly random pile until we get a full deck 100 497 366 2294 # number of people for to get 366 distinct birthdays 1000 7274 2000 15934 5000 44418 10000 95768 100000 1187943 1000000 14182022
Let me know if you have any questions or suggestions. Good luck and good optimizing!