# algorithm - 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[0], a[1], … , a[N - 1].

The third line contains N space-separated integers: b[0], b[1], … , 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.

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[0]);
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;
}
``````

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.

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.

``````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);
}
``````