To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards the stick and moves on to the next stick. Note that Py can compare relative lengths of all already seen sticks.
Note that: The answer is considered correct if the absolute or relative error does not exceed 10e-7
Constraints: 1 <= N <= 10e5
Sample Inputs and Outputs:(n -> probability)
- 1 -> 1
- 2 -> 0.5
- 3 -> 0.5
- 10 -> 0.398690476190
Notes: In the first test, Py chooses the first stick because it is the only one stick. In the second test, it does not matter if he/she chooses the first or the second stick. The probability of choosing the longest one is 0.5. In the third example, he bypasses the first stick, because if Py chooses it the probability would be 1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first one Py moves on to the third one.
My Attempt: I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?