need help in this question

[1vRz3TCk]

It would be better if you explained how you think it would go. Then we might be able to guide you to a better understanding of the problem.

[hasura]

@CodeMonkey

Let us assume there are n coins 1,2,3...n (n being the real coin)

Initially I thought the best strategy to waste k chances unknowingly is to use 2 coins in the balance starting from LHS to RHS. But this gave WA.

Then I thought the following way,
- On odd turn of k we will weigh all remaining coins whose identity is unknown till now (half on each side of balance and the coins will contain real coin also). This won't reveal identity of any coin
- On even turn of k we will weigh the part that doesn't contain the real coin in groups of 2. This will reveal the identity of k*2 coins (them being fake = identity revealed)
- Continue this way until either k is exhausted or identity of all coins is revealed.

And finally ans = 1 / (number of unknown coins)

The above method gives minimum possible probability but it still gives WA (not optimal.. I didn't understood how?)

[1vRz3TCk]

hasura wrote:

- On odd turn of k we will weigh all remaining coins whose identity is unknown till now (half on each side of balance and the coins will contain real coin also). This won't reveal identity of any coin

This will not help. You alway need to put some on the scales and leave some off, so each weighing helps you narrow it down. Don't forget that effectively the scales only tell you if the real coin is on the scale or not.

[hasura]

@CodeMonkey Every time while weighing should the real coin be included or not in one of the sides of balance?

[1vRz3TCk]

The idea is you do not know which coin is the real coin. You may need to reread the question.

[tpb]

So what's the probability for the n=11, k=1 case? It seems to me that it's the same as guessing without any weighing, 1/11.

I'm also thinking the n=11, k=3 case is 3/22.

[Browni3141]

tpb wrote:

So what's the probability for the n=11, k=1 case? It seems to me that it's the same as guessing without any weighing, 1/11.

I'm also thinking the n=11, k=3 case is 3/22.

I think the greatest challenge for this problem is understanding the problem's wording.

What happens when you weigh two coins against each other?

Case A:

The scale balances and we can rule out those two coins as being the real. There are 9 unknown coins left so it's a 1/9 guess.

Case B:

The scale doesn't balance so we know one of the two coins is gold. There are two unknown coins left so it's a 1/2 guess.

We only consider the worst case, so if we use the strategy of weighing only one coin against another, the answer is 1/9. This answer is not optimal. The goal of the problem is to find the best worst case.

[tpb]

@Browni3141, do you know the correct answer for n=11,k=1 and n=11,k=3? Are you saying you think/know that my guesses are wrong?

[Browni3141]

tpb wrote:

@Browni3141, do you know the correct answer for n=11,k=1 and n=11,k=3? Are you saying you think/know that my guesses are wrong?

Yes, I have solved all of the problems in Division 2. I'm trying not to help beyond understanding the problem statement. I don't know how strict CodeChef is supposed to be about these contests.

[tpb]

I'm not doing the contest, but I don't mind waiting. I assume the answer will become available soon?

[Browni3141]

All the solutions are available now on the site. I used a simple recursive solution for this one. At every step we try to eliminate half the coins. Sorry if the winProbability function looks a little obscure. I should have simply treated the root differently and the code would look a little nicer. I could have implemented a lookup table, but it wasn't necessary for my submission to finish in time.

#include <iostream>

using namespace std;

double winProbability(uint64_t, uint64_t, uint64_t);

int main()
{
    std::ios::sync_with_stdio(false);
    uint64_t T, N, K;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> N >> K;
        cout << winProbability(N, K, 0) << '\n';
    }
    return 0;
}

double winProbability(uint64_t unknownCoins, uint64_t remainingAttempts, uint64_t fakeCoins)
{
    if (unknownCoins == 1)
        return 1.0;
    if (remainingAttempts == 0)
        return 1/double(unknownCoins);
    if (unknownCoins%2 == 1 || (unknownCoins>>1)%2 == 0 || (unknownCoins>>1) <= fakeCoins)
        return winProbability(unknownCoins-(unknownCoins>>1), remainingAttempts-1, fakeCoins+(unknownCoins>>1));
    else
        return winProbability((unknownCoins>>1)+1, remainingAttempts-1, fakeCoins+(unknownCoins>>1)-1);
}

There is a special case when unknownCoins mod 2 == 0 and (unknowncoins>>1) mod 2 == 1. For example:
n = 10, k = 1. We would like to eliminate 5 coins. The only way to do this is to weigh 5 coins against 5 other coins. This only works if we have identified at least 5 fake coins already. Otherwise, we measure a group of 3 == 3 and only get to eliminate 4 coins.

n = 10, k = 1 : weigh 3 == 3 and guess 1/6
However:
n = 20, k = 2 : 1/5 because:
n = 20, k = 2 : weigh 5 == 5
n = 10, k = 1 : weigh 5 == 5 using known fakes from the last step.
n = 5, k = 0 : guess 1/5


for n = 13, k = 3: weigh 3 == 3 and the scale will balance, we're left with 7unkwown coins and 2 tries.

n = 7, k = 2 : weigh 2 == 2
n = 3, k = 1 : weigh 1 == 1

n = 2, k = 0 : No more tries, guess 1/2.