### ahmed_aly's blog

By ahmed_aly, 8 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? Tutorial of Codeforces Beta Round #78 (Div. 2 Only)  Comments (6)
 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.
•  So, what is the correct approach?
•  8 years ago, # ^ | ← Rev. 3 →   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.
•  We will see it in editorial :)
•  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...
•  « 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 ...