CareerCup

1) take a doubly circular linked list, take two pointers(forp and backp) and start from any point, calculate X(Ci-Gi).
2) when moving forward to next station using forp calculate sum = sum + X. if sum is -ve move back using backp and calculate sum = sum + (Ci-1 - Gi-1). continue to move back till sum becomes +ve and then start again moving forward using step 2 itself.
3) when forp equals backp and sum is +ve u have got the starting station else if sum is -ve there is no starting station.
This is a linear time algorithm.

0. Able to complete one round => sum(Ci-Gi) >= 0
1. Start from any point, say, point 1,
2. Accumulate (Ci-Gi) from 1 to point k, Ak = sum(Ci-Gi) from 1 to k, for k = 1,..,n
3. The start point should be k = argmin(Ak), i.e., where Ak reach minimum.

In algorithm, remember the minimum and its index during accumulation, it's linear time.

Ne 1 plz elabrote the above Algo..............given by LKS

Bum. It is simple
1. Select any start point.
2. Move on unless you have enough gas
3. Select the last station you have succefully passed as a new start point. (There is no reason move back and force)
4. Goto 2

0. Able to complete one round => sum(Ci-Gi) >= 0
1. Start from any point, say, point 1,
2. Accumulate (Ci-Gi) from 1 to point k, Ak = sum(Ci-Gi) from 1 to k, for k = 1,..,n
3. The start point should be k = argmin(Ak), i.e., where Ak reach minimum.

In algorithm, remember the minimum and its index during accumulation, it's linear time.

My idea is based on greedy algo: find a sequence of Ck, Ck+1, .... Ck+m that yields the largest sum. Ck will be the starting point.

AS you may already know, finding such sequence is O(n)

getting confused, isnt it travelling sales man problem which is NP-complete...:(

How are they expecting O(n) algo?

nopes..its not TSP.