Of the Children: Difference between revisions

From programming_contest
Jump to navigation Jump to search
imported>Kmk21
Created page with "BFS state explotion. State would have to be list of cities visited, city we're at, and amount of money we have. Then binary search across starting $ to find the minimum needed..."
 
imported>Kmk21
No edit summary
 
Line 1: Line 1:
BFS state explotion. State would have to be list of cities visited, city we're at, and amount of money we have. Then binary search across starting $ to find the minimum needed.
BFS state explosion. state is city we're at and amount of money we have. Optimize for lowest "debt" incurred. Solution is the minimum debt that gets you to the final city with any amount of money. That debt is the amount you have to start with to ensure you have enough.


Runtime log(10,000) * 24 * 2^24 * 10000 = ~10^13
Very similar to [[Full Tank?]]


eugh.
[[Category:ICPC Problems]]
 
[[Category:Midatl2015]]
BUT...it's a bit smaller than that....there are only 23 cities max, and the start and end are fixed...which brings the DP bit down to 21
[[Category:Algorithm Medium]]
 
[[Category:Implementation Easy]]
21*2^21*10000*log(10000) = ~10^12
[[Category:BFS]]
 
[[Category:State Explosion]]
we're getting closer....but not good enough
 
what if we BFS our paths, and keep track of the most in debt we go along the journey, and that's the amount we'd need to start with
 
21*2^21*10000 = 440 billion....smaller
 
Hmmm....what to do....
 
AH! Process the states in number of cities visited total order!
 
#start with 0 cities visited and loop to all cities visited
#loop over all combinations of cities previously visited
#*each one stores the minimum debt needed to get to that

Latest revision as of 04:01, 27 August 2016

BFS state explosion. state is city we're at and amount of money we have. Optimize for lowest "debt" incurred. Solution is the minimum debt that gets you to the final city with any amount of money. That debt is the amount you have to start with to ensure you have enough.

Very similar to Full Tank?

Retrieved from "https://wiki.speedyguy17.info/index.php?title=Of_the_Children&oldid=787"