CODEWITHSUNDEEP
algorithm
naiu
naiu

Reputation: 19

Frog jumps across a river with stones

This is different from the classic codility Frog-River-One with leaves falling at different times problem.

Problem statement

There is a part where it got cut off: If the monkey can just jump across river, the function returns 0. If it's impossible to jump across river, then -1.

Some test cases include:

[[-1, 5, -1, 5, -1, 10], 3] -> returns 5

[[1, -1, 0, 2, 3, 5], 3] -> returns 2

[[0, 0, 0, 0, 0, 0], 3] -> returns 0

The image has a problem description. I did this in a brute-force way using recursion, and although I believe it returned correct answers, it probably wasn't good enough because it would yield run time of O(n^D).

Is there a way to solve this problem more efficiently? What am I not seeing? I feel that there might be a DP solution or like a simple math trick... I am attaching my solution for reference.

My recursive solution with explanation

Upvotes: 1

Views: 2288

Answers (1)

md5
md5

Reputation: 23699

Note that the earliest time you can reach x = i can be expressed by the following recurrence relation:

shortest[i] = if A[i] = -1 then +inf 
              else max(A[i], min{shortest[j] | i - D <= j < i})

So first there is a simple O(ND) solution using only dynamic programming.

This can actually be reduced to O(N + D) using an efficient algorithm to maintain the mininum of shortest on the sliding window [i-D ... i] (using double-ended queue).

Upvotes: 3

Related Questions