tirupati's blog

A Car Trip Of sundar
By tirupati, history, 9 years ago, In English

Today I was trying to solve some questions from codechef and I ran into this question. I tried to optimise it in different ways but I failed in every attempt. The problem statement is here. I am getting TLE on my submission here. Can someone help by giving me a rough idea on solving this question? Thank You...:)

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved it in the following manner: First sort the petrol pumps in ascending order of x let f[i] denote the minimum amount of money to be paid when we reach the ith petrol pump. We can get that f[i]=c[i]+min(f[j] such that x[i]-x[j]<=d) This will take upto n^2 operations. To speed up we can use a segment tree and find out the minimum cost of all petrol pumps in the range [x[i]-d,x[i]-1]. As x[i]<=10^9,we can precompute the left most petrol pump reachable for each i in one pass of the array. This approach takes nlogn operations. My submission:http://www.codechef.com/viewsolution/7351279

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can also solve it in O(nlogn) using set.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The naive DP approach to solve this is O(N ^ 2) Time complexity where DP[i] denotes the least money to be spent to reach ith position . And for calculating dp[i] , we have to do a range minimum query from dp[i] to dp[j] where j is the least index such that the jth position >= ith position — D . So we can use a segment tree to speed this up to O(nlogn). http://www.codechef.com/viewsolution/7353139

→ Reply