patternMinor
In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?
Viewed 0 times
shiftgasproblemthesamestartingamountregardlesshowcity
Problem
I'm working through Elements of Programming Interviews as practice for finding a job. I've spent a ridiculous amount of time on Problem 18.7.
In the gas-up problem, $n$ cities are arranged on a circular road. You
need to visit all of the $n$ cities and come back to the starting
city. A certain amount of gas is available at each city. The total
amount of gas is equal to the amount of gas required to go around the
road once. Your gas tank has unlimited capacity. Call a city $c$
ample if you can begin at $c$ with an empty tank, refill at it, then travel through each of the remaining cities, refilling at each, and
return to $c$, without running out of gas at any point. See Figure
18.3 for an example. [You can see Figure 18.3 on the Google Books result if you search for "Elements of Programming Interviews Problem
18.7.]
Given an instance of the gas-up problem, how would you efficiently [i.e. in $\mathcal{O}(n)$ time or better]
compute an ample city, if one exists?
I couldn't figure it out. I read the hint, and I still couldn't figure it out. I gave up, and read the answer in the back of the book. I still couldn't figure it out. I searched Google and this site for a more complete solution, but didn't find one.
This is the part that's getting me:
On closer inspection, it becomes apparent that the graph of the amount
of gas as we perform the traversal is the same up to a cyclic shift
regardless of the starting city.
I must not be inspecting closely enough, because this is not apparent to me at all. I tried calculating the remaining gas at each city during a traversal of an example circuit, starting at different cities (and permitting the number to be negative when necessary, as the solution suggests). There does not seem to be any relation between the series of numbers I get when starting at different cities. I understand, if we accept that the amount of gas remaining at each city is the same up to a cyclic shift, how the algorithm t
In the gas-up problem, $n$ cities are arranged on a circular road. You
need to visit all of the $n$ cities and come back to the starting
city. A certain amount of gas is available at each city. The total
amount of gas is equal to the amount of gas required to go around the
road once. Your gas tank has unlimited capacity. Call a city $c$
ample if you can begin at $c$ with an empty tank, refill at it, then travel through each of the remaining cities, refilling at each, and
return to $c$, without running out of gas at any point. See Figure
18.3 for an example. [You can see Figure 18.3 on the Google Books result if you search for "Elements of Programming Interviews Problem
18.7.]
Given an instance of the gas-up problem, how would you efficiently [i.e. in $\mathcal{O}(n)$ time or better]
compute an ample city, if one exists?
I couldn't figure it out. I read the hint, and I still couldn't figure it out. I gave up, and read the answer in the back of the book. I still couldn't figure it out. I searched Google and this site for a more complete solution, but didn't find one.
This is the part that's getting me:
On closer inspection, it becomes apparent that the graph of the amount
of gas as we perform the traversal is the same up to a cyclic shift
regardless of the starting city.
I must not be inspecting closely enough, because this is not apparent to me at all. I tried calculating the remaining gas at each city during a traversal of an example circuit, starting at different cities (and permitting the number to be negative when necessary, as the solution suggests). There does not seem to be any relation between the series of numbers I get when starting at different cities. I understand, if we accept that the amount of gas remaining at each city is the same up to a cyclic shift, how the algorithm t
Solution
This is over a year later, but I also found this question really frustrating, but after reading other explanations, I've finally figured it out. So, I want to share with everyone my findings!
In this problem we're guaranteed that the amount of gas is enough to go around the road once. We then have this equality
$Amount_{gas}$ = $Amount_{distance}$
$$\sum_{i=1}^{n} x_{i} = 0$$
where $x_{i}$ is the Amount of gas at station i - the cost:
$$G[i] - D[i]$$
If we reach a point $j$ such that:
$$\sum_{i=1}^{j} x_{i} 0$$
Why!?!??! Because the problem promises us enough gas to cover the distance!
$$\sum_{i=1}^{j} x_{i} + \sum_{i=j + 1}^{n} x_{i} = 0$$
If we start at point $j + 1$, which is right after we don't have enough gas,
the equation becomes
$$\sum_{i=j + 1}^{n} x_{i} + \sum_{i=1}^{j} x_{i} = 0$$
Starting at $j + 1$ means we have $\sum_{i=j + 1}^{n} x_{i}$ gas before j, so we won't have a negative number.
This agrees with the solution in EPI because we are in fact doing a vertical shift on our piecewise function $\sum_{i=1}^{n} G_{i} - D_{i} $
The pictoral graph in EPI helps us see that it's not good enough to merely spit out the first j that gives us a negative value. If instead, we find the minimum, we will have more than enough gas before we reach j (first point that gives us negative amount of gas left) and cover subsequent negative gas stations until the aforementioned minimum.
In this problem we're guaranteed that the amount of gas is enough to go around the road once. We then have this equality
$Amount_{gas}$ = $Amount_{distance}$
$$\sum_{i=1}^{n} x_{i} = 0$$
where $x_{i}$ is the Amount of gas at station i - the cost:
$$G[i] - D[i]$$
If we reach a point $j$ such that:
$$\sum_{i=1}^{j} x_{i} 0$$
Why!?!??! Because the problem promises us enough gas to cover the distance!
$$\sum_{i=1}^{j} x_{i} + \sum_{i=j + 1}^{n} x_{i} = 0$$
If we start at point $j + 1$, which is right after we don't have enough gas,
the equation becomes
$$\sum_{i=j + 1}^{n} x_{i} + \sum_{i=1}^{j} x_{i} = 0$$
Starting at $j + 1$ means we have $\sum_{i=j + 1}^{n} x_{i}$ gas before j, so we won't have a negative number.
This agrees with the solution in EPI because we are in fact doing a vertical shift on our piecewise function $\sum_{i=1}^{n} G_{i} - D_{i} $
The pictoral graph in EPI helps us see that it's not good enough to merely spit out the first j that gives us a negative value. If instead, we find the minimum, we will have more than enough gas before we reach j (first point that gives us negative amount of gas left) and cover subsequent negative gas stations until the aforementioned minimum.
Context
StackExchange Computer Science Q#44556, answer score: 6
Revisions (0)
No revisions yet.