Dynamic Divisor Path

Moderate

0/80

1 upvote

Problem statement

You are given an array A of N distinct positive integers. You must find the minimum cost to travel from index 0 to index N-1.

From your current index i, you can make two types of forward moves:

Step: Move to the next index, i+1. This move has a cost of 1.

Jump: Move to a future index j (where j > i). This move has a cost of j - i. A jump is only possible if the value at the destination, A[j], is a multiple of the value at your current location, A[i].

There is a special rule: whenever you successfully complete a jump from i to j, the value A[j] is permanently incremented by 1. This change can affect which future jumps are possible.

Your task is to find the minimum possible total cost to reach index N-1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of array A.

Output Format:

Print a single integer representing the minimum possible cost to travel from index 0 to N-1.

Note:

This problem can be modeled as a shortest path problem on a graph where the nodes are the indices 0 to N-1.

Since edge weights (costs) are not uniform (they can be 1 or j-i), an algorithm like Dijkstra's is required to find the minimum cost.

Sample Input 1:

6
2 5 7 3 6 8

Sample Output 1:

Explanation for Sample 1:

Let's explore possible paths from index 0 to 5:
- Path 1 (Walking): `0->1->2->3->4->5`. The cost is `1+1+1+1+1 = 5`.
- Path 2 (Using a jump): At index 0, the value is `A[0]=2`. We check for forward indices `j` where `A[j]` is a multiple of 2.
  - `A[4]=6` is a multiple of 2. A jump from `0` to `4` is possible.
  - The cost of this jump is `4 - 0 = 4`.
  - After the jump, we are at index 4. The path from 4 to 5 is a step, costing `1`.
  - The total cost for this path is `4 (jump) + 1 (step) = 5`.
Both paths have the same cost. The minimum cost is 5.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

2 <= N <= 2000
1 <= A[i] <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Dynamic Divisor Path

Console