PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a permutation P.
Find the minimum integer K such that it’s possible to sort P by performing the following operation:
Choose indices i and j such that P_i + P_j \leq K, and swap the values of P_i and P_j.
EXPLANATION:
Let’s fix a value of K and analyze when P can be sorted.
Note that P is a permutation, so when it’s sorted, the value at index i will itself be i.
If P_i \geq K, then no matter which index j is chosen, we’ll have P_i + P_j \gt K.
This means it’s not possible to move P_i at all - so if P_i \neq i it’s definitely impossible to sort P.
So, let’s assume P_i = i for all i \geq K.
That means the elements K, K+1, K+2, \ldots, N are already in place - we only need to worry about elements \lt K (which are all at positions \lt K as well).
It is, in fact, always possible to sort all these small elements.
The trick here is that the element 1 can be swapped with anything else, since its sum with any element \lt K cannot exceed K.
That gives us the following sorting algorithm:
- Move 1 to index K-1, then swap it with the element K-1 to obtain P_{K-1} = K-1.
- Move 1 to index K-2, then swap it with the element K-2 to obtain P_{K-2} = K-2.
\vdots - Move 1 to index 2, then swap it with the element 2 to obtain P_2 = 2.
After this, all the other elements are in place, so P_1 = 1 will also be true.
We now have a way to check if a specific value of K allows P to be sorted: simply check if all elements \geq K are in their respective final places.
To find the minimum possible value of K, we simply extend this idea a bit: we only need to find the largest suffix that’s already in place, which is easy to do with a linear scan.
If the elements N, N-1, N-2, \ldots, K are in place, but K-1 is not, the answer is K.
Alternately, since our check for a fixed K runs in linear time, you can use binary search to find the minimum K.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in reversed(range(1, n+1)):
if p[i-1] != i:
ans = i+1
break
print(ans)