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