PROBLEM LINKS
DIFFICULTY
Easy
PRE-REQUISITES
Binary Search, Greedy algorithms
Problem:
Chef is travelling to rest from his hard work at his restaurant chain. For this Chef decides to visit N+1 cities by starting at city 0 and ending on city N. Chef can travel a maximum distance D per each day.
As it is a big trip he will stay at hotels along the way and pay for a night at each of these holes. Let the cost of a night at hotel i be c[i].
His boss wants him to make his trip as quickly as possible: say L days. Also, he wishes to impose a threshold C such that even when the Chef only stays at hotels of cost <= C, he is able to reach in L days. Find this least possible threshold C along with the least time L.
Quick Explanation:
We can solve the problem by first finding out the value of L. This can be done by assuming initially that there is no restriction on the money spent on an overnight stay. Then if we apply a greedy approach, as we travel as far as we can per day (justification in Detailed Explanation), we can find the value L.
Then combining this idea along with the use of Binary Search for value C we can find the answer to original problem.
We ask the question: “Given the value C, is it possible to reach destination in L days?” This can be answered as follows: we can remove all hotels that have a cost larger than C (since we can’t stay there any more), and see if the destination can still be reached in L days (in the same greedy manner as described with “no restrictions”).
If it can, then that means that it’s safe if we try our luck with lower values of C.
Else, the least C will be higher than current value and we apply binary search until we reach the desired value.
Detailed Explanation:
Justification for Greedy Approach:
We need to show that if an Optimal solution takes L days, and Greedy solution takes some L1 days, then we have that L1 = L.
This is generally done (in pretty much All Greedy problems) by converting the OPT soln to GREEDY by a sequence of local changes, each of which does not make the solution any worse. The logic being described is There exists some Optimal solution that does exactly what Greedy is doing (Here, the hotels visited by GREEDY are the same as the hotels visited by some OPT).
Let OPT visit hotels OPT1, OPT2, OPT[3], …, OPT[L], and GREEDY visit hotels GDY1, GDY2, GDY[3], …, GDY[L1].
Since OPT is different from GREEDY, let us say the first position where they differ is at i. That is, OPT1 = GDY1, OPT2 = GDY2, …, OPT[i-1] = GDY[i-1], and OPT[i] != GDY[i].
Now, since GDY[i-1] to GDY[i] is feasible (it is in the GREEDY solution), hence OPT[i-1] to GDY[i] is also feasible (since OPT[i-1] = GDY[i-1]).
Also, since OPT[i] is before GDY[i] (because GREEDY goes as far as possible), we have that GDY[i] to OPT[i+1] is also feasible.
Finally, the above two conditions confirm that the sequence OPT1, OPT2, …, OPT[i-1], GDY[i], OPT[i+1], OPT[i+2], …, OPT[L] is a sequence of hotels visited that is a feasible trip.
But voila! We now have that OPT resembles GREEDY some more!! That is, the first position where they differ is at position > i. Hence, we can continuously make these changes till finally OPT resembles GREEDY exactly, and hence we have that L = L1.
Binary Search on C:
As it was mentioned on the quick explanation, the idea of Binary Search can be applied to solve this problem, by exploiting some of the properties of the usage of this technique.
Namely, Binary Search technique is typically used to search for a given value on a sorted array, or for example to search for a phone number on a city’s phonebook.
The common property to all the uses that are given to binary search is that when we ask a question regarding a parameter “i”, we either get a string of 'No’s followed by 'Yes’s, or 'Yes’s followed by 'No’s: the standard examples are for the question “Is arr[i] < x?” where x is what we are searching for. A detailed tutorial on this kind of thinking can be found at TopCoder here.
Let F© = minimum number of days needed to reach city N, assuming that the threshold is c. We know that, since the cost of each hostel is <= N, F(N) = L.
We also know that, F(0) = infinity, since having a threshold of 0 means we cannot stay in any hostel. In fact, we show that F is a decreasing function.
To Show: F(c1) >= F(c2) whenever c1 <= c2. Let us consider the set of hostels we stay in given the threshold c1. Now, notice that since c2 >= c1, we can stay in those same hostels given threshold c2. Thus, we already have a trip that takes F(c1) days given the threshold c2. Since F(c2) is the minimum number of days required for all feasible trips, F(c2) <= F(c1)
The binary search now works as follows. Remember, (1) L = F(N). (2) We are aiming to find the minimum value C, such that F© = L:
low = 0, high = N; // Keep in mind that we always ensure F(low) > L, F(high) = L
while(high - low > 1)
mid = (low + high)/2
if(F(mid) > L) //finding the value of F given a threshold takes O(N) time via greedy approach
low = mid
else
high = mid
answer = high
Alternative Solutions (for subtasks):
Subtask 1:
The solution here resembles that of the approach described in the above explanations, except that we search over all possible C one after the other. Since there are N possible values of C, and O(N) time per feasibility check, we get that this solution takes O(N^2) time.
Subtask 2:
Let:
L(i) = minimum number of days to reach city i.
C(i) = minimum cost to reach city i, without losing time.
L(i) = 1 + min { L(j) : dist(i,j) <= D, j<i } – if the last stop before reaching city i was city j.
C(i) = min { max( C(j), cost-of-overnight-stay(j)) : dist(i,j)<=D, j<i, L(j) = L(i) -1, } – if the last stop before reaching city i was city j, and the respective number of days are as required
This approach will take O(min(ND, NN)) since we may have to check either previous D hotels, or atmost previous N hotels for filling in each value of L and C. This approach works for both subtask 1 and subtask 2 (since D = 9 in ST2).