PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Prasant Kumar
Tester: Harris Leung
Editorialist: Nishank Suresh
DIFFICULTY:
2076
PREREQUISITES:
Dynamic programming
PROBLEM:
You have an array A. In one move, you can choose two indices i and j with i \leq j and A_i = A_j, and set every element in the segment [i, j] to A_i.
Find the minimum number of moves required to sort A, or report that it isn’t possible.
EXPLANATION:
This problem can be solved with the help of dynamic programming.
Let dp_i denote the minimum number of moves requred to sort the first i elements of A. We want to compute dp_N.
The transitions are as follows:
Transitions
- First, if A_i \geq A_{i-1}, we can use dp_{i-1} moves to sort the first i-1 elements, and that automatically makes the first i elements sorted.
- Second, we can try to apply a move that ends at position i.
- If we choose the starting position of this move to be index j, the cost is dp_j + 1, since we require dp_j moves to sort the first j elements after making this move. Note that we can only choose an index j such that A_i = A_j.
- So, the cost of this transition is the minimum value of dp_j + 1 across all indices j \lt i with A_j = A_i
- Finally, dp_i is the minimum of the above two cases. For convenience, define dp_i = \infty (where \infty denotes some large value, say 10^9) if the first i elements cannot be sorted.
The above transitions give us a solution in \mathcal{O}(N^2), which is too slow. However, note that:
- The first case is always \mathcal{O}(1) and doesn’t really need to be optimized
- The second case is the one that might take \mathcal{O}(N). However, we are constrained to look at only those indices j \lt i such that A_j = A_i, and want the minimum dp_j across these indices.
- So, we can simply maintain an array mn, where mn_x denotes the minimum value of dp_j across all indices with A_j = x that we have seen so far.
- Updating mn is simple: once we have computed dp_i for an index i, simply set mn_{A_i} \gets \min(mn_{A_i}, dp_i)
With this optimization, our solution is now \mathcal{O}(N).
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define int long long
#define endl "\n"
using namespace __gnu_pbds;
signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int arr[n];
vector<int> op(n+1,1e9),dp(n+1,1e9);
for(int i=0;i<n;i++){
cin>>arr[i];
}
dp[0]=0;
op[arr[0]]=0;
for(int i=1;i<n;i++){
if(arr[i-1]<=arr[i]){
dp[i]=dp[i-1];
}
dp[i]=min(dp[i],1+op[arr[i]]);
op[arr[i]]=min(op[arr[i]],dp[i]);
}
cout<<(dp[n-1]<=n?dp[n-1]:-1)<<endl;
}
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+1;
int n;
ll a[N],dp[N];
void solve(){
cin >> n;
map<ll,int>f;
for(int i=1; i<=n ;i++){
cin >> a[i];
dp[i]=1e9;
if(a[i]>=a[i-1]) dp[i]=dp[i-1];
if(f[a[i]]<0){
ll s=f[a[i]]+1+(int)1e9;
dp[i]=min(dp[i],s);
}
ll s=dp[i]-1e9;
if(f[a[i]]>s) f[a[i]]=s;
}
if(dp[n]>=1e9) cout << "-1\n";
else cout << dp[n] << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
const int inf = 1e7;
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> dp(n, inf); dp[0] = 0;
vector<int> best(n+1, inf); best[a[0]] = 0;
for (int i = 1; i < n; ++i) {
if (a[i] >= a[i-1]) dp[i] = dp[i-1];
dp[i] = min(dp[i], best[a[i]] + 1);
if (a[i-1] <= a[i]) best[a[i]] = min(best[a[i]], dp[i-1]);
}
if (dp[n-1] < n) cout << dp[n-1] << '\n';
else cout << -1 << '\n';
}
}