DEARRANGE-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh

DIFFICULTY:

2882

PREREQUISITES:

Derangement, next_permutation or random shuffle

PROBLEM:

You are given a permutation P of length N. A permutation of length N is an array where every element from 1 to N occurs exactly once.

You must perform some operations on the array to make it sorted in increasing order. In one operation, you must:

  • Select two indices L and R (1 \leq L \lt R \leq N)
  • Completely dearrange the subarray P_L, P_{L+1}, \ldots P_R

A dearrangement of an array A is any permutation B of A for which B_i \neq A_i for all i.

For example, consider the array A = [2, 1, 3, 4]. Some examples of dearrangements of A are [1, 2, 4, 3], [3, 2, 4, 1] and [4, 3, 2, 1]. [3, 5, 2, 1] is not a valid dearrangement since it is not a permutation of A. [1, 2, 3, 4] is not a valid dearrangement either since B_3 = A_3 and B_4 = A_4.

Find the minimum number of operations required to sort the array in increasing order. It is guaranteed that the given permutation can be sorted in atmost 1000 operations.

HINT

The answer is always less than or equal to 2

EXPLANATION:

If the permutation P is already sorted the answer is 0. Let us look at the case when we can sort the permutation by just one move. If there exists a subarray P[L,R] such that for each index i in the prefix P[1,L-1], P_i=i and for each index j in the suffix P[R+1,N], P_j=j and for all index k in the subarray P[L,R], P_k!=k. Then we can derange the subarray P[L,R] to achieve the sorted premutation. Otherwise we can always do just 2 operations to obtain the sorted permutation.

By Brute Force we can check that for all permutations of size 4 or greater there exists a derangement such that for no index i, P_i=i in the resulting derangement. Now, apply the operation on the whole permutation P. To obtain the derangement of P such that for no index i P_i=i in the derangement we break the array into size 4 consecutive subarrays starting from the index 1. Merge the last subarray to the second last subarray if it has a size less than 4. Now iterate over all permutations possible of the elements of these 4 size subarrays and check whether the permutation is a derangement as well as for no index i in the array we get P_i=i by the derangement. This can be easily implemented using the next_permutaion and single for loop in C++.
The only case that remains is when N=3.The only edge case in which an answer exists and it is not possible to get the answer using the approach defined above is P=[3,2,1]. This case can be solved beforehand and taken into account.

Answer for P={3,2,1}

2
1\: 2
2 \: 3\: 1
1 \: 3
1\: 2\: 3

TIME COMPLEXITY:

O(N) or O(N^2) depending on implementation for each test case.

SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myrand(ll l,ll r)
{
    ll temp=rng();
    temp=abs(temp);
    temp%=(r-l+1);
    temp+=l;
    return temp;
}
int sumN=0;
void solve()
{
    int n=readInt(3,1000,'\n');
    sumN+=n;
    assert(sumN<=1000);
    int A[n+1]={0};
    int mark[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        if(i==n)
            A[i]=readInt(1,n,'\n');
        else
            A[i]=readInt(1,n,' ');
        mark[A[i]]=1;
    }
    for(int i=1;i<=n;i++)
        assert(mark[i]==1);
    int l=n+1,r=0;
    for(int i=1;i<=n;i++)
    {
        if(A[i]!=i)
            r=i;
    }
    for(int i=n;i>=1;i--)
    {
        if(A[i]!=i)
            l=i;
    }
    if(l>r)
    {
        cout<<0<<'\n';
        return;
    }
    for(int i=l;i<=r;i++)
    {
        if(A[i]==i)
        {
            cout<<2<<'\n';
            cout<<1<<' '<<n<<'\n';
            vector <int> v;
            for(int i=1;i<=n;i++)
                v.pb(i);
            int iter=0;
            while(true)
            {
                // iter++;
                // if(iter>=100)
                // {
                //     cout<<"BAD\n";
                //     cout<<n<<'\n';
                //     for(int i=1;i<=n;i++)
                //         cout<<A[i]<<' ';
                //     cout<<'\n';
                //     exit(0);
                // }
                shuffle(all(v),rng);
                int flag=1;
                for(int i=0;i<n;i++)
                {
                    if(i==0)
                    {
                        if(v[i]==A[i+1])
                        {
                            flag=0;
                            break;
                        }
                        else
                            continue;
                    }
                    if(v[i]==i+1 || v[i]==A[i+1])
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag==1)
                    break;
            }
            for(auto it:v)
                cout<<it<<' ';
            cout<<'\n';
            if(v[0]!=1)
                cout<<1<<' '<<n<<'\n';
            else
                cout<<2<<' '<<n<<'\n';
            for(int i=1;i<=n;i++)
                cout<<i<<' ';
            cout<<'\n';
            return;
        }
    }
    cout<<1<<'\n';
    cout<<l<<' '<<r<<'\n';
    for(int i=1;i<=n;i++)
        cout<<i<<' ';
    cout<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,200,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n;
    cin >> n;
    vll v(n), vv(n);
    vll check1(3);
    check1 = {3, 2, 1};
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        vv[i] = v[i];
    }
    if (v == check1)
    {
        cout << 2 << ' ';
        cout << 1 << ' ' << 2 << '\n';
        cout << 2 << ' ' << 3 << ' ' << 1 << '\n';
        cout << 1 << ' ' << 3 << '\n';
        cout << 1 << ' ' << 2 << ' ' << 3 << '\n';
        return;
    }
    //------------- Case when answer is 0
    sort(all(vv));
    if (vv == v)
    {
        cout << 0 << '\n';
        return;
    }
    //------------- Case when answer is 1
    int issortedtill[n], issortedfrom[n];
    if (v[0] == 1)
        issortedtill[0] = true;
    else
        issortedtill[0] = false;
    for (int i = 1; i < n; i++)
        if (issortedtill[i - 1] && v[i] == i + 1)
            issortedtill[i] = true;
        else
            issortedtill[i] = false;
    if (v[n - 1] == n)
        issortedfrom[n - 1] = true;
    else
        issortedfrom[n - 1] = false;
    for (int i = n - 2; i >= 0; i--)
        if (issortedfrom[i + 1] && v[i] == i + 1)
            issortedfrom[i] = true;
        else
            issortedfrom[i] = false;
    for (int i = 0; i < n; i++)
    {
        bool flag = true;
        for (int j = i; j < n; j++)
        {
            if (v[j] == j + 1)
                flag = false;
            if (flag && (j == n - 1 || issortedfrom[j + 1]) && (!i || issortedtill[i - 1]))
            {
                cout << 1 << '\n';
                cout << i + 1 << ' ' << j + 1 << '\n';
                for (auto x : vv)
                    cout << x << ' ';
                cout << '\n';
                return;
            }
        }
    }
    //------------- Case when answer is 2
    cout << 2 << '\n';
    vector<int> tillnow;
    for (int i = 0; i < n;)
    {
        vector<int> temp;
        if (n - i < 8)
            for (int j = i; j < n; j++)
                temp.pb(v[j]);
        else
            for (int j = i; j <= i + 3; j++)
                temp.pb(v[j]);
        sort(all(temp));
        bool flag = true;
        do
        {
            flag = true;
            for (int j = 0; j < temp.size(); j++)
            {
                if (v[i + j] == temp[j] || temp[j] == i + j + 1)
                    flag = false;
            }
            if (flag)
                break;
        } while (next_permutation(all(temp)));
        for (auto x : temp)
            tillnow.pb(x);
        i += temp.size();
    }
    cout << 1 << ' ' << n << '\n';
    for (auto x : tillnow)
        cout << x << ' ';
    cout << '\n';
    cout << 1 << ' ' << n << '\n';
    for (int i = 1; i <= n; i++)
        cout << i << ' ';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

1 Like

An alternative approach to the problem : https://www.codechef.com/START41A/problems/DEARRANGE


Read the editorial’s solution for the test cases in which the answer will be 0 or 1 and also one edge test case.

Now, for case when ans=2 :


Rotate the array by 1, n times and check whether the current rotated array is valid or not each time. (Valid array: If it does not match with any index of the given array and also with the sorted array).

Now, there may be a possibility that none of the rotated arrays is valid. Think of the case when will it be possible :slight_smile:

Since after each rotation, so there must be at least one index in each rotation that matches with the given array or with the sorted array, so all the indices follow some fixed order (i.e. after $x$ rotations $yth$ indexed element will make the array invalid).

How \, can \, we \, disturb \, this \, order?

Yes, it’s easy, swap any two elements to disturb the order → Just find two elements that do not match with their index, and also they should not match with their index after the swap.

The order is disturbed, now we can surely say that at least in one of the n rotations we will get the valid array.

In 2nd step, just print the sorted array.

Submission : https://ideone.com/4S9T4y

3 Likes
if(a[ids[i]]==j || a[ids[j]]==i)
 {
     swap(a[ids[i]],a[ids[j]]),done=1;
     break;
}

Can you explain this if condition for swapping in your code?

Also i tried to implement your logic by doing this:
→ if we have an array where each rotation is invalid then this implies in each rotation some element is going to its required position in sorted array. And these elements are going to be distinct for each rotation. This implies we can calculate distances for each element with respect to its position in current permutation and sorted array and this distance array must be a permutation of [0,n-1]
→ now if this distance array is the permutation of [0,n-1] then we need to swap and update distance array
→ now for rotation we want to make sure that no element comes back to its sorted position so we need to make some rotation which is not present in the distance array. Also if we did the swapping above then if we swapped (i,j) we can’t rotate by j-i since it won’t conflict with sorted array but it will with initial permutation. So we need to find such rotation value and rotate

Do you think there is a mistake here?