# Dynamic Programming: Find possible ways to reach destination

I'm trying to solve this problem, O(N^2) solution is simple, O(N) is possible, but I cannot think of how. Here's the question:

There are N cities and N directed roads in Steven's world. The cities are numbered from 0 to N - 1. Steven can travel from city i to city (i + 1) % N, ( 0-> 1 -> 2 -> .... -> N - 1 -> 0).

Steven wants to travel around the world by car. The capacity of his car's fuel tank is C gallons. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N.

How many cities can Steven start his car from so that he can travel around the world and reach the same city he started?

Note

The fuel tank is initially empty.

Input Format The first line contains two integers (separated by a space): city number N and capacity C. The second line contains N space-separated integers: a, a, … , a[N - 1]. The third line contains N space-separated integers: b, b, … , b[N - 1].

Output Format The number of cities which can be chosen as the start city.

Sample Input

3 3
3 1 2
2 2 2
Sample Output

2
Explanation

Steven starts from city 0, fills his car with 3 gallons of fuel, and use 2 gallons of fuel to travel to city 1. His fuel tank now has 1 gallon of fuel. On refueling 1 gallon of fuel at city 1, he then travels to city 2 by using 2 gallons of fuel. His fuel tank is now empty. On refueling 2 gallon of fuel at city 2, he then travels back to city 0 by using 2 gallons of fuel.

Here is the second possible solution. Steven starts from city 2, fill his car with 2 gallons, and travels to city 0. On refueling 3 gallons of fuel from city 0, he then travels to city 1, and exhausts 2 gallons of fuel. His fuel tank contains 1 gallon of fuel now. He can then refuel 1 gallon of fuel at City 1, and increase his car's fuel to 2 gallons and travel to city 2.

However, Steven cannot start from city 1, because he is given only 1 gallon of fuel, but travelling to city 2 requires 2 gallons.

Now I know this algorithm could be solved in O(N) time complexity, which I am unable to, guess it can be solved using dynamic programming, please help me get a clue how it could be broken into sub problems.

• This sounds similar to this question. Is it? – Nico Schertler Jun 25 '14 at 13:32
• The problem is similar, but it doesn't give an algorithm to find all possible starting points. – gnasher729 Jun 25 '14 at 15:31

I've made and an algorithm that should solve the problem, it outputs 2 for your case, but it must be tested on other testcases. I'm not sure it's correct. My main idea was that if you can make an iteration starting from one point you can make how many you wish, and the reverse is also true. If you can't make more than one, you cannot make even one.

``````#include <algorithm>
#include <iostream>

using namespace std;

#define PROB_SIZE 3
int n = PROB_SIZE, c = 3;
int a[PROB_SIZE] = {3, 1, 2}; // available
int b[PROB_SIZE] = {2, 2, 2}; // used
int d[PROB_SIZE];
int dmin[PROB_SIZE];

int main()
{
//The fuel used in the trip to next node (amount put in minus the amount consumed in one trip).
for (int i = 0; i < n; i++) {
d[i] = a[i] - b[i];
}
//The fuel that i need to start a trip in this point and reach point 0.
dmin[n - 1] = d[n - 1];
for (int i = n - 2; i >= 0; i--) {
dmin[i] = min(d[i], d[i] + dmin[i + 1]);
}
//The second loop to be sure i cover a whole loop from any point.
dmin[n - 1] = min(d[n - 1], d[n - 1] + dmin);
for (int i = n - 2; i >= 0; i--) {
dmin[i] = min(d[i], d[i] + dmin[i + 1]);
}
//If for any point i need to have more fuel than i can carry then the trip is impossible for all points.
for (int i = 0; i < n; i++) {
if ((-dmin[i] + a[i]) > c) {
cout << 0 << endl;
return 0;
}
}
int cnt = 0;
//Any point that i need to have 0 fuel to reach point 0 making at least one round trip is a good starting point.
for (int i = 0; i < n; i++) {
if (dmin[i] >= 0) {
cnt++;
}
}
cout << cnt << endl;
}
``````
• I'm not sure if I understand you correctly. Are you saying that whenever you can make a whole round from one start point, you can make the whole round from any other? That's definitely not true. Anyway, could you explain your algorithm a bit more? At least add some comments? – Nico Schertler Jun 26 '14 at 20:49
• No, that's clearly not true since in the example we see that we have one point where we cannot start the loop, i am saying that if you can start from point x and make a whole loop back to x, then you can continue from point x and make another loop. And the reverse, if you start from point x, make a loop and then when trying to make a second loop, you run out of fuel, that means that you have made a mistake when making the first loop. – George Nechifor Jun 27 '14 at 7:14
• I have confirmed that this code successfully passes all test cases on the page that this question has been copied from. However, the comments in the code are highly confusing, starting from the very first thing defined: d[i]=a[i]-b[i]. How is this the fuel "used"? It should more accurately be described as the fuel "gained"? And also if a[i]>c then d[i] is not a meaningful quantity at all. It works, but I'm not sure why it works. – xdavidliu Sep 23 '18 at 15:38

