CareerCup

Lets assume all the gas stations are node on a circular linked list.

Foreach node assign a value = fuel (in km) - distance to next station (in km)
Now this becomes a circular array.

Our problem is transformed into the problem where we need to find a subarray with maximum sum. (Standard problem, and it can be solved in o(n) .. search maximum subarray in wikipedia, in case you are not aware of it).

Correct me if any of my above assuptions are incorrect.

1. Select an arbitrary pit as start
2. Iterate through every pit in some direction, for each pit calculate the amount of fuel. Some of these values can be negative.
3. Select the pit with the minimum (most negative) value (or any of such pits). This pit is the one we are looking for.

I have a correct solution to it. The code is very simple and clear. It outputs ALL valid start positions in O(2N) for one direction. You need to do it again (with input array reversed) to compute for the opposite direction. Total time is O(4N).
I will briefly explain the logic shortly.

#define  IDX(i) (((i) + (size<<1)) % size)
vector<int> findValidStarts(vector<int> distances, vector<int> gas_amounts)
 //distances[0] indicates the gas consumption between station idx [0, 1], distances[size - 1] ~ [size-1, 0]
{
	int extra_gas = 0;
	int size = distances.size();
	int beg = 0, end = 0;
	do
	{
		if (extra_gas >= 0)
		{
			extra_gas += gas_amounts[IDX(end)] - distances[IDX(end)];
			end ++;
		}else{
			beg --;
			extra_gas += gas_amounts[IDX(beg)] - distances[IDX(beg)];
		}
	}while (IDX(beg) != IDX(end));
	vector<int> answers;
	do
	{
		if (extra_gas >= 0)
		{
			answers.push_back(IDX(beg));
			beg --;
			extra_gas = gas_amounts[IDX(beg)] - distances[IDX(beg)];
		}else{
			beg --;
			extra_gas += gas_amounts[IDX(beg)] - distances[IDX(beg)];
		}
	}while(IDX(beg) != IDX(end));
	return answers;//answers contains ALL the valid start positions.
}

I can't understand why you have to be that hard on this problem. Let's look at the constraints again:
- The location and the amount of fuel pits are KNOWN
- All the fuel in the fuel pits together are JUST ENOUGH to travel a full perimeter or the track.

Thus it's safe to assume that:
- The car start with an empty fuel tank
- No constraints on the capacity the fuel tank (i.e it can store all the fuel in the fuel pit together)

Thus the strategy is:

- Start at the largest pit, take all the fuel in the pit of course
- Now we have to chose between 2 directions, let's say clockwise or counterclockwise
- The direction should satisfy that from the first node to the last node on the traveling path, the arc should be smaller than the other arc of the other direction.

I find this is an elegant solution. Please give me an example of how we can fail the challenge if we follow this strategy.

The solution by @Harty, is a brute force approach..
Start from each node, and traverse hence you would end up in O(n2) algorithm.

Also we need to consider that one must traverse in both clockwise and anticlockwise directions.
which is n2+n2 Algo.. which still runs in O(n2) algorithm.

1. consider any arbitrary start point A.
2. start doing the calculation s= Fuel at pump A +route ahead A to B
3. if at any time s <0 ;
It means the point that we considered was not the start point
4. then shift the start point in the direction of the route and see if the s(s = s - route(A to B) - fuel(A) ) is now greater than 0
5. goto step 2

If it exits succesfully we would be knowing the start point.
I am not sure whther the solution would be O(n) as i forgot how to calculate complexity, but thi s must be better than O(n^2)

I think this can be done in O(n). There are two or three phases:

Phase 1:
1) Start at an arbitrary point. Record the location as your starting point and the amount of fuel now in the tank, after loading up.
2) travel clockwise to the next site. Subtract the amount of fuel consumed from the amount in the tank. if this is the initial site chosen in step 1), you are done with this phase. otherwise, goto step 3)
3) if the remaining fuel is positive, add the fuel from the newly reached depot to the amount of fuel available, then goto step 2). Otherwise, replace the starting point with the new location, and reset the amount of fuel available to the amount at the new location., then goto step 2)

