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