CODEWITHSUNDEEP
algorithmdata-structuresgraphdynamic-programming
Roshan
Roshan

Reputation: 35

Minimum time to reach from city 1 to N in less than O(N*N) time

There are N cities with cost given in array arr[1..N]. The time required to reach city j from city i is |i - j| * arr[i]. Condition: 2 <= N <= 10^5 and 1 <= arr[i] <= 10^9 Now, we have to find minimum time to reach city N from city 1.

I can think of two ways to solve this problem:

One way to solve this problem is to use Dynamic Programming and calculate minimum time to reach city j where 2 <= j <= N. Finally return dp[N]. But it will take O(N*N) time.

Other way is to first reach from city 1 to say city j where 2 <= j <= N with minimum time then repeat same from city j until we reach city N. But this will also take O(N*N) time in worst case.

Is there any more optimal solution for this problem?

Upvotes: 1

Views: 447

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59154

1/arr[i] is the speed at which you leave at after stopping in city i.

Just start from city 1 toward city N, and stop in any city i that would increase your speed. That is to say, stop in any city with a lower arr[i] than the last one you stopped at.

Upvotes: 2

Maras
Maras

Reputation: 982

Let's focus on your DP approach.

Observation: It's never optimal to go backwards.

We can solve it in O(n^2) using simple DP:

DP(i) - smallest cost to get to city i

DP(1) = 0

DP(i) = min 1 <= j < i { DP(j) + arr[j] * (i - j)} - you decide to go from city 1 to j somehow and then jump right to city i.

Let's change the formula a bit:

DP(i) = min 1 <= j < i { ( DP(j) - j * arr[j] ) + i * arr[j] }

We can look at it as a minimum of linear functions evaluated in specific point:

a_j = arr[j]
b_j = DP(j) - j * arr[j]
x = i

F_j(x) = a_j * x + b_j

We want to find min 1 <= j < i { F_j(i) }

There is a common DP optimization trick called Convex Hull Trick. It enables to solve DP problems having this kind of formula in O(n log n). You can find a tutorial here: https://codeforces.com/blog/entry/63823

Upvotes: 2

Related Questions