TRIPPY IUPC Editorial

PROBLEM LINK: Exploring Undiscovered Planets

AUTHOR: tds115

DIFFICULTY: Easy-Medium

PREREQUISITES: DP, Heaps

The recurrence relation of the following problem can be defined as f(n)=a[n]+min( f(n-1),f(n-2),...,f(n-k)), where a[i] is the value of petrol per litre.

We can use the memorization technique to solve the following, to get minimum of last k elements we can maintain a heap.

Expected Solution - https://ideone.com/Dkil7V.

1 Like

Any similar problem…
Thanks

There is a whole class of problems on this topic. Key-word is “Gas Station Problem”. There are many variations.

1 Like

Thanks a lot…

No problem

Can someone explain the code or process in easier manner.
Thanks

It can also be done using deque and approach similar to sliding-window problems

Can u share your apraoch pls…

My approach was this:
for every planet a[i], we need to go to that planet from a[i+1] to a[i+k+1] with the minimum weight/cost “to the end”
to calculate the weight “to the end” we start from last and memoize the results

let n be 8 and k be 3 then the dependency would look like this
dag

so we start from the last and then maintain a priority_queue/multiset for the next k elements and remove them once we are past k elements O(NlgK )
(OR)
a deque for O(N)
my code here

Amazing, thanks you very much for explaining your method