← All solutions

There are two observations to make in this problem. The first, minor observation, is that the answer, if finite, is at most B (where B is the bound on the coordinates). This means that we can do a binary search for the longest possible survival time, answering “infinity” if it exceeds B.

To check if one can survive for T time steps, the main observation is that it suffices to check if there is some point that is reachable in T steps that no mummy can reach in T steps. This amounts to checking whether the union of n squares of side length 2T + 1 completely cover another square of side length 2T + 1. This can be done in n log n time using a standard sweepline approach.