PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Shivam Gupta
Tester: Zhong Ziqian
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Case-based. Optimality and Probabilities.
PROBLEM:
Given N-1 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
- Whenever we use balance, We divide the coins into 3 piles. One each lying on balance both sides, and the third pile which is not put on balance.
- If the balance does not tilt, We know, that both sides have the same weight, which implies that the gold coin must be in the third pile. So, the problem reduces to the same smaller problem, with N being the size of third pile and K being K-1.
- If the balance tilts to any side, we know, that the coin is lying on one side of the balance. But we do not know which side it is lying. So, the problem reduces to the same smaller problem, with N being Number of coins lying on both sides combined, and K being K-1.
- Optimal strategy is to divide coins into piles, so that the maximum of Number of coins on both sides combined, and Number of coins not on balance, is Minimized.
- We can make cases on basis of N \bmod4. If N \bmod4==0, divide into piles of side N/4, N/4 and N/2. If N \bmod4==1, divide into piles of size N/4, N/4 and N/2+1 and if N \bmod4==3, divide into piles of size N/4+1, N/4+1 and N/2. Here, the division is floor division.
- N \bmod4==2 is a special case. If there are any other fake coins, we can divide into piles of size N/4, N/4+1 and N/2+1 and use one fake coin with the first pile. This way, the problem gets reduced to N/2 coins for the next step. Otherwise, we have to make piles of size N/4+1, N/4+1 and the remaining in the third pile.
- N = 2 is a special case, answer is always 1/2.
EXPLANATION
Let 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.
- We have fake coins which we have marked (Using balance second time or later).
- We do not have any fake coin till now (Using balance the first time).
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/2-1. 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 Complexity
Time complexity is O(min(K, logN)) per test case.
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. 