STRSORT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: pvtr
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a permutation of \{1, 2, \ldots, N\}.
In one move, you can:

  • Swap A_i and A_j, where |i-j| \gt 1.
    This costs one coin.
  • Pick indices i \lt j \lt k such that A_i \gt A_j \lt A_k, and delete A_i from the array.
    This costs zero coins.

Find a sequence of operations that reaches a sorted array using the least number of coins possible, or claim that it’s impossible to reach a sorted array.

EXPLANATION:

The absolute best case is when we need to use 0 coins, i.e, only the delete operation is allowed.
Let’s try to figure out when this is possible.

Note that since we must choose i \lt j \lt k and delete A_i, in particular the last two elements of A will never be deleted.
So, if the final array is to be sorted, certainly A_{N-1} \lt A_N must hold.
In fact, this condition is also sufficient: if A_{N-1} \lt A_N, there always exists a sequence of deletions resulting in a sorted array.

Proof with construction

Let’s fix k = N as a constant.
Let j = N-1 initially. We’ll maintain A_j \lt A_k at all times.

Then, for each index i from N-2 down to 1:

  • If A_i \gt A_j, then we know A_i \gt A_j \lt A_k. So, delete A_i from the array.
  • If A_i \lt A_j, set j = i and continue on.

Notice that after each step, the non-deleted elements from [A_i, A_{i+1}, \ldots, A_N]$ form a sorted sequence (we only add an element to the start of the sequence, and only when it’s smaller than the previous first element).
So, when the process ends, we’ll have a sorted array and we’re done!

This gives us a hint as to how to proceed: if we end up with A_{N-1} \lt A_N, we’ll be done.

Intuitively, this means the minimum number of coins needed is also pretty small: for example, A_{N-1} and A_N can be swapped using three operations (fix some i \leq N-3, then swap(A_i, A_{N-1}), swap(A_i, A_N), swap(A_i, A_{N-1})).
So, the answer is surely \leq 3 coins.

Checking if 0 coins are needed is as mentioned above.

Checking if 1 coin is needed is also trivial: for each i from 1 to N-2, check whether swapping A_i with A_{N-1} or A_N will allow for A_{N-1} \lt A_N; if yes, perform this swap and then apply the 0 coin algorithm.
Note that A_{N-2} can’t be swapped with A_{N-1} because of the distance condition, make sure to take care of that.

We check 2 swaps for each index, and do non-trivial work at most once, so it’s still \mathcal{O}(N).

If one swap isn’t enough, then two swaps will always be enough (or, in a small handful of cases, the answer is No).

This can be done as follows:

  • If N \geq 5, then A_1 and A_2 can always be swapped with A_N and A_{N-1}.
    So, swap \min(A_1, A_2) with A_{N-1} and the other one with A_N.
    Now A_{N-1} \lt A_N.
    In fact, this even works for N = 4 when A_1 \lt A_2.
  • This leaves us with 3\leq N \leq 4 to deal with. You can either bruteforce all possible swaps/deletes here, or do a bit of casework:
    • If N = 3 and it hasn’t been sorted yet, notice that A_2 = 3 will be the case.
      In such cases, the answer is No.
    • If N = 4 and it hasn’t been sorted yet, the only possible arrays are [3, 1, 4, 2] and [3, 2, 4, 1].
      These can both be solved using two swaps: swap(A_1, A_4) followed by swap(A_1, A_3) makes A_3 \lt A_4.

The problem is now solved.

You might notice that we performed all swap operations before any delete operations, though we’re allowed to interweave them as we please.
However, performing deletes after swaps doesn’t improve optimality anyway.

Proof

If 0 coins are needed by our algorithm, no swaps are performed and it’s surely optimal.

Otherwise, we have A_{N-1} \gt A_N.
This relation will not change no matter how many deletions are done; which means that at least one swap is definitely needed.
So, the minimum number of coins needed is \geq 1.
In particular, that means our solution for the case when exactly one coin is used is also optimal.

