×

# MAGICHF2 Editorial (Unofficial)

Contest

Author: shivam_g1470
Editorialist: srvptk

Easy

# Prerequisites:

Divide and Conquer, Recursion, Maths

# Problem:

Chef has N coins out of which 1 is real and other (N-1) 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 = (N-hlf1)
return Compute( max(hlf1,hlf2), k-1)

}

### Corner Cases:

Now we have to deal with some corner cases. My solution had to deal with three corner cases, these were:
1. if N=1
result = 1.0
2. if N=2
result = 0.5
Doesn't matter how many times we use the balance, we won't be able to find the real coin among the two. So, the probability of finding a real coin will always be 0.5 irrespective of the value of K.
3. if K=1
If both hlaves are odd then we have to deal with max(hlf1,hlf2)+1 coins in total (Observation). So,
result = 1.0/(max(hlf1,hlf2)+1)
Otherwise,
result = 1.0/max(hlf1,hlf2)
4. If we don't get into any of the above corner cases, we simply use:
Compute(N,K)

# Time Complexity:

O(logN) for every case.

# Implementation:

Editorialist Solution

4★srvptk
102
accept rate: 0%

 0 @david_s You are completely ignoring the fake coins after eliminating them. (We are allowed to re-use 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. https://www.codechef.com/viewsolution/21510908 answered 13 Nov, 12:02 21●2 accept rate: 25%
 0 @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 6★ducpro 240●1●7 accept rate: 0%
 -1 The question is quite simple once I read this solution. On the other hand, the question statement and sample testcases are very much incomplete. I didn't realize until now that we could put multiple coins on the scale and weigh them together. -_- Only if I had realized this, I'd have solved it right away. In my humble opinion, nobody actually learns anything if the problem statement is itself so incomplete. It rather becomes a matter of luck. answered 13 Nov, 04:01 4★omerjerk 9●2 accept rate: 0% 1 The balance is magical — it stays balanced when the sums of weights of coins put on each side....... ig u could infer from this that multiple coins can be on the balance (13 Nov, 12:34) Obviously I could have. But I missed this small detail. That's my whole point. Problem setter could have written down the "specifications" of the scale properly and not hide it in words. Thank you. (14 Nov, 22:50) omerjerk4★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,163
×326
×196
×132
×9