You are not logged in. Please login at www.codechef.com to post your questions!

×

MAGICHF2 Editorial (Unofficial)

Problem Link:

Contest

Author: shivam_g1470
Editorialist: srvptk

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:


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

asked 12 Nov, 17:16

srvptk's gravatar image

4★srvptk
102
accept rate: 0%

edited 12 Nov, 17:48


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;
link

answered 13 Nov, 05:53

david_s's gravatar image

4★david_s
911
accept rate: 14%

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.

(13 Nov, 17:46) rajankur5★

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

(14 Nov, 05:11) david_s4★

@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

link

answered 13 Nov, 12:02

masood786's gravatar image

3★masood786
212
accept rate: 25%

edited 13 Nov, 12:21

@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

link

answered 13 Nov, 17:15

ducpro's gravatar image

6★ducpro
24017
accept rate: 0%

edited 13 Nov, 17:16

-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.

link

answered 13 Nov, 04:01

omerjerk's gravatar image

4★omerjerk
92
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) vikaskodag984★

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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 12 Nov, 17:16

question was seen: 573 times

last updated: 14 Nov, 22:50