PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The problem can be solved with a binary search approach. Given a value D, we can efficiently determine if there is a way to move each person with distance at most D or not. The idea is that we can assume that the left-most person moved as far left as they can. Then, the second person moves as far left as they can up to distance D or until they are T units next to the first person. Basically, the first person moves to x’ _ 1 := max(0, x _ 1-D) and every subsequent person i moves to x’ _ i := max(x’_ {i-1}+T, x _ i-D). If this max ever moves someone more than D units to the right, then we report that distance D is not sufficient. Otherwise, we report that distance D is ok. Of course, if
distance D suffices then any distance D’ >= D will also work so the binary search approach will succeed.
The output precision was chosen to be 4 decimals because the input precision was 3 decimals and one can argue that the solution is always
an integer multiple of 0.0005. It’s a fun exercise.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.