Harolinch's blog

By Harolinch, history, 6 years ago, In English

this problem killed me... can anyone help me with it ?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is the outline of the solution.

  1. If at time t, Alexander is ahead of Arthur, then at time t + 1, also Alexander will be ahead of Arthur
  2. If at time t, Alexander is behind Arthur, then even at time t — 1, also Alexander will be behind Arthur.

This allows us to use binary search !

Now, we need a way to answer the following question — Given a time t, how do we find out who is ahead ? Once we know the answer to this question, we simply binary search over time t.

Now, Alexander will simply have c — t at time t.

What about Arthur ?

The value of a decreases by the number of times b falls below w.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Búsqueda binaria.