Jumping Frog with Energy - Difficult Dynamic Programming/Greedy Problem

Question

Given a set of n stones, arranged in a row at equal distances from each other. The stones are numbered from 0 to n-1. A frog that is on stone number 0 has to get to stone number n-1.

A jump is a move from stone i to stone j ( i<j ). Such a jump has length equal to j-i. The maximum jump length of the frog depends on its energy level (which cannot drop below 0). A jump of length j-i costs the frog j-i energy. For example, with an initial energy of 3, a frog on stone 0 can jump to stone 3 at most.

On some stones, there may be worms, which add energy to the frog. If the frog jumps on a stone with a worm on it, it MUST eat the worm. The list T[0...n-1] contains the energy values of the worms on the corresponding stones. If there is no worm on the stone, this is equivalent to a value of 0.

The frog starts with 0 Energy, but it is guaranteed that there is a worm on stone number 0.

Given a list T, the task is to return a list of the indexes of the stones on which the frog has been, before getting to stone n-1. However, this must be the shortest possible list. In some cases there may be more than one solution, whichever is accepted. It is guaranteed that always the frog will be able to get to stone n-1.

Example no. 1: For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].

Example no. 2: For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].

I have no idea how to approach this problem, all I know is that I probably need to use some dynamic programming or greedy algorithm here, but how? Anyone have any ideas?

Answer 1

You can solve this in O(n log n) time using a greedy algorithm and a priority queue.

It is quite helpful to re-frame the problem away from jumps of variable length.

New problem framing:

• Suppose you're at the 0th stone, and must walk on every stone from 0 to n-1.
• You have T[0] current energy-units initially, and every step costs 1 energy unit.
• At each stone T[i] you pass, you get an option to pay one jump-dollar and receive T[i] energy-units, at most once. Your goal is to minimize the cost in jump-dollars.
• Your energy units are not allowed to be at zero when you take a step.

The key observation is that we don't have to decide which stones we've landed on (bought energy from) until we actually need that energy for our next step.

So, keep a max-heap (priority-queue) of all the T[i] (energy-units sales) that we've passed but haven't purchased. If our current energy is 0, greedily remove the largest T[i] (energy-unit sale), add it to our current energy, and append i to the list of stones we've bought energy from.

This is akin to retroactively having decided to stop at the ith stone, which is OK since nothing is affected apart from our current energy and the list of available energy choices. This greedy algorithm works because we only ever visit a stone when it is unavoidable, and choosing any other stone to visit (instead of the highest energy unused one) can never increase our current energy.

---

Python code (using the heapq module)

def min_jump_path(stones: list[int]) -> list[int]:
    """Return a shortest valid path to end of the array.
    We must walk from index 0 to n-1, at a cost of 1 energy unit per step.
    Energy cannot be 0 when taking a step.
    Runtime: O(n log n). Space: O(n)"""

    used_stones: list[int] = [0]
    current_energy: int = stones[0]

    available_energy_choices: list[tuple[int, int]] = []

    for idx, energy_offered in enumerate(stones[1:], 1):
        current_energy -= 1

        # If we need to use some stone's energy to continue
        if current_energy < 0:

            # Return some 'error-value' if impossible
            if len(available_energy_choices) == 0:
                return []

            energy_gain, stone_used = heapq.heappop(available_energy_choices)
            energy_gain = -energy_gain  # Negated for max-heap
            current_energy += energy_gain
            used_stones.append(stone_used)

        if energy_offered > 0:
            heapq.heappush(available_energy_choices,
                           (-energy_offered, idx))  # Negated for max-heap

    # Used stone list may be out of order initially
    return sorted(used_stones)

Usage:

print(min_jump_path([3, 0, 2, 1, 0, 2, 5, 0]))
# [0, 2, 5]

print(min_jump_path([7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]))
# [0, 5, 7]