Can anyone explain the approach mentioned in the editorial for Run Direction in detail?
I am not able to understand the greedy approach and also how can we apply binary search?
I am not able to understand the intuition behind binary search on this problem.
Thanks!
Consider the function:
p(t)=\begin{cases}\text{True},\quad \text{if it is possible to avoid passing before time }t,\\\text{False},\quad \text{otherwise.}\end{cases}
If we had such a function we could use a binary search to approximate the optimal time t. Here we don’t actually have to find the optimal configuration: we just bound t from above and below.
In the editorial the a greedy algorithm is used to implement this function p(t).
My dynamic programming solution (link) might be easier to understand and could also be helpful in understanding the greedy method that was used in the editorial. Like the dynamic programming solution, the greedy solution starts by sorting the children by the starting position. We then work through the children from left to right.
Each time we consider a new child we only need to check when that child passes the most recently added child before time t. If the most recently added child is running to the left that makes it easiest to avoid a crossing. For that reason we always try to add new children running to the left. If that is not possible without crossing the previous child before time t, then we try to add the new child running to right. If that is still not possible then no configuration of the children avoids crossing before time t.
Notice that this greedy algorithm does not give us the optimal configuration: it simply tells us if the optimal is less than t. It essentially evaluates p(t).
2 Likes
Thanks! Your answer helped me to understand it.