ARBSHUFFLE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: archit
Editorialist: raysh07

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

A permutation is called sortable if it can be sorted by the following type of operation: Choose P_X = X and then shuffle either P[1, X] or P[X, N] arbitrarily.

You are given a permutation P. Find the minimum number of swaps (not necessarily adjacent) that you need to do to make it un-sortable.

EXPLANATION:

Let us first figure out what permutations are sortable. Intuitively, having many fixed points makes it likely for a permutation to be sortable. Let us verify that claim. Here, a fixed point is a position X such that P_X = X.

Claim: Any permutation having \ge 2 fixed points is sortable.

Proof: Suppose X and Y (X < Y) are 2 fixed points. Let Z be the position of 1. If Z < Y, then we can simply put Z into the 1-st index by an operation on [1, Z] and then use index 1 to sort everyone.

Assume Z > Y now. Then, we can use an operation on [X, N] whose only purpose will be to swap P_X and P_Z. This makes the position of 1 become X. Now, we can simply use the operation on [1, Y] to put 1 into the 1-st index yet again.

What about permutations with \le 1 fixed point? Well, obviously for 0 fixed points, they are never sortable. What about 1 fixed point?

Suppose P_X = X and P_Y \ne Y for all Y \ne X.

Let us notice another observation. Suppose Y < X and P_Y < Y, then also we can sort the permutation because operating on [1, X], we just bring Y to it’s correct place making only one necessary swap without changing P_X. Now, we have 2 fixed points, so it is sortable.

Similarly, Y > X and P_Y > X implies sortable as well.

Thus, for the permutation to have one fixed point and not be sortable means that for all Y < X, P_Y > X and for all Y > X, P_Y < X. This can be verified to be not only necessary, but also sufficient since no improvements are possible.

Also this means that the only time this can happen is when the number of integers < X and > X are equal, i.e. N odd and X = \frac{N + 1}{2}

Finally, for the minimum number of swaps. Let F denote the number of current fixed points. We can obtain \lceil \frac{F}{2} \rceil by swapping 2 fixed points at a time till there are 0 left.

However, sometimes \lfloor \frac{F}{2} \rfloor is possible by leaving out exactly one fixed point. As we have seen above, that is only possible when the last fixed point is \frac{N + 1}{2} (and N is odd). In this case, we can swap the other fixed points and check manually.

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());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> p(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> p[i];
    }
    
    vector <int> fixed;
    for (int i = 1; i <= n; i++){
        if (p[i] == i){
            fixed.push_back(i);
        }
    }
    
    int m = fixed.size();
    int ans = (m + 1) / 2;
    
    if (m % 2 == 1 && n % 2 == 1 && fixed[m / 2] == (n + 1) / 2){
        for (int i = 0; i < m / 2; i++){
            int x = fixed[i];
            int y = fixed[m - 1 - i];
            swap(p[x], p[y]);
        }
        
        int pos = fixed[m / 2];
        bool good = true;
        
        for (int i = 1; i < pos; i++){
            if (p[i] < pos){
                good = false;
            }
        }
        for (int i = pos + 1; i <= n; i++){
            if (p[i] > pos){
                good = false;
            }
        }
        
        if (good){
            ans = m / 2;
        }
    }
    
    cout << ans << "\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;
}```
2

Test Case 2 : The given permutation is already sorted, so it definitely is sortable. Further, we can choose X = 1, Y = 3 and swap P_1 and P_3 to get [3, 2, 1] which is un-sortable.

How is the permutation [3, 2, 1] un-sortable? (Index 2 = 2)

Question: A permutation P is called sortable if it is possible to obtain P_i = i for each 1 \leq i \leq N after some (possibly zero) operations.

Thank you for the help.

3

The only index for Pi = i is for i = 2 in the array [3,2,1]

If we do the operation P[2, N], i.e we can replace the subarray [2,1] with [1,2] or [2,1]. The latter will result in the same array, and the former in [3,1,2]. In this array, we have no index with Pi=i.

If we do the operation P[1,2], i.e we can replace the subarray [3,2] with [2,3] or [3,2]. Similarly, the latter will result in the same array, and the former in [2,3,1]. Again in this array, we have no index with Pi=i.

Thus, we can say this is unsortable.

1 Like