# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

* Author:* Danny Boy

*Anay Karnik*

**Tester:***Mohan Abhyas*

**Editorialist:**# DIFFICULTY:

MEDIUM

# PREREQUISITES:

dp

# PROBLEM:

There are N stones numbered 1 through N. Each stone has a value written on it; for each valid i, the value on stone i is V_i.

You are initially on the first stone and your goal is to jump to stone N by perfoming a valid sequence of jumps. Formally, let’s denote a sequence of visited stones during these jumps by S_1, S_2, \ldots, S_M, where M-1 is the number of jumps. Then, the following conditions must be satisfied:

- 1 = S_1 \lt S_2 \lt \ldots \lt S_M = N
- for each i (1 \le i \lt M), \min(V_{S_1}, V_{S_2}, \ldots, V_{S_i}) + \max(V_{S_{i+1}}, \ldots, V_{S_M}) = S_{i+1} - S_i, which is the length of the i-th jump

Find the minimum number of jumps needed to reach stone N, or report that it is impossible to reach stone N using valid jumps.

# EXPLANATION:

dp[i][j][k] denotes minimum suffix length from stone i in sequence of stones containing i with minimum of elements in prefix of sequence till i = j and maximum of elements in suffix of sequence after i = k.

More Clearly:

Consider a sequences of stones S_1,S_2,\dots,S_l = i,\dots,S_M = N satisfying all required conditions to be valid jumps, min(V_{S_1},V_{S_2},\dots,V_{S_l=i}) = j and max(V_{S_{l+1}},\dots,V_{S_{M} = N}) = k.

dp[i][j][k] = min(M-l+1) over all such sequences satisfying above conditions

Dp Equations:

Consider the optimal sequence of stones corresponding to dp[i][j][k].

Let the sequence be S_1,S_2,\dots,S_l = i,\dots,S_M = N

S_{l+1} = S_l(= i) + min(V_{S_1},V_{S_2},\dots,V_{S_l=i})( = j) + max(V_{S_{l+1}},\dots,V_{S_{M} = N})(= k)

Let u = i+j+k

Case u = N and k = V_u

dp[i][j][k] = 1

Case V_u < k

dp[i][j][k] = dp[u][min(j, V_u)][k]+1

Case V_u = k

dp[i][j][k] = min(dp[u][min(j, V_u)][0 \dots k])+1

To efficiently compute min(dp[u][min(j, V_u)][0 \dots k]) maintain another pdp[i][j][k] = min(dp[i][j][0 \dots k])

pdp[i][j][k] = min(pdp[i][j][k-1], dp[i][j][k])

Final answer will be min(dp[1][V_1][0..N])

# TIME COMPLEXITY:

\mathcal{O}(N*N*N) per testcase.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define double long double
using namespace std;
void db() {cerr << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
cerr << a << ' ', db(b...);
}
const int N = 1e5 + 1, mod = 998244353;
int inf = 1e9 + 1;
int dp[500][501][501]{}, pre[500][501][501]{};
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
int v[n];
for (int i = 0; i < n; i++)
cin >> v[i];
int ans = inf;
for (int i = 0; i < n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
dp[i][j][k] = inf;
for (int i = 0; i < n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
pre[i][j][k] = inf;
for (int i = n - 2; i >= 0; i--){
for (int j = 1; j <= n; j++){
for (int k = 1; k <= n; k++){
int u = i + j + k;
if (u >= n or v[i] < j or v[u] > k)
dp[i][j][k] = inf;
else if (u == n - 1 and k == v[n - 1])
dp[i][j][k] = 1;
else if (v[u] < k)
dp[i][j][k] = dp[u][min(j, v[u])][k] + 1;
else
dp[i][j][k] = pre[u][min(j, v[u])][k] + 1;
pre[i][j][k] = min(pre[i][j][k - 1], dp[i][j][k]);
if (i == 0 and j == v[0])
ans = min(ans, dp[i][j][k]);
}
}
}
cout << (ans >= inf ? -1 : ans) << '\n';
}
}
```