I can’t seem to find the correct approach for this question, and would be glad if someone explained the algorithm, or at least the logic to use.

here’s the link: http://www.codechef.com/TCFS15P/problems/SPIDY2/

I can’t seem to find the correct approach for this question, and would be glad if someone explained the algorithm, or at least the logic to use.

here’s the link: http://www.codechef.com/TCFS15P/problems/SPIDY2/

1 Like

Let DP[i] be the minimum energy required to reach the ith building.

Then DP[i] can be found out by this relation :

DP[i] = min( DP[i],DP[i - 2^k] + abs(H[i] - H[i - 2^K]) ) where k goes from 0 to j such that 2^j is the largest power of 2 less than i.

Base Condition : DP[1] = 0

and also initialize each DP[i] to infinite at the start.

3 Likes

answer is DP[n]

So is dynamic programming a must for this?

because i havent learned it yet

this is really basic dp. Just think of this as a way of using previous results we have found to find current result. Do you know recursion ??

yes, i do know recursion, so code aside, can you just give me the steps, the logic in plain language, ur thought process

suppose we have to find the min energy required to reach building i. The buildings from which we can jump to i are i - 1, i - 2, i - 4… Suppose we already know the mid energy required to reach i-1,i-2,i-4… Then simply the min energy required to reach ith building from i - 2^kth building is |height[i]-height[i-2^k]| + min energy required to reach i - 2^kth building. We find the minimum for each k and that is the answer for ith building