While you try to find out whether you can get from city i back to city i, you need to gather information about previous cities. I'd create a stack containing information that you could start at city x, and arrive at city y with z fuel in the tank.

When you check out city j, you find that you can put X fuel in the tank at j, and driving to j+1 takes Y fuel. If X >= Y, you put that information on the stack. Otherwise, pop the top of the stack. The information there will tell you that you could start at some x and arrive at j with z fuel in the tank. Starting at x, you would leave j with min (z + X, C) in the tank. If that is enough, push the information back on the stack. If not, pop the next item from the stack. If the stack is empty, there is no way to reach j+1.

Now you need to figure out how to end the search, and prove that there are only O (N) operations.

• please can you describe the logic, thnx – user3098199 Jun 25 '14 at 19:17

Simpler method: You have your list of cities, and one by one you remove the ones where you cannot start.

You look for the first city i that hasn't enough fuel to get to city i+1. If there is no such city, you can start anywhere. Since you can't get from i to i+1, you remove it from the list of cities, but you need to combine it with the previous one. If the previous city has x fuel and needs y, x >= y, and city i has X fuel and needs Y you do the following:

1. Replace X with min (X, C - (x - y)) (because the extra fuel can't be used).
2. Subtract min (y, X) from y and X (because that's you much you can refill)
3. Replace x with min (C, x + X) and y with y + Y.

At that point, you check the previous city again. You finish when you can go from each city to the next. You may end up with one city that can't reach the next one; in that case you fail.

• Please can you also describe the logic? – user3098199 Jun 25 '14 at 19:17
• But what happens if you can't get from i to i+1 when starting with an empty tank, and you can't get from i-1 to i when starting with an empty tank, BUT when starting with an empty tank at an earlier city (e.g. i-2) you can get to i+1? It seems that your algorithm won't handle this case, because after it fails to adjust the link from i to i+1 the first time (i.e. when the test x >= y fails for the link from i-1 to i), it won't make another attempt later on. – j_random_hacker Jun 26 '14 at 4:42
``````static int n = 3;
static int c = 3;
static int a[] = {3, 1, 2};
static int b[] = {2, 2, 2};
static int currentCity;

public static void main(String[] args) {

List<String> citi = new ArrayList<String>();

//try one by one
for(int i = 0; i < n; i ++){
currentCity = i;
if(!startFrom(i, 0))
continue;

}

for (String s: citi)
System.out.println(s);
}

public static boolean startFrom(int i, int left){
int tankVal = (a[i] + left) > c ? c : (a[i] + left);

if(b[i] > tankVal)
return false;

left = tankVal - b[i];

int next = (i + 1) % n;
if(next == currentCity)
return true;
return startFrom(next, left);
}
``````

First, I would like to point out that this question is word-for-word lifted from an exercise on HackerRank.

Here's a sketch of an algorithm that has been confirmed to pass all test cases on that site for this particular problem in O(N) time.

For all partial "trips" starting from 0 and ending at i for 0 < i < N, compute the following information:

1) What is the minimal gas we need to begin the trip at city 0 in order to successfully go from 0 to i?

2) Starting with this minimal amount (assuming the partial trip is even possible) how much gas will we have as we enter city i?

3) During such a trip, what is the largest amount of gas you will ever carry in your tank?

The reason we need #3 is because of the limited gas tank capacity sometimes prevents us from taking the "gas profile" of some trip and just "shifting everything up". Knowing how close we are to the ceiling for some given trip tells us exactly how much we can "shift up" before we hit the ceiling. (This sounds vague, but one should think about this point closely).

Once you have these three for every 0 < i < N, you also must compute these three for all partial trips starting at some i with 0 < i < N and wrapping around back to zero.

All six of these figures of merit can be computed in O(1) time per city using some slightly clever dynamic programming, and once you have them all for all the cities, it takes O(1) time to check if a city can wrap around completely.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9450566,"math_prob":0.94191927,"size":2201,"snap":"2020-10-2020-16","text_gpt3_token_len":597,"char_repetition_ratio":0.16659081,"word_repetition_ratio":0.045045044,"special_character_ratio":0.2812358,"punctuation_ratio":0.11729623,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9707836,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-04T12:34:20Z\",\"WARC-Record-ID\":\"<urn:uuid:092ecf0a-93a9-48eb-bef7-0259baa0f325>\",\"Content-Length\":\"183530\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a9de1a22-50d3-4718-90e6-01c2a626dff9>\",\"WARC-Concurrent-To\":\"<urn:uuid:813c6994-33d1-496d-87d6-0893fe0a9403>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://stackoverflow.com/questions/24408371/dynamic-programming-find-possible-ways-to-reach-destination\",\"WARC-Payload-Digest\":\"sha1:LEF6GLW64PBVDZPU7TMHEEELH2ULZZ7E\",\"WARC-Block-Digest\":\"sha1:INAMQNHAT7VF2JDQQY75VVZ6YNPRJIK3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585370521876.48_warc_CC-MAIN-20200404103932-20200404133932-00105.warc.gz\"}"}