ANADSW - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: mexomerf
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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
2

Got it thanks