Phase 2:
1) When you get back to the first point chosen in step 1) you should have a proper "starting position" recorded.
2) Start at that position and travel clockwise to check if the fuel level ever goes negative. If it does go negative, goto phase 3. Otherwise, you are done.

Phase 3:
1) Repeat Phase 1, but travel in a counter-clockwise direction.


Analysis:
I believe this works because, assuming there _is_ a solution, because you are always better starting off at a higher fuel level.

a) Take 2 points -- A and B -- on the track (with an arbitrary number of depots between each) b) You have consumed a certain amount of fuel -- X -- travelling from A to B
c) You will consume a certain amount of fuel -- Y -- travelling from B to A.
d) If you have not gone negative, travelling from A to B, then you are, by definition, in a better position using the remaining fuel plus the amount at B to finish the journey, than you would be if you just used the amount at B.

I am not yet sure if phase 3 is needed. ie. is it possible to set up the track so that there is only a solution in one direction.

Is it fine to assume that car has no fuel in the beginning and then it becomes mandatory to start at a fuel pit, get the fuel filled and go ahead?

We are given locations of fuel pits and their capacities.
Let Capacity of pit 'i' = Ci.
Let distance for which Ci will last (or the distance that Ci amount of fuel will help in travelling) = di
Distance between consecutive points i and j = Dij
Without loss of generality, lets start at a point Ci.
Then in order to move from i to j,
di >= Dij (fuel provided at starting point Ci should help the car go atleast Dij distance).

At point j,
di - Dij = distance that left out fuel in car can run for
Therefore,
(di - Dij) + dj >= Djk (where j and k are consecutive points)

At each point, we need to ensure that above inequality holds true.

Greedy approach: Start at a point where (di - Dij) is maximum. May not lead to a correct solution.

O(n2) solution is obvious (as stated by many above).
Need to think of a better solution.

is n't it a max sub array problem in circular region where we hav to maximize fuel left

This is o(N) problem. You start at the first point and you do the next steps:
1) add the current full and substract the distante to the next point
2) if it;s negative, try start at that point ( Go to step 1)
3) you have to keep 2 variabiles, Start and End, and if Start == End , you stop, and tha's the answer. Start is the last moment you execut Step 2 and End is the curent pozition
You go in circular. Worst case O(2N) = O(N)

O(N) solution:
Map this problem to the following one
An array of size (= length of circular track) exists with all values 0 except the indices where fuel pits are there. The indices where fuel pits exist have values = amount of fuel that can be refilled from there.
Circular track => You can move across the array and after the final index return back to 0th index.

1. find the first fuel pit in the array. Assign this value to a variable say amountOfFuel.
2. As you move across the array (in a circular fashion), keep decrementing the value of amountOfFuel and if you encounter another fuel pit(another index with non-zero value), add the value to the variable. If you reach back at the starting point after a circular trip, voila!!
3. if you run out of fuel, then the fuel pits, that you have encountered till now, won't be the starting points obviously. So you again move forward until you find the next fuel pit and restart from point 1.

In case you have crossed one circle and still don't find a starting point.
Do the above again in the opposite direction.
Hope that helps

1. Add total amount of fuel T(f) and add up all the miles T(m). If T(f) < T(m), quit.
2. Rest of the steps look good to me to complete the solution in O(n).

Let's consider one direction first, for each station, say, it has x amount of fuel and the distance from this station to the next station is y (let x and y have the same unit...), we can use the number x-y to represent this station in this direction.

Thus, we have a circle of m numbers (a) and need to find a start point, so that sum_{k=i}^{j} a_k >=0 for any j.

For each station, use another array to represent its "capability" as the start point. 0 means "not sure yet", -1 means "no", and 1 means "yes". denote this array as b

- initially, b[i] = 0
- if a[i] < 0: b[i] = -1
- if a[i] = 0: b[i] = -1 (theoretically, it can be the starting point. but there must be another solution)
- if a[i] > 0,
- if a[i-1] >0 (note, a[-1]=a[m-1]), b[i] = -1

for the rest stations with b[i] = 0, i can only think of brute force examinations.....

the worst case running time for this is O(n). However, on average, it should be a lot faster.

