MMP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

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

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';
    }
}
1 Like