Finding minimum number of jumps increasing the value of the element

user_13899089 0
Viewed 201

Optimizing a leetcode-style question - DP/DFS

The task is the following:

  • Given N heights, find the minimum number of suboptimal jumps required to go from start to end. [1-D Array]
  • A jump is suboptimal, if the height of the starting point i is less or equal to the height of the target point j.
  • A jump is possible, if j-i >= k, where k is the maximal jump distance.
  • For the first subtask, there is only one k value.
  • For the second subtask, there are two k values; output the amount of suboptimal jumps for each k value.
  • For the third subtask, there are 100 k values; output the amount of suboptimal jumps for each k value.

My Attempt

The following snippet is my shot at solving the problem, it gives the correct solution.

This was optimized to handle multiple k values without having to do a lot of unnecessary work. The Problem is that even a solution with a single k value is o(n^2) in the worst case. (As k <= N) A solution would be to eliminate the nested for loop, this is what I'm uncertain about how to approach it.

def solve(testcase):
    N, Q = 10, 1
    h = [1 , 2 , 4 ,2 , 8, 1, 2, 4, 8, 16] # output 3
    #    ^---- + ---^   0  ^--- + --^ + ^
    k = [3]
    l_k = max(k)



    distances = [99999999999] * N
    distances[N-1] = 0
    db = [ [0]*N for i in range(N)]

    for i in range(N-2, -1, -1):
        minLocalDistance = 99999999999
        for j in range(min(i+l_k, N-1), i, -1):   
            minLocalDistance = min(minLocalDistance, distances[j] + (h[i] <= h[j]))
            db[i][j] = distances[j] + (h[i] <= h[j])
            
        distances[i] = minLocalDistance
    print(f"Case #{testcase}: {distances[0]}")

NOTE: This is different from the classic min. jumps problem

dynamic-programming algorithm python
1 Answers

Consider the best cost to get to a position i. It is the smaller of:

  1. The minimum cost to get to any of the preceding k positions, plus one (a suboptimal jump); or
  2. The minimum cost to get to any of the lower-height position in the same window (an optimal jump).

Case (1) can be handled with the sliding-window-minimum algorithm that you can find described, for example, here: Sliding window maximum in O(n) time. This takes amortized constant time per position, or O(N) all together.

Case (2) has a somewhat obvious solution with a BST: As the window moves, insert each new position into a BST sorted by height. Remove positions that are no longer in the window. Additionally, in each node, store the minimum cost within its subtree. With this structure, you can find the minimum cost for any height bound in O(log k) time.

The expense in case 2 leads to a total complexity of O(N log k) for a single k-value. That's not too bad for complexity, but such BSTs are somewhat complicated and aren't usually provided in standard libraries.

You can make this simpler and faster by recognizing that if the minimum cost in the window is C, then optimal jumps are only beneficial if they come from predecessors of cost C, because cost C+1 is attainable with a sub-optimal jump.

For each cost, then, you can use that same sliding-window-minimum algorithm to keep track of the minimum height in the window for nodes with that cost. Then for case (2), you just need to check to see if that minimum height for the minimum cost is lower than the height you want to jump to.

Maintaining these sliding windows again takes amortized constant time per operation, leading to O(N) time for the whole single-k-value algorithm.

I doubt that there would be any benefit in trying to manage multiple k-values at once.

user_54835260
Related