The problem was:
A circular road, with $n$ petrol stations, which just enough petrol to complete one full circle along the road. You have a car with an empty tank (but infinite capacity), and can start at any petrol station an drive along the road, filling petrol along the way.
You need to find all the stations that will allow you to complete a full circle without running out of petrol.
The algorithm needs to run in $O(n)$ time.
Solution
Note that we allow the car to travel either clockwise or anti-clockwise. We will provide a solution for the clockwise case, the other is similar. Also note that if the car chooses to go in one direction first, it has to continue along that direction.
We were given the input as $p_1, p_2, \dots, p_n$ and $d_1, d_2, \dots, d_n$
where $p_i$ was the amount of petrol in station $i$, and $d_i$ was distance between station $i$ and $i+1$ (written in clockwise consecutive order).
Let $e_i = p_i - d_i$, the amount of petrol left in the car, if an empty car starts at station $i$ and goes to station $i+1$. Note that $e_i$ could be negative.
Suppose we start at station $k$. Then the amounts of petrol that will be in the car at each station will be
$$e_{k}, e_k + e_{k+1}, \dots, e_k + \dots + e_n, e_k + \dots + e_n + e_1, \dots, e_k + \dots + e_n + e_1 + \dots + e_{k-1}$$
We need each of those to be non-negative.
Let $S_k = e_1 + e_2 + \dots + e_k$. We are given that $S_n = 0$ and the above intermediate amounts are
$$S_{k+1} - S_k, S_{k+2} - S_k, \dots, S_n - S_k, S_n - S_k + S_1, \dots S_n - S_k + S_{k-1}$$
Thus we need that for every $j$, since $S_n = 0$ that
$$ S_j \ge S_k$$
Thus we need to pick all the $k$ such that $S_k$ is the smallest.
Repeat in the other direction and we are done.
The $S_n \gt 0$ case is more interesting, and can still be solved in $O(n)$ time.
Now the conditions become
1) $ S_j \ge S_k$, for $j \gt k$
and
2) $ S_j + S_n \ge S_k$, for $j \le k$.
The candidates satisfying condition 1) can be computed by traversing the $S$ array from right to left, keeping track of the minimum seen so far.
The candidates satisfying condition 2) can be computed by traversing the array from left to right and keeping track of the smallest possible value of $Sj + S_n$.
A circular road, with $n$ petrol stations, which just enough petrol to complete one full circle along the road. You have a car with an empty tank (but infinite capacity), and can start at any petrol station an drive along the road, filling petrol along the way.
You need to find all the stations that will allow you to complete a full circle without running out of petrol.
The algorithm needs to run in $O(n)$ time.
Solution
Note that we allow the car to travel either clockwise or anti-clockwise. We will provide a solution for the clockwise case, the other is similar. Also note that if the car chooses to go in one direction first, it has to continue along that direction.
We were given the input as $p_1, p_2, \dots, p_n$ and $d_1, d_2, \dots, d_n$
where $p_i$ was the amount of petrol in station $i$, and $d_i$ was distance between station $i$ and $i+1$ (written in clockwise consecutive order).
Let $e_i = p_i - d_i$, the amount of petrol left in the car, if an empty car starts at station $i$ and goes to station $i+1$. Note that $e_i$ could be negative.
Suppose we start at station $k$. Then the amounts of petrol that will be in the car at each station will be
$$e_{k}, e_k + e_{k+1}, \dots, e_k + \dots + e_n, e_k + \dots + e_n + e_1, \dots, e_k + \dots + e_n + e_1 + \dots + e_{k-1}$$
We need each of those to be non-negative.
Let $S_k = e_1 + e_2 + \dots + e_k$. We are given that $S_n = 0$ and the above intermediate amounts are
$$S_{k+1} - S_k, S_{k+2} - S_k, \dots, S_n - S_k, S_n - S_k + S_1, \dots S_n - S_k + S_{k-1}$$
Thus we need that for every $j$, since $S_n = 0$ that
$$ S_j \ge S_k$$
Thus we need to pick all the $k$ such that $S_k$ is the smallest.
Repeat in the other direction and we are done.
The $S_n \gt 0$ case is more interesting, and can still be solved in $O(n)$ time.
Now the conditions become
1) $ S_j \ge S_k$, for $j \gt k$
and
2) $ S_j + S_n \ge S_k$, for $j \le k$.
The candidates satisfying condition 1) can be computed by traversing the $S$ array from right to left, keeping track of the minimum seen so far.
The candidates satisfying condition 2) can be computed by traversing the array from left to right and keeping track of the smallest possible value of $Sj + S_n$.
No comments:
Post a Comment