Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### ahmed_aly's blog

By ahmed_aly, 9 years ago, ,
This is my approach for this problem, and I don't know why it's wrong.

1- Let X be the smallest power of 2 which is greater than or equal to N.
2- Let X = 2 ^ P.
3- Make P tosses to generate a random binary number consisting of P bits, let's call it I.
4- If I is less than N, so the king selects the Ith knight (0-indexed).
5- Otherwise, repeat again starting from step 3.

Now the final result should be:
F(N) = P + [(X - N) / X] * F(N)
F(N) - [(X - N) / X] * F(N) = P
F(N) * (1 - [(X - N) / X]) = P
F(N) = P / (1 - [(X - N) / X])

I'm sure this will select a knight with equal probability, but I'm not sure if it's the minimum expected number of tosses.

Is there anything wrong in my approach or is it my calculations?

• +5

 9 years ago, # |   0 Try n = 5. Author's wrong (I assume not optimal) solution gives 22/5 and natalia's (560061) solution 18/5, whilst using this approach you get 24/5.
•  9 years ago, # ^ |   0 So, what is the correct approach?
•  9 years ago, # ^ | ← Rev. 3 →   +5 They found that correct approach is unusable due to time complexity as I understood (for 10^17 etc). ;-)For your solution (mine is the same) here is counter-example:Regard n=10. We toss the coin 4 times to get one of 16 variants. If variant is higher than 10 but less than 16, we can use its result (1 of 5) to select one of 5 pairs of knights, after that we could toss the coin only once to choose one of them. Am I not right?I do not know what to do with this example, but I hope that you (being far more professional sportsman than I) could find it out.
•  9 years ago, # ^ |   0 We will see it in editorial :)
•  9 years ago, # ^ |   +1 However it is far more funny to try solving problems which have no (known) solution... I liked this problem much and I am thankful to its author.Maybe it is good idea to include one problem without solution in each round... Looking for best or fastest approximation for example...
•  9 years ago, # ^ |   +5 « Maybe it is good idea to include one problem without solution in each round... Looking for best or fastest approximation for example... »→ That's called a Topcoder's Marathon match ...