Now, let’s look at when we used two coins.
We have A_{N-1} \gt A_N.
Further, a single swap wasn’t enough to reverse this relation. That means:

  • A_{N-1} = N (otherwise N could be placed at A_N)
  • A_N \lt A_i for every 1 \leq i \leq N-3; otherwise swapping A_i and A_{N-1} would satisfy the condition.
    Notice that since A is a permutation, this means A_N must be either 1 or 2.
    Further, if A_N = 2, then A_{N-2} = 1 will hold (otherwise 1 could be swapped to position N-1).

The final observation allows us to prove optimality via induction on N.

That is, consider a permutation of \{1, 2, \ldots, N\} (where N \geq 4) that’s of either the form [\ldots, N, 1] or [\ldots, 1, N, 2].
We claim that any such permutation requires at least 2 coins to be solved.
This can be verified manually for N = 4, so let’s look at N \gt 4.

  • If the first move is a deletion, we end up at the same pattern but with N-1 — this is because the last two elements can’t be deleted; and in the case [\ldots, 1, N, 2] the 1 can’t be deleted either.
    By inductive hypothesis we still require 2 coins.
  • if the first move is a swap, then we know for sure that A_{N-1} \gt A_N still holds (because no single swap can overcome this), and so at least one more coin is needed.
    This means \geq 2 coins are needed in total, and we’re done!

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;

const int TOTAL = 5e5;
const int N = 3e5;
const int TC = 5e4;

int SUM = 0;

vector<vector<int>> ans;
int res;

void Delete(vector<int> a){
    // for(int i = 0; i < a.size(); i++) cout<<a[i]<<" ";
    // cout<<"\n";
    int n = a.size();

    int j = n - 1, k = n;
    vector<int> c;
    int cur_rem = 0;

    for(int i = 0; i < n - 2; i++){
        if(a[i] > a[n - 2]){
            ans.push_back({2, i + 1 - cur_rem, j - cur_rem, k - cur_rem});
            cur_rem++;
        }
        else c.push_back(a[i]);
    }

    //now all the elements > an-1 are removed

    c.push_back(a[n - 2]);
    c.push_back(a[n - 1]);

    a = c;
    int removed = 0;

    n = a.size();

    vector<array<int,2>> stk;

    for(int i = 0; i < n - 2; i++){
        while(stk.size() > 0 && stk.back()[0] > a[i]){
            ans.push_back({2, stk.back()[1], i - removed + 1, n - removed});
            stk.pop_back();
            removed++;
        }
        stk.push_back({a[i], i - removed + 1});
    }

    cout<<"YES\n";
    cout<<ans.size()<<" "<<res<<"\n";
    for(int i = 0; i < ans.size(); i++){
        for(int j = 0; j < ans[i].size(); j++)
            cout<<ans[i][j]<<" ";
        cout<<"\n";
    }
}


void solve(){
    ans.clear();
    int n; cin>>n;
    assert(3 <= n && n <= N);

    SUM += n;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];

    set<int> s;
    
    vector<int> m(n + 1);
    
    for(int i = 0; i < n; i++){
        assert(a[i] >= 1 && a[i] <= n);
        s.insert(a[i]);
        m[a[i]] = i;
    }

    assert(s.size() == n);

    if(a[n - 2] < a[n - 1]){
        res = 0;
        Delete(a);
        return;
    }

    if(a[n - 2] != n){
        res = 1;
        ans.push_back({1, m[n] + 1, n});
        swap(a[m[n]], a[n - 1]);
        Delete(a);
        return;
    }

    if(n == 3){
        cout<<"NO\n";
        return;
    }

    if(a[n - 3] == 1){
        if(a[n - 1] == 2){

            // .... x, n
            res = 2;
            ans.push_back({1, 1, n - 1});
            ans.push_back({1, 1, n});
            swap(a[0], a[n - 2]);
            swap(a[0], a[n - 1]);
            Delete(a);
            return;
        }

        //  ... 1, 2, x (x > 2)
        res = 1;
        ans.push_back({1, m[2] + 1, n - 1});
        swap(a[m[2]], a[n - 2]);
        Delete(a);
        return;
    }

    if(a[n - 1] != 1){
        // .... 1, x (x > 1)
        res = 1;
        ans.push_back({1, m[1] + 1, n - 1});
        swap(a[m[1]], a[n - 2]);
        Delete(a);
        return;
    }

    //... 1, x (x > 1)
    res = 2;    
    ans.push_back({1, 1, n - 1});
    ans.push_back({1, 1, n});

    swap(a[0], a[n - 2]);
    swap(a[0], a[n - 1]);

    Delete(a);
}

