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?