# MMP - Editorial

Author: Danny Boy
Tester: Anay Karnik
Editorialist: Mohan Abhyas

MEDIUM

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])

# 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';
}
}

1 Like

The editorial is honestly very confusing. It is very hard to follow the idea and not to lose your mind in all of these symbols and variables. I think MathJax is really overused here and the editorial lacks some simple natural explanations. It also seems to be improperly formatted in some places (lacking  or vice versa, cases could be written as a list). Hope you guys look into this.