sagar_is_dumb's blog

By sagar_is_dumb, history, 4 weeks ago, In English,

I am trying to solve this problem on codechef

My code is :-

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  

4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help ?

4 weeks 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].