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 edit summary |
||
| Line 9: | Line 9: | ||
dp[node][probability] = minimum time of getting to a node with at least a given probability | 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 [[ | The issue with the first one is time is 10^18. Even with [[Category:Interesting Points|range compression]] or | ||
Revision as of 21:20, 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 or