In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?

Question

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 the solution gives would solve the problem. I cannot see how this is the case. What am I missing?

Answer 1

Suppose that starting at city $i$, traversing the cities in ascending order, we have $A_j$ amount of fuel remaining when we arrive at city $j$. If instead we start at city $i+1$ then the amounts $A_j$ will change by $[\textrm{gas required to go from $i$ to $i+1$}]-[\textrm{gas at city $i$}]$ for all $j$.

So the problem can be solved by computing the values $A_j$ starting at city $0$, finding the minimum and then looping over all the cities, updating the minimum value until it becomes non-zero (at which point you've found an ample city).

Answer 2

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$$

This must mean $$\sum_{i=j + 1}^{n} 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.

Answer 3

I also had problems solving this task and I came up with an alternative O(n) solution, which I find more simple to understand (at least for me).

The idea is to start at some city and try to advance the head to the next city if we have enough fuel. If we can't advance the head, we move the tail. At each step we have to adjust the current fuel we have. This way we move like a caterpillar until we reach our own tail:

public static City findGasup(City city) {
    int currentGallons = 0;

    City head = city;
    City tail = city;
    while (true) {
        if (currentGallons + head.gallons >= head.miles / 20) {
            currentGallons += head.gallons;
            currentGallons -= head.miles / 20;

            if (head.next == tail) {
                return tail;
            }

            head = head.next;
        } else {
            currentGallons -= tail.gallons;
            currentGallons += tail.miles / 20;
            if (tail == head) {
                head = head.next;
            }

            tail = tail.next;
        }
    }
}

It requires at most 2 passes around the cities and we could also add a condition to terminate after those 2 passes in case there is no ample city.

Answer 4

The problem is not easy, it took me a lot of time to understand and prove the solution.
Model the problem to a sequence of integers: element at i = the remaining of gas after city i = G[i] – D[i]. In other words, the sum of any subsequence i to j is the remaining of gas after traveling from city i to city j.
We can find A, the minimum-sum subsequence (A = total of elements from beginning to the city j at which the sum is minimum), by traversing all the cities once; the starting city does not matter. Then the city j+1 is the ample city.
Proof:
From the problem description: total of sequence = A + remaining = 0
When beginning at the city j+1 right after the minimum city: remaining + S >= remaining + A = 0
For any city inside remaining: Q >= 0 because if Q < 0 then A + Q < A while A is the minimum
Therefore, sum of any of subsequence when beginning at j+1 always >= 0, i.e., never run out of gas.