Asking help from smart math people (Again)

wasab · March 20, 2019

I am currently stuck with this problem. I know this can be done with dynamic programming(question says so) but I am having difficulty pinpointing the optimal substructure/subproblem. I was thinking I would consider stopping at whichever gas station within 100 miles of stony brook that fills up the most gas per second as the optimal subsolution and then go to whichever next fastest gasoline refilling gas station within 100 miles of that station as the next optimal subsolution and so on until all the way to San Francisco but the ci minutes is confusing me. what does that mean? Is it saying C7 is going to take the most time refilling and c1 takes the least?

@Dash Lambda

Can you please kindly explain what ci means and give me some hints if you have a moment to spare? I would really appreciate it.

Dash Lambda · March 20, 2019

It uses i as an index, so x_i is the distance to the i^th gas station from the starting point and c_i is how long it takes the i^th gas station to fill up. So a gas station that's 20 miles from SF that takes 5 minutes to fill up would have x_i = 20 and c_i = 5.

As for hints: Since you're trying to find the path that will spend the least time filling up, the distance between the gas stations only matters for determining which ones can connect. You can use that fact to directly apply an algorithm you're familiar with.

wasab · March 20, 2019

4 hours ago, Dash Lambda said:

It uses i as an index, so x_i is the distance to the i^th gas station from the starting point and c_i is how long it takes the i^th gas station to fill up. So a gas station that's 20 miles from SF that takes 5 minutes to fill up would have x_i = 20 and c_i = 5.

As for hints: Since you're trying to find the path that will spend the least time filling up, the distance between the gas stations only matters for determining which ones can connect. You can use that fact to directly apply an algorithm you're familiar with.

I see, so I can pretty much construct stations as the nodes, their refilling rate as the edge weight and connect all the stations within 100 miles of each other with an edge. I can then apply bellman Ford algorithm. I think that works. Thanks again. You are my math hero.