SWAPPERM2 - Editorial

[raysh07_adm]

PROBLEM LINK:

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

Author: raysh07
Tester: archit
Editorialist: raysh07

DIFFICULTY:

Easy-Medium

PREREQUISITES:

None

PROBLEM:

Given a permutation P, define f(P) = lexicographically smallest possible permutation possible by doing the following steps:

• for each i = 1...N, either skip this, or choose X such that P_X = i or P_{X + 1} = i and then swap P_X and P_{X + 1}.

Find f(P).

EXPLANATION:

Because this is a lexicographic order minimization problem, we should try to build the answer one element at a time.

So, the natural first question is: what elements can be brought to index 1?

Suppose the prefix looks like A_1, A_2, ...., A_K, X and we ask ourselves the question whether it is possible to bring X to the start. Here we may assume X is a prefix minima, because otherwise it is clearly non-optimal.

On the X-th move, we swap A_K and X. After that, just like in SWAPPERM1, we have to depend on the A_i to be able to swap with X, since X cannot be swapped anymore.

This means that A_1 > A_2 > ... > A_{K - 1} must hold, because we require that the A_i-th move occur before the A_{i - 1}-th move.

This condition is both necessary and sufficient to be able to get X to the first position (along with X being prefix minima).

Thus, let P be the length of the longest decreasing prefix. Then, the first element will be either A_P or A_{P + 2} depending on whichever is smaller. (Because A_1, A_2, ..., A_{P - 1}, A_{P + 1} are larger than A_P, and A_i for i \ge P + 3 do not satisfy the decreasing condition)

---

What happens after we bring X to the beginning? Let’s think of 2 cases, depending on whether we bring the index P or P + 2.

• Case 1 - The index P is brought to 1:
  Then, we did not affect any indices greater than P + 1. They still have their swappability maintained. Also, only A_{P - 1} can still be swapped with other elements (which is now present at A_P), the others become fixed. However, if we swap A_{P - 1} with T (using T to swap, this restriction is not present if we use A_p to swap) later on, it must satisfy T > A_P because we require the T-th swap to occur after the A_p-th swap.

• Case 2 - The index P + 2 is brought to 1:
  A similiar analysis follows. All indices \ge P + 3 are intact. The element A_{p + 1} may be swapped and again we get some restriction on T.

---

We can just simulate this process of finding the longest decreasing sequence, and then trying the 2 options of P or P + 2. It will work in amortized O(N) time. We maintain a vector used_i that denotes the maximum element somebody has been swapped with, so that we can judge whether a swap is ok or not.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's Code (C++)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

vector <int> g(vector <int> p){
    int l = 0;
    int n = p.size();
    
    vector <int> ans;
    
    // the last thing may not be swappable anymore 
    vector <int> used(n + 1, 0); // must be strictly increasing 
    
    while (l < n){
        int r = l;
        while (r + 1 < n && p[r + 1] < p[r]){
            r++;
        }
        
        bool take_this = true;
        if (r + 2 < n && p[r + 2] < p[r]){
            take_this = false;
        }
        
        bool flag = false;
        
        if (take_this){
            if (l == r){
                ans.push_back(p[l]);
                l++;
            } else {
                if (used[p[r - 1]] > p[r]){
                    flag = true;
                }
                used[p[r - 1]] = p[r];
                ans.push_back(p[r]);
                for (int i = l; i < r - 1; i++){
                    ans.push_back(p[i]);
                }
                swap(p[r - 1], p[r]);
                l = r;
            }
        } else {
            if (used[p[r + 1]] > p[r + 2]){
                flag = true;
            }
            used[p[r + 1]] = p[r + 2];
            ans.push_back(p[r + 2]);
            for (int i = l; i <= r; i++){
                ans.push_back(p[i]);
            }
            l = r + 2;
            swap(p[l], p[l - 1]);
        }
        
        if (flag){
            ans.push_back(p[l]);
            l++;
        }
    }
    
    return ans;
}

void Solve() 
{
    int n; cin >> n;
    
    vector <int> p(n);
    for (int i = 0; i < n; i++){
        cin >> p[i];
    }
    
    auto fast_ans = g(p);
    for (auto x : fast_ans){
        cout << x << " ";
    }
    cout << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}