Mummy Madness

Instead of finding out how far we can get, we'll instead binary search on whether we can survive for some fixed number of days. Now the only challenge is to figure out if we can survive for some N days.

Fortunately it suffices to see if there is any point on the graph WE can reach in N days, but the mummies can't.

Rough Proof: Suppose the mummies can't reach the point we're aiming for, but can get us along the path. If they could get us along the path, and can move at least as fast as us, it means they could also reach the point in N days.

Suppose the mummies CAN reach the point we're aiming for, but we can take some path that prevents that. The path the mummy must take to get to a point in some minimal time is bounded by the right angle centered on the point and facing in the cardinal direction that contains the mummy. If the mummy is on the diagonal, he must travel straight toward the point, and if the mummy CROSSES the diagonal, he will have taken at least 1 more step than is optimal. So to accomplish our task, we must force the mummy to cross the diagonal. For that to happen, we must both A) be in a quadrant separate from the mummy, and B) be at least as far away from the point as the mummy. If we are nearer to the point, then the mummy will take the diagonal step towards the point. But, if we are at least as far away from the point as the mummy, and he cannot reach the point in N days, then we neither can reach it in N days.

Anyway, we need to find if such a point exists.

Naive Solution: Walk all points and calculate distance to all mummies and our start. Runtime: 10^6^2 * 10^5 mummies....10^17! woot! not

Better solution: Rotate, use a sweepline So we know we only have 10^5 mummies, so should be able to better than checking every square. So first lets rotate the grid by 45 degrees so now our diamonds are squares. Run a sweep line across the grid which stops at the 2n locations where a mummies bounding box begins or ends (or ours). For each of those points, we either add a segment to our covered portion, or remove one. When we reach our own bounding box, and when we remove some segment while in our bounding box, we have to check whether the range inside our reachable range is fully covered by the ranges of the sweep. Naively, this takes time equal to the number of segments we're currently storing, but we can use the structure of the problem that all the squares are the same size to our advantage. There must be two segments in our set that completely cover the one that we just removed (or else we survive!!), one that covers the top, and one that covers the bottom (or it could be one that covers the whole thing). So we greedily select the lowest segment whose location is greater than or equal to this one, and the highest segment whose location is less than or equal to this one. If these two cover the entire span of the removed segment, the mummies can still reach all the positions. Otherwise, there is an uncovered spot, and we can survive.

You can use a tree set, but an interval tree is probably better suited to get your two queries in log(n) time. This makes the time to do the entire sweep O(nlogn).

That makes the entire runtime 10^5 * log^2(10^5). plenty fast.