int main(){
    // ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    int t; cin>>t;
    assert(1 <= t && t <= TC);

    while(t--)
        solve();

    assert(SUM <= TOTAL);
}
Tester's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

void swap(vector<vector<int> > &swaps,int a[],int pos[],int i,int j)
{
    swaps.push_back({i,j});
    swap(a[i],a[j]);
    pos[a[i]]=i;
    pos[a[j]]=j;
}

void solve(int tc)
{
    int n;
    cin >> n;
    int a[n+1],pos[n+1];
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        pos[a[i]]=i;
    }
    vector<vector<int> > swaps,dels;
    if(a[n-1]>a[n])
    {
        if(a[n-1]!=n)
            swap(swaps,a,pos,pos[n],n);
        else if(n==3)
        {
            cout << "NO\n";
            return;
        }
        else if(a[n]>2)
        {
            int i=pos[1];
            if(i==n-2)
                i=pos[2];
            swap(swaps,a,pos,i,n-1);
        }
        else if(a[n]==2 && a[n-2]!=1)
            swap(swaps,a,pos,pos[1],n-1);
        else
        {
            swap(swaps,a,pos,pos[n-1],n);
            swap(swaps,a,pos,1,n-1);
        }
    }
    assert(a[n-1]<a[n]);
    int d = 0;
    stack<int> rem;
    for(int i=n-2;i>=1;i--)
    {
        if(a[i]>a[n-1])
        {
            dels.push_back({i,n-1-d,n-d});
            d++;
        }
        else
            rem.push(i);
    }
    stack<int> final;
    while(!rem.empty())
    {
        while(!final.empty() && a[final.top()]>a[rem.top()])
        {
            dels.push_back({final.size(),final.size()+1,n-d});
            d++;
            final.pop();
        }
        final.push(rem.top());
        rem.pop();
    }
    int c = swaps.size();
    cout << "YES\n";
    cout << d+c << " " << c << '\n';
    for(int i=0;i<c;i++)
        cout << "1 " << swaps[i][0] << " " << swaps[i][1] << '\n';
    for(int i=0;i<d;i++)
        cout << "2 " << dels[i][0] << " " << dels[i][1] << " " << dels[i][2] << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    if a == sorted(a):
        print('Yes')
        print(0, 0)
        continue
    
    if n == 3 and a[1] == 3:
        print('No')
        continue
    
    print('Yes')
    
    # Solve 0
    def solve0(swaps):
        moves, pos, truepos = [], n-2, n-2
        sub = 0
        for i in reversed(range(n-2)):
            if a[i] < a[truepos]:
                pos = i + sub
                truepos = i
            else:
                moves.append([i, pos-sub, n-1-sub])
                sub += 1
        print(len(moves) + len(swaps), len(swaps))
        
        for i, j in swaps:
            print(1, i+1, j+1)
        
        for i, j, k in moves:
            print(2, i+1, j+1, k+1)
            sub += 1
    
    if a[-2] < a[-1]:
        solve0([])
        continue
    
    # Check 1
    done = False
    for i in range(n-2):
        if a[i] > a[-2]:
            done = True
            a[i], a[-1] = a[-1], a[i]
            solve0([(i, n-1)])
            break
        if i < n-3 and a[i] < a[-1]:
            done = True
            a[i], a[-2] = a[-2], a[i]
            solve0([(i, n-2)])
            break
    if done == True: continue

    # Answer is 2
    if n >= 5:
        swaps = []
        if a[0] > a[1]:
            a[0], a[-1] = a[-1], a[0]
            a[1], a[-2] = a[-2], a[1]
            swaps = [(0, n-1), (1, n-2)]
        else:
            a[0], a[-2] = a[-2], a[0]
            a[1], a[-1] = a[-1], a[1]
            swaps = [(0, n-2), (1, n-1)]
        solve0(swaps)
        continue
    
    swaps = [(0, n-1), (0, n-2)]
    a[0], a[-1] = a[-1], a[0]
    a[0], a[-2] = a[-2], a[0]
    solve0(swaps)