sagar_is_dumb's blog

By sagar_is_dumb, history, 5 months ago, In English,

I am trying to solve this problem on codechef https://www.codechef.com/problems/TRIP.

My code is :- https://ideone.com/ZgA0yr

I am not sure why am I getting TLE. Any help would be great.

P.S: Code is small to go through so please go through it if possible.

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help ?

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem can be solved in linear time by using two pointers (well, three actually).

Let DP[i] be the minimum "steps" to reach station i and W[i] be the amount of ways to reach station i in the minimum number of "steps".

Suppose we are at station r. Let l1 be the leftmost station that can reach station r without refueling and l2 be the rightmost station such that DP[l2] = DP[l1]. Then DP[r] = DP[l1] + 1 and . We can calculate that sum in O(1) using prefix sums. Let , then the above formula becomes W[r] = S[l2] - S[l1 - 1].

We start by setting W[1] = 1 and in the end the answer will be DP[N] - 1 (because we're not counting steps but refuels) and W[N].