PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Med
PREREQUISITES:
None
PROBLEM:
You’re given a permutation P.
You can perform the following operation:
- Choose a pivot index i such that P_i = i.
- Then, rearrange the elements before i among those indices, and the elements after i among those indices.
Find the minimum number of operations needed to sort P, if it’s possible at all.
EXPLANATION:
P if sorted if and only if P_i = i for every index i.
Our operation appears to be quite powerful, given that we can freely rearrange a large part of the permutation with each operation.
So, it’s reasonable to expect that not too many operations will be needed.
Let’s try to check for a few small numbers.
Zero operations is trivially possible when P is already sorted; so we deal with only unsorted P from now on.
Let’s call index i a fixed point if P_i = i.
If P has no fixed points, it’s impossible to perform any operations on it at all, so the answer is immediately -1. Henceforth, we assume P has fixed points.
Suppose i is a fixed point for P.
When can we perform an operation with i and sort P?
Clearly, this is possible if and only if:
- Elements 1, 2, 3, \ldots, i-1 appear in positions 1, 2, \ldots, i-1 in some order.
- Elements i+1, i+2, i+3, \ldots, N appear in positions i+1, i+2, \ldots, N in some order.
We need to check for these conditions quickly.
Note that the two conditions are equivalent, so it suffices to check only the first.
One way of performing this check quickly is as follows:
- Let \text{pos}(x) denote the position of x in P, i.e. P_{\text{pos}(x)} = x.
- Then, the condition we want to check is simply that each of \text{pos}(1), \text{pos}(2), \ldots, \text{pos}(i-1) are all \leq i-1.
This is equivalent to checking if the maximum among them is \leq i-1.
So, all that needs to be done is build the \text{pos} array, then compute the prefix maximums of the \text{pos} array, and finally check if the appropriate prefix maximum is \leq i-1.
Now we know how to check for one operation being possible, what about two operations?
Suppose we operate first on index i, then on j.
For now, suppose j \lt i.
Now, given that the operation on j results in P being sorted, this means that after the first operation, we have P_j = j, and each of 1, 2, \ldots, j-1 appear in some order in positions 1, 2, \ldots, j-1.
However, this was achieved only by the operation on i: in particular, this means that in the initial permutation P, all the elements 1, 2, \ldots, j appeared to the left of i.
However, observe that we don’t really need to consider an arbitrary j at all.
Indeed, if we’re able to make some j work like this, we can always just choose j = 1 instead.
This gives us a fairly simple criterion for when two moves are enough: there should exist some fixed point i, such that the element 1 appears to its left.
Note that this was assuming that j \lt i; if j \gt i then we instead obtain the condition “there should exist some fixed point i, such that the element N appears to its right.”
Checking for these two conditions is rather easy: only the leftmost and rightmost fixed points matter, and their positions need to be compared against the positions of 1 and N, respectively.
What if two moves isn’t enough?
This would mean 1 appears to the right of all initial fixed points; and N appears to the left of all initial fixed points.
Our goal is, of course, to change this.
Clearly, only the positions of 1 and N, as well as fixed points, are important. We focus on those.
First, suppose there are two non-adjacent fixed points i and j; say with i+1 \lt j.
Then, since the element 1 is to the right of j (and hence i), we can use one operation on i to bring 1 to index i+1; after which it’s to the left of j so we know from above that two operations will suffice.
This leaves us with the case where we don’t have non-adjacent fixed points - which in turn means there’s either only one fixed point; or two but they’re adjacent.
Let’s now consider what happens when there’s only one fixed point, say i.
Observe that:
- If it’s possible to create a fixed point j \gt i+1, then we can create this fixed point while also placing 1 at index i+1, and the resulting permutation will only need two operations (for three in total).
- Similarly, if it’s possible to create a fixed point j \lt i-1, we can place N at i-1 and use three operations in total.
- If both are impossible, there’s in fact still one case where things work out: when both i-1 and i+1 can be made fixed points.
Doing this will give us non-adjacent fixed points, after which the resulting permutation can be solved again (though it’s easy to see that you will always require three more moves if it ever comes to this, so the final answer will be 4).
Finally, when there are two adjacent fixed points, simply try each of them independently and take the best answer.
While this looks very casework-y and annoying to implement, with some thought it’s possible to end up with something relatively clean.
First, observe that checking for the answer being 0, 1, or 2 are all easily done in linear time; with the linear algorithm for \text{ans} = 1 described above.
Further, if P contains non-adjacent fixed points, then if the first three checks fail, the answer will surely be 3.
This leaves us with the case where there are at most two fixed points remaining.
Let’s fix a fixed point, i.
We then want to check:
- Can a fixed point \gt i+1 be created?
A simple way to check for this, is to just compute the maximum element among positions i+1, i+2, \ldots, N.
If this maximum is \gt i+1 then it’s possible to create a fixed point \gt i+1 (and so the answer is 3), otherwise it’s not. - Can a fixed point \lt i-1 be created?
Similarly, a simple check for this is to find the smallest element in the prefix under consideration, and check if it’s \lt i-1. - If both above checks fail, can i-1 and i+1 be made fixed points?
This is easy to check, just look at the positions of i-1 and i+1.
If this check succeeds (where everything else failed), the answer is 4.
In the end, if every check failed, the answer is -1.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector p(n, 0);
for (int &x : p) {
cin >> x;
--x;
}
if (is_sorted(begin(p), end(p))) {
cout << 0 << '\n';
continue;
}
auto solve_split = [] (auto a) { // Assumes a has non-adjacent fixed points
int n = size(a);
// Check 0
{
if (is_sorted(begin(a), end(a))) return 0;
}
// Check 1
{
vector pos(n, 0);
for (int i = 0; i < n; ++i)
pos[a[i]] = i;
for (int i = 1; i < n; ++i) pos[i] = max(pos[i], pos[i-1]);
// pos[i] = smallest prefix that contains all of 0...i
for (int i = 0; i < n; ++i) {
if (a[i] == i) {
if (i == 0 or pos[i-1] == i-1) return 1;
}
}
}
// Check 2
{
// Fixed point after 1?
bool flag = false;
for (int i = 0; i < n; ++i) {
if (a[i] == 0) flag = true;
if (flag and a[i] == i) return 2;
}
// Fixed point before n?
flag = false;
for (int i = n-1; i >= 0; --i) {
if (a[i] == n-1) flag = true;
if (flag and a[i] == i) return 2;
}
}
// 3 is always doable
return 3;
};
auto getpos = [] (auto a) {
int n = size(a);
vector<int> fixed;
for (int i = 0; i < n; ++i) if (a[i] == i)
fixed.push_back(i);
return fixed;
};
auto fixed = getpos(p);
if (fixed.empty()) cout << -1 << '\n';
else if (fixed[0]+1 < fixed.back()) cout << solve_split(p) << '\n';
else {
// Operate once
// Fix the leftmost and rightmost things possible
// Everything else: place in sorted order (really only care about 1 and n, which should be as far left/right as possible resp.)
// At most two ops, try both
int ans = 100;
for (int i = 0; i < n; ++i) {
if (p[i] != i) continue;
vector q(n, -1);
q[i] = i;
set<int> vals;
for (int j = 0; j < i; ++j) vals.insert(p[j]);
for (int j = 0; j < i; ++j) {
if (vals.count(j)) {
q[j] = j;
vals.erase(j);
break;
}
}
for (int j = 0; j < i; ++j) {
if (q[j] != -1) continue;
q[j] = *begin(vals);
vals.erase(q[j]);
}
vals.clear();
for (int j = i+1; j < n; ++j) vals.insert(p[j]);
for (int j = n-1; j > i; --j) {
if (vals.count(j)) {
q[j] = j;
vals.erase(j);
break;
}
}
for (int j = i+1; j < n; ++j) {
if (q[j] != -1) continue;
q[j] = *begin(vals);
vals.erase(q[j]);
}
fixed = getpos(q);
if (fixed[0]+1 < fixed.back()) ans = min(ans, 1 + solve_split(q));
}
if (ans == 100) ans = -1;
cout << ans << '\n';
}
}
}