6
$\begingroup$

Consider the following problem:

You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between two adjacent cities is one mile. We are currently at city $1$, and would like to drive to city $n$. Each day, we can drive at most $k$ miles, before we sleep for the night. We pay $a_i$ for lodging at the city located at mile $i$. Each lodging cost is a positive number. Given that we can spend an arbitrary number of days on the road trip, determine a plan of driving to minimize lodging costs.

Input: An integer $k$, and a length $n$ array of positive integers $a_1,...,a_n$.

Output: The minimum lodging cost to complete the road trip starting from city 1 and ending at city n.

The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?

$\endgroup$
  • $\begingroup$ Since $k$ is part of the input, the complexity is actually $O(n^2)$. $\endgroup$ – Yuval Filmus Mar 20 '15 at 3:27
  • $\begingroup$ Do you have more than an intuition? Does the exercise call for a better running time? Otherwise, I see no reason why you could improve on $O(n^2)$ substantially. $\endgroup$ – Yuval Filmus Mar 20 '15 at 3:28
  • $\begingroup$ The exercise does suggest that it is achievable in $O(n)$ time. However, I'm struggling to see how it can be done. $\endgroup$ – Dave Mar 20 '15 at 3:58
  • $\begingroup$ You can try other popular paradigms such as greedy and divide and conquer. $\endgroup$ – Yuval Filmus Mar 20 '15 at 6:26
  • $\begingroup$ @YuvalFilmus means to use $\Theta$ there. I don't see how even $O(n^2)$ is correct, though; $k$ is a number so $\Theta(nk)$ is pseudopolynomial, far away from linear time. $\endgroup$ – Raphael Mar 20 '15 at 6:58
4
$\begingroup$

This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.