Problem Link:ContestAuthor: shivam_g1470 Editorialist: srvptk Difficulty:EasyPrerequisites:Divide and Conquer, Recursion, MathsProblem:Chef has N coins out of which 1 is real and other (N1) coins are fake. He has to find the maximum probability in worst case to determine the real coin with the help of a balance by using it upto K times.Explanation:This problem can be solved through a divide and conquer approach. Everytime we have N coins, we will be dividing it into two approximately equal halves and process the larger one. When we divide the N coins into two halves then we can use the balance to determine whether the coin is in one of the halves. If we checked either of the half for a real coin and failed then we will continue our search with other half, otherwise we would search the checked half.As we are interested in the worst case scenario, so we would always go with the larger half. By this approach our problem can be solved in logN time, which can successfully be applied for N<=10^18. When we can no longer use the balance then we have to select one of the coin to be real from the remaining part left unsearched, and the probability of finding a real coin will be: 1/(no. of remaining coins) Recursive Approach:double Compute(N,k){ if(k>=N){ return 1.0 } if(k==0){ return 1.0/(double)N } hlf1 = N/2 hlf2 = (Nhlf1) return Compute( max(hlf1,hlf2), k1) } Corner Cases:Now we have to deal with some corner cases. My solution had to deal with three corner cases, these were:
Time Complexity:O(logN) for every case.Implementation:Editorialist Solutionasked 12 Nov, 17:16

@david_s You are completely ignoring the fake coins after eliminating them. (We are allowed to reuse them). So, for example, if we have 12 coins and 2 measurements, we first eliminate 6 coins by the method you argued. But for the remaining 6 coins we can measure 3 of the new ones to 3 of the old ones, thus eliminating at most 3 at this stage, leading to probability 1/3. The trick here is that, if at any stage, we are left with (4k+2) coins, we can reduce it to (2k+2) if we do not have any extra coins, else we can further reduce it to (2k+1) in presence of extra coins. Here's my implementation. answered 13 Nov, 12:02

@david_s I spent a whole day making the same mistake as you did, until I decided to read some of the wikipedia pages on balancing coins problem, and suddenly remembering that you can REUSE the elimninated coins that you are sure to be correct. All I did was adding 1 line to the code and it turns into an AC. Sad for you that you didn't see the problem. In the 10 2 case, you eliminate down to 6 coins first, but then you can eliminate down to 3 coins by weighing 3 of them with the 3 out of 4 coins that you already know are correct. So the answer is 1 / 3 answered 13 Nov, 17:15
