MAGICHF2 Editorial (Unofficial)

general
, , , ,
1

Problem Link:

 <a href = "https://www.codechef.com/NOV18B/problems/MAGICHF2"> Contest </a>

 

 <b>Author</b>: <a href="https://www.codechef.com/users/shivam_g1470">shivam_g1470</a> 

 <b>Editorialist</b>: <a href="https://www.codechef.com/users/srvptk">srvptk</a>

Difficulty: 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: 

         <b>double Compute(N,k)</b>{


 		     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 
           <b>result = 1.0</b>
</li>
<li>
   if <b>N</b>=<b>2</b> 

       <b>result = 0.5</b> 

   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 <b>0.5</b> irrespective of the value of <b>K</b>. 	   
</li>
<li>
   if <b>K</b>=<b>1</b> 

       If both hlaves are odd then we have to deal with <b>max(hlf1,hlf2)+1</b> coins in total (Observation). So, 

	   <b>result = 1.0/(max(hlf1,hlf2)+1)</b> 

	   Otherwise, 

	   <b>result = 1.0/max(hlf1,hlf2) </b>
</li>
<li>
   If we don't get into any of the above corner cases, we simply use: 

   <b> Compute(N,K) </b>
</li>
## Time Complexity: O(logN) for every case. ## Implementation: Editorialist Solution
1 Like
2

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.

3

I derived what I thought was a correct solution, but it was rejected as a ā€˜Wrong Answerā€™.

As an example, my logic was as follows:

(1) Suppose we have N = 4, K = 1

We put 1 coin into each scale. Whether they are equal or not, we have 2 to choose from.
The answer is 1 / 2.

(2) Suppose we have N = 6, K = 1

We put 2 coins into each scale. If they are equal, then we have 4 to choose from.
The answer is 1 / 4.

(3) Suppose we have N = 6, K = 2.

For the first step, weigh as for K = 1.
If in the first step the coins are equal, proceed with the 4 as for example (1).

If they are unequal, then one of the others is the real coin.
In this case we swap one of the coins, and weigh again,
and definitely have the answer. This situation is not relevant here.

(4) Now suppose we have N = 12, K = 2

For the first step we put 3 coins into each scale.
Whether they are equal or not, we have 6 to choose from.

For the second step we proceed with the 6 as for example (2), answer 1/4.

However for the method described, and in one of the solutions I downloaded,
the solution to the second step is 1 / 3, which I believe to be WRONG.

Have I missed something?

My algorithm and its implementation are is

            long num = 1;
            if (k == 0 || n <= 2) {
                // When K = 0, the solution is simply 1 / N.
                // When only 2, we can never tell which coin is real, solution is 1 / 2.
                num = n;
            } else if (k < 63) {
                // Most of the time the solution is 1 / (2 * (floor((N - 1) / 2^(K+1)) + 1)).
                // Subtract 1 when the last binary digit of N is 1, 
                // and the previous K digits are 0.
                long numn = ( n - 1 ) >> 1;
                for (int i = 0; i < k; ++i) {
                    num = numn;
                    if (num <= 0)
                        break;
                    numn >>= 1;
                }
                if (num <= 0) {
                    // after enough weighings we are certain of the result
                    num = 1;
                } else {
                    long diff = n - ( numn << ( k + 1 ));
                    num = ( numn + 1 ) << 1;
                    if (diff == 1)
                        --num;
                }
            }

            double prob = 1 / (double) num;
4

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

1 Like
5

@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

6

Yes,you have missed something. In N=12 K=2 ,in first step six coins will be left and six eliminated. But,in second step when we have six coins left we can divide six into three each and check three coins with any three eliminated coins i.e we will compare any three left coins with any three eliminated coins because we know that any 3 eliminated coins are fake. So,probability for N=12,K=2 is 1/3. Similarly,for N=20 K=2 answer is 1/5 not 1/4 which will be according to your logic.

7

Thank you for this explanation! I had indeed missed this possibility.

8

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.