ahmed_aly's blog

Solution for problem B in round 78
By ahmed_aly, 13 years ago, In English
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?
  • Vote: I like it
  • +5
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    So, what is the correct approach?
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      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.
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      We will see it in editorial :)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        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...
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          « 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 ...
          → Reply