# 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

*. The logic being described is*

**does not make the solution any worse***(Here, the hotels visited by GREEDY are the same as the hotels visited by*

**There exists some Optimal solution that does exactly what Greedy is doing***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(N*D, N*N)) 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).