sagar_is_dumb's blog

Simple DP problem- TRIP
By sagar_is_dumb, history, 6 years 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

Comments Comments (1)
| Write comment?
»
6 years 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].

→ Reply