PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Abdullah Aslam
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Probability, Modular arithmetic and a bit of proof. (Setter says “Proof by intuition”).
PROBLEM:
There are initially N indistinguishable boxes, exactly one of them containing one magic pill. You have to find the probability of finding the box containing the magic pill in at least one operation when you can perform operation M times.
In one operation, you can do either one of the following two.
- Make a guess. If the chef finds the box, the game is over. Otherwise, K more indistinguishable empty boxes are added every time a guess is made. Let’s call it a guess operation.
- Remove i*K boxes such that i \geq 0 and i*K \leq X where X is the number of boxes present. No guess is made here. Let’s call it a remove operation.
Important to notice is that N < K.
QUICK EXPLANATION
- When only one operation is left, it is better to make a guess, increasing the probability of winning.
- Otherwise, we can always make a remove operation in the current move and guess operation in next move which gives better probability than making two guesses in two moves.
- To simplify calculating probability, notice that it is easier to calculate the probability of losing and then take its complement.
EXPLANATION
First thing, Let us consider it’s the last move. It’s obvious that making a guess now is better, than making a remove because making a guess increases your chances of winning. The final number of boxes is useless.
Secondly, At any point during the game, Number of boxes is X = N+x*K for some x \geq 0 When performing remove operation, we always choose to remove the maximum number of boxes we can (to maximize win probability), which happens to be x*K, leaving N boxes behind. This also implies that if the number of boxes is N before the current move, it makes sense to make a guess, since remove operation cannot remove any box at all. So, strategy maximizing win probability never have two consecutive remove operations.
Remember K > N. Let’s assume K = N+d.
If we have N boxes, it’s obvious we make a guess. The number of boxes becomes 2*N+d.
Now comes the interesting part. Suppose we have more than one move remaining, with 2*N+d boxes before the current move, with the second move being a guess move. Now, what is better? The first move to be a guess move or to be a remove operation.
Let’s analyze both cases.
In the first case, the Number of boxes before the second move is N, winning probability in these two moves is 1/N.
In the second case, Probability of win = P(win at first move)+P(win at second move) - P(win at both moves). The number of boxes before the second moves is 3*N+2*d. So, the probability becomes
\frac{1}{2*N+d} + \frac{1}{3*N+2*d} - \frac{1}{(2*N+d)*(3*N+2*d)} = \frac{5*N+3*d-1}{(2*N+d)*(3*N+2*d)}. Lets multiply numerator by N, we have \frac{5*N^2+3*d*N-N}{6*N^2+7*d*n+2*d^2}. It can be seen, that with N,d \geq 1, this probability is always less than 1. Dividing both sides with N, we have \frac{5*N+3*d-1}{6*N^2+7*d*N+2*d^2} < \frac{1}{N}.
Hence, we can see, that it is better to perform a remove operation and then make a guess, rather than making two consecutive guesses when we have N+K boxes available.
So, our final optimal strategy looks like. Make a guess. The number of boxes now is N+K. Perform remove and make another guess and so on. But as we noted earlier, the Last move shall always be guessing, which we shall ensure (There is two consecutive guess in the end when M is even).
Now, if M is odd, we are making (M+1)/2 guess when at each guess we have N boxes. It shall be complicated to handle inclusion-exclusion here, and the simpler way is to calculate the probability of losing and takes its complement. The probability of losing is just the product of the probability of losing at each turn.
Probability of losing is \frac{(N-1)^{(M+1)/2}}{N^{(M+1)/2}}. So, probability of winning become 1-\frac{(N-1)^{(M+1)/2}}{N^{(M+1)/2}}.
When M is even, we have M/2 guesses with N boxes present, and one guess (last one) with N+K boxes. Probability of winning here is 1-\frac{(N+K-1)*(N-1)^{M/2}}{(N+K)*N^{M/2}}.
Implementation is left as an exercise.
Time Complexity
Time complexity here is O(log(M)) per test case due to fast power.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
