Catch the Plane

This problem asks gives us a bus schedule, where each bus has a probability of ACTUALLY running, and then asks us to figure out the max probability we can arrive at a given node before a given time.

Standard problems might ask us to optimize for the probability of ever reaching a given location, or the minimum time it takes to get there, but attempting to do both at the same time makes this slightly more difficult. A way to fix this might be to use a dp:

dp[node][time] = maximum probability of getting to node at time

or swapping the dimensions

dp[node][probability] = minimum time of getting to a node with at least a given probability

The issue with the first one is time is 10^18. Even with , where wee only consider times that a bus leaves or arrives at, we are still at 10^6^2 = 10^12. The second method is not viable since probability doesn't give a discrete measure, or perhaps more validly, there are too many discrete probabilities to memoize.

The key thing to note here is that we're not REALLY optimizing in two dimensions. We are optimizing in one dimension, probability, and the other dimension is a constraint, namely that we must be at node X before time t. It doesn't matter how much earlier than time t we get there. So what challenges do we face if we just dijkstra over maximum probability? The issue is the maximum probability way of reaching a node may not give us a path that allows us to reach the end node in time. So ultimately, we want to find the highest probability path, but have a way of doing it ONLY if we know we have a way of reaching the goal along that path. Unfortunately we don't know which paths allow us to reach the airport in time!

There is a second issue. Suppose we are just optimizing over probability: We then run into an issue where arriving late at a given node with a high probability, but the only way to get to the end before time T is a very low probability path. It would, thus, have been better to take an earlier bus with somewhat lower probability to get to this node, but which allows us to take a higher probability out!. This is an intrinsic problem when we have different busses we can take out of a node depending on arrival time. Of course, trying to consider arrival time blows up the complexity again, anyway.

So what to do?

Idea: What if we run the problem backwards (airport->start point), and only consider buses that are arrive at the airport in time? This eliminates time as a factor we need to consider! Since we will only be evaluating paths which we KNOW get us to the aiport in time. This involves initializing every node to 0, and processing nodes in order of highest probability of reaching.

...