Catch the Plane: Difference between revisions
Jump to navigation
Jump to search
Created page with "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 no..." |
(No difference)
|
Revision as of 21:19, 2 November 2018
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 Category:Interesting Points or