Tutorial for Codeforces 1367F2 - Flying Sort (Hard Version)

Don’t be intimidated by the official solution.

Solution #

First let’s introduce “sorted subsequence”: a sorted subsequence is a subsequence that is a subarray of the sorted array. It’s easy to see that the unmoved elements form a sorted subsequence. So if we find the longest sorted subsequence, the answer is minimized.

Since we only care about the relative order of numbers, we can compress the number which makes it easier to program. Then for each number we make an array storing all the indices of this number.

Now let’s iterate over each number. If the smallest index of the current number is greater than the biggest index of the previous number, we can simply add all the index to our subsequence. Otherwise, we need to start a new subsequence. There are two things we should notice:

Part of the indices of the current number can be added to the old subsequence. E.g. 1,2,1,1,2, the second 2 can be added so we have 1,1,1,2.
The new subsequence can also include part of the indices of the previous number. E.g. 1,2,2,1,2 we can add the first 1 to the front so we have 1,2,2,2.

There is one special case: the subsequence consists indices of two numbers and indices of both numbers are incomplete. E.g. 2,1,1,2,2,1, it’s easy to see that we need a prefix of the fist number the a suffix of the second number. So we can iterate over each prefix of the first number and find the corresponding suffix of the second number.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define all(x) (x).begin(),(x).end()
#define size(x) int(x.size())
#define pb push_back
 
using namespace std;
using ll=long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    for1(T,tt){
        int n;
        cin>>n;
        vector<int> a(n),d(n);
        forn(i,n){
            cin>>a[i];
            d[i]=a[i];
        }
        //coord compression 
        sort(all(d));
        d.resize(unique(all(d))-d.begin());
        vector<vector<int>> pos(size(d));
        forn(i,n){
            a[i]=lower_bound(all(d),a[i])-d.begin();
            pos[a[i]].push_back(i);
        }
 
        int r=-1,mxlen=0,curlen=0;
        forn(i,size(d)){
            if(pos[i][0]>r){
                curlen+=size(pos[i]);
            }else{
                //extend to the right for the old sequence
                auto j=lower_bound(all(pos[i]),r);
                mxlen=max(mxlen,curlen+int(pos[i].end()-j));
                //extend to the left for the new sequence
                auto it=lower_bound(all(pos[i-1]),pos[i][0]);
                curlen=int(it-pos[i-1].begin())+size(pos[i]);
            }
            mxlen=max(mxlen,curlen);
            r=pos[i].back();
        }
        //check the special case: sequence containing only two numbers
        forn(i,size(d)-1){
            forn(j,size(pos[i])){
                auto it=lower_bound(all(pos[i+1]),pos[i][j]);
                mxlen=max(mxlen,j+1+int(pos[i+1].end()-it));
            }
        }
        cout<<n-mxlen<<endl;
    }
    return 0;
}