Author: mexomerf
Tester: yash_daga
Editorialist: iceknight1093

TBD

None

PROBLEM:

You have an array A. Any two of its elements can be swapped, as long as they’re not adjacent.
Is it possible to sort A?

EXPLANATION:

When N\geq 4, we have plenty of freedom - in fact, enough freedom that it’s always possible to sort the array!

Proof

Let’s show that given any two indices i and j (i \lt j), we can swap the values of A_i and A_j without changing the rest of the array.

First, of course if i and j aren’t adjacent indices we can swap them directly; which means we only need to care about j = i+1.
Now,

• If i = 1, index 4 is not adjacent to either i or j.
So, perform the sequence: \text{swap}(A_1, A_4) \to \text{swap}(A_2, A_4) \to \text{swap}(A_1, A_4).
After these three moves, you can see that the values at positions 1 and 2 have swapped places, and everything else is as it was before.
• If i \geq 3, index 1 is not adjacent to either i or j; so do the same as above.
• If i = 2, we have the following sequence of moves:
\text{swap}(A_2, A_4) \to \text{swap}(A_3, A_1) \to \text{swap}(A_1, A_4) \to \text{swap}(A_2, A_4) \to \text{swap}(A_1, A_3).
Once again, you can verify that this swaps the values at indices 2 and 3, with the others being unchanged.

That leaves us with N \leq 3.

• If N = 1, the array is already sorted.
• If N = 2, no swaps can be made - so the answer is Yes if A is already sorted and No otherwise.
• If N = 3, the middle element can’t be moved, but the first and last can be swapped if needed.
So, as long as \min(A_1, A_3) \leq A_2 \leq \max(A_1, A_3), it’s possible to sort the array; and otherwise it isn’t.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n == 2 and a[0] > a[1]: print('No')
elif n == 3:
a[0], a[2] = min(a[0], a[2]), max(a[0], a[2])
if a[0] <= a[1] <= a[2]: print('Yes')
else: print('No')
else:
print('Yes')

2 Likes

Got it thanks