SORTARRAY - Editorial

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

Well, we are choosing the optimal calculated value for A[i] for each relaxation, won’t the minimum index of A[i] give the optimal value?

Like, A = [ 4, 2, 4, 1, 2, 4 ]
For the last 4, why will the first 4 not give the optimal value?

Help me out with a test case, please!!

1 Like

Consider A = [1, 3, 2, 1, 2, 3, 2]. If you match the last 2 with the first 2, it becomes impossible to sort the array. Instead, you have to match it with the second 2 and then match the 1's, for a final array of [1, 1, 1, 1, 2, 2, 2].

4 Likes