PROBLEM LINK:Practice Setter: Shivam Gupta DIFFICULTY:Easy PREREQUISITES:Casebased. Optimality and Probabilities. PROBLEM:Given $N1$ Fake coins and one gold coin, We need to find the Minimum probability of finding the gold Coin if we are allowed to use the Balance $K$ times. All coins are same in appearance, and all fake coins have the same weight too, but the gold coin has different weight. We can use balance. If we have the same weight on both sides, it stays balanced, otherwise, it may tilt to any side. NOT SO QUICK EXPLANATION
EXPLANATIONLet us handle base cases first. If $N = 1$, we only have the gold coin, hence the probability of finding gold coin is $1$. (Unless you don't want to find. :P) If $N = 2$, we can never find the gold coin, because even if we try to use the balance with each coin on either side, the balance shall always tilt, giving us no information about which coin is the gold coin. Hence, the probability is $1/2$. Assume we mark the coins we identify as fake. This will be helpful later. Now, coming to the general case, See, that In the end, Chef is playing optimally, so he wants to maximize the probability of finding the gold coin. So, he'll want to reject as many fake coins as he can using balance optimally. Now, As per problem, we are to assume the worst case always, We will consider the way, by which the chef is left with the largest number of fake coins to filter. See the working of balance. It just tells us whether the weight of two piles of coins, lying on either side of the balance, is equal or not. Tilting balance doesn't tell anything at all. Now, we can see, that every time we use balance, we are actually dividing the coins into 3 piles, One pile on one side of the balance, second pile on the other side of the balance, and third pile which is not kept on balance. Now, If the balance does not tilt, the weight of coins of the first two piles is same, which means, that we don't have the real coin in any of the two piles on balance. Since we are to assume the worst case for the chef, the gold coin will be on the balance, if the number of coins on both sides of the balance shall be greater than coins not on balance. So, Optimality for the chef is to minimize the maximum of Coins on balance and coins not on balance. Since we can put an equal number of coins on both sides, we end up having four cases. If $N \bmod4 == 0$ In this case, we can make three piles, of sizes $N/4$, $N/4$ and $N/2$, place first two on either side of the balance. The Maximum of coins on balance and coins not on balance is $max(N/4+N/4, N/2) = N/2$. We can see, we cannot get any better. If $N \bmod4 == 1$, we have to put that one coin in the third pile, since we have to place the same number of coins on both sides of the balance. Hence, the piles will be made as $N/4$, $N/4$ and $N/2+1$. The Maximum of coins on balance and coins not on balance is $max(N/4+N/4, N/2+1) = N/2+1$. If $N \bmod 4 == 2$, This is a special case. Now marking the fake coins come useful. See, We want to divide the coins into piles such that the maximum comes out to be $\bmod N/2$. There are two possibilities.
If we have a spare fake coin which we have marked, we can use it to balance the number of coins on both sides of the balance. Hence, we can make piles of size $N/4$, $N/4+1$ and $N/2$. Place the spare fake coin with pile first so as to balance the number of coins on both sides. The Maximum number of coins on balance and coins not on balance is $max(N/4+1+N/4+1, N/2) = N/2+1$, but, since we have the spare coin marked, we can directly identify it, hence, The number of coins, out of which we need to find the gold coin is $max(N/4+1+N/4+1 1, N/2)$ which comes out to be $N/2$. Suppose we do not have any fake coin, So, we will have to make piles of side either $N/4$, $N/4$ and $N/2+1$, or $N/4+1$, $N/4+1$ and $N/21$. We can see, that the maximum Number of coins left shall, in both cases, be $N/2+1$. Consider an example, Suppose we are left with 14 coins out of which one is the gold coin. We see, $14 \bmod4 = 2$. Assume we have a spare fake coin. So, we can make piles of size 3, 4 and 7 respectively and use the spare coin with the first pile. This way, on balance we have 4 coins on each side. If it balances, the gold coin is in 7 coins not put on the balance. If it tilts, the gold coin is on balance. But the spare coin is marked, so, the number of unidentified coins is 7. So, in the worst case, we are left with 7 unidentified coins. Now, If in the same example, we do not have a spare fake coin, we will have to make piles of size 3,3,8 or piles of size 4,4,6. We can see, that in the first case, the worst case will be when the gold coin is not on balance, resulting in 8 unidentified coins. In the second case, If the coin is on balance, the number of unidentified coins is 8. If $N \bmod4==3$, Only optimal configuration is piles of size $N/4+1$, $N/4+1$ and $N/2+1$. The maximum number of coins come out to be $N/2+1$. This way, we can use the balance optimally and in the end, after using balance $K$ times, we would be left with a set of, say $X$ coins. Now, the probability of picking the gold coin is $1/X$, Since there is one gold coin and rest are fake. Implementation For implementing above, The critical thing to notice is that after using balance every time, we reduce the number of unidentified coins by half. We can see, that in $K$ steps, we can roughly find out gold coin out of $2^K$ coins. Upper limit on $N$ is $10^{18}$, so, $log_2 (10^{18})$ comes out something like $59.79 < 60$. So, we can simulate the balance up to $min(K, 60)$ steps and find out the answer. Time ComplexityTime complexity is $O(min(K, logN))$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 09 Nov '18, 23:27

Here is video editorial available to this problem  https://youtu.be/zXmhkuL3l9I answered 21 Dec '18, 21:00

The notsoquick explanation says: For N % 4 == 3, divide the piles into sizes N/4+1, N/4+1 and N/2, whereas the explanation says: divide them into sizes N/4+1, N/4+1 and N/2+1. I think there's a mistake in the latter one. Also, when I read the notsoquick explanation. My initial thinking was that the sizes must be N/4+1, N/4+1 and N/2+1. But then I realized since we are using floor division, and N = 4k+3, N / 2 = 2k+1, which gives us the 3rd extra coin. So, rather than going this way and using N/2, I did it like this: Each pile is of size M = N/4 (floor division). In case N % 4 == 3, the pile sizes are M + 1, M + 1, 2M + 1. So, worst case is 2M + 2 coins. I found this way to be more intuitive. I haven't read the complete explanation, just read the notsoquick explanation, so correct me if I'm wrong somewhere. answered 17 Nov '18, 11:18