solvedata(int[] arr){
for(int k=0;k<arr.length;k++)
int point=solve(arr,k,arr[k],k)
if(point!=-1){
System.out.println(point);
}
}

}

solve(int[] carr, int i,int j,int start){
if(i<0)
i=carr.length-1
if(i>carr.length-1)
i=i%carr.length;

if(j<0)
return -1
if(j>0 && j%carr.length==start)
return start

int left= solve(arr,i-1,j-dist(i,i-1),k)
int right= solve(arr,i+1,j-dist(i,i+1),k)
if(left!=-1 || right!=-1)
return Math.max(left,right)

}
return -1
}

Why are all these people giving O(n^2) solution and claim it's O(n)?
If you have to check certain starting-points(or gas station) by going through the n-sized-array(or the track),
and you have to try that for each of n-starting-points until you find it, that's O(n^2). NOT O(n).

Assume that F[i] is the fuel available at point i and D[i] is the distance of point i from the begining.
I assume that I copy each arrays to the end of it to make a circle. If there are N points the size of F and D is going to be of size 2N.
I define L[i] to be the maximum distance that could be traveled to point i with starting fuel that existed at the starting point and R[i] to be the corresponding remaining fuel.
Here is the psuedu code:

L[0]=0;
S[0]=0;
for (int i=0; i<2N-1; i++)
{
	if(S[i]+F[i] < D[i+1]-D[i])//if we cant make it to the next point
	{
		L[i+1]=0;
		S[i+1]=0;
	}
	else
	{
		L[i+1]=L[i]+D[i];
		S[i+1]=S[i]+F[i]-D[i+1];
	}
	if (L[i+1]>=MAXDIST)
		return (i%N);
}
return -1;//not found

The approach should be suppose there are x number of Pits......
Pick the largest available pit should be first. the direction should be chosen where
if you divide the whole circle into half. the sum of available pits of semi circle to be which is big comapre to other should be chosen.
eg: if there are 1635274 pits . Choose 6 as first and direction should be not 7+2+5+3(=15) , but i should be 7+4+1+6(=18)

Assumption:
1) the data is provided in the form of a circular array( somewhat like a queue)
2) structure of each element of array contains
a) the fuel pool present.
b) the distance to the next pool.
Explanation:
1)starting from first pool move ahead if possible( i++ )
2) if you cannot move further, move j backwards to check if now i can move further
3) repeat until I and j meet.

int findStart(stop *a,int n){
    if (n==0) return 1000;
    int i=0;
    int j= n-1;
    int fuel = a[0].pool;
    int count =1;
    while(i!=j){
        count++;
        if(a[i].next<=fuel){
            fuel = fuel-a[i].next;
            i++;
            fuel = fuel+a[i].pool;
        }
        else{
        fuel = fuel + a[j].pool -a[j].next;
        j--;
        }
    }
    cout<<count<<endl;
    return (j+1)%n;
}

Dynamic programming is the way to go. Start on any pit keep going till fuel lasts i.e. see what is distance b/w this pit and next pit and how much fuel left after you reach there. In case you stop somewhere assume starting from next but rather taking the car back subtract distance covered by first pit of previous entry and continue from remaining fuel. Continue in one direction and if you reach the starting point then print that pit else start in other direction.

funny all these ppl trying to solve this without the 'given' numbers. Once you had these it would just be simple addition and subtraction. A visual representation would give the quickest answer in my book.

The problem seems to be pretty simple.. But I doubt.

From the problem definition it can be noticed that the track is circular.. and user is has only 2 options, moving in clockwise and counterclockwise directions.

Calculate total perimeter of the track, divide it into segments , and joining two segments is a fuel pit.
Check travelling in a particular direction consuming fuel at pits is enough to reach next pit or ahead of it.
And this should work.

Why not just find the pit with the most fuel and try one direction, and if that doesn't work, try the other direction. Given the constraints of the problem, and assuming the car can hold unlimited fuel (because it's not specified in the problem), I believe this has to work. It is also by far the simplest algorithm on this page.

can you elaborate your solution ?

Start at the pit station that will have the most fuel left until reaching the next station?