INVDISORD - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

None

PROBLEM:

You are given an array A of length N containing distinct integers in [1, N].
You can do the following:

  • First swap some (maybe equal) pair of elements in A.
  • Then, choose a subsequence of A and replace it by its reflection.
    This involves swapping the i-th and (sz+1-i)-th largest element of the subsequence, where 1\le i \lt sz+1-i and sz is the subsequence size.

Find whether it is possible to sort A.

EXPLANATION:

Let’s first understand the reflection operation alone - when can we use it to sort an array that’s not sorted?

For this, it’s perhaps easier to understand how it affects the position array of the elements.
That is, consider an array \text{pos}, where \text{pos}[x] denotes the (unique) index containing position x in the array.

Then, if we perform the reflection operation on a subsequence whose elements are x_1, x_2, \ldots, x_m (in sorted order), the operation is equivalent to performing
\text{swap}(\text{pos}[x_i], \text{pos}[x_{m+1-i}]) for each i with i \lt m+1-i.

Equivalently, we’re just reversing the subsequence at positions x_1, x_2, \ldots, x_m of the \text{pos} array!

Our final goal is to sort A, which is equivalent to having \text{pos}[x] = x for all x.
Let’s see when this is possible by reversing a single subsequence of \text{pos}.

Let the indices such that \text{pos}[i] \neq i be called bad indices.
Suppose these are i_1, i_2, \ldots, i_k.

Surely the subsequence we choose must include all these indices.
Further, we’ll never need to include any other index - this is because the values at all other indices must not move, and if we include an index in the subsequence that’s being reversed the value there will surely move (unless the index is the middle of the subsequence, in which case we could just not choose it and obtain the same result).

So, if any move works, it must be to choose the subsequence consisting of all bad indices.

It can now be seen that reversing the subsequence of bad indices i_1, \ldots, i_k will work if and only if \text{pos}[i_1] \gt \text{pos}[i_2] \gt\ldots \text{pos}[i_k], i.e the values at these indices are strictly decreasing.
Necessity is obvious: if the values weren’t decreasing, then after reversal they won’t be increasing so we certainly can’t have \text{pos}[x] = x for all x (which is a strictly increasing array).
Sufficiency can be proved by seeing that if these are all the bad indices, then \text{pos}[i_1] = i_k and \text{pos}[i_k] = i_1 must hold so they’ll both swap into place; and now recursively apply that logic to the remaining subsequence.

We’ve thus derived a condition for when a single reflection can work: all the bad indices in \text{pos} must form a decreasing sequence.

We now have one swap to work with to obtain this state.
Note that a swap in the array A is equivalent to a swap in the array \text{pos}, so we’re still just working with a single swap.

Suppose the initial bad indices are i_1 \lt i_2 \lt \ldots \lt i_k.
Let’s call i_j an ascent if \text{pos}[i_j] \lt \text{pos}[i_{j+1}], i.e. the subsequence ascends here.
We only have one swap - so if we do have an ascent, the swap must include at least one of its elements; otherwise the ascent will remain and we can’t have a decreasing subsequence.

There are now a couple of things that can happen:

  1. There are no ascents.
    This means the subsequence is already in descending order, so we don’t even need the swap and the answer is Yes.
  2. There are \ge 3 ascents.
    In this case, the answer is surely No, because one swap can affect at most two of the ascents, so at least one will remain and the subsequence can’t be made decreasing.
    (Technically, the ascents can overlap so a bit more casework is required when they do; but you’ll still find it’s impossible to fix all ascents with one swap).
  3. There are exactly two ascents, say i_x and i_y.
    Here, observe that any swap must include at least one of i_x and i_{x+1}, as well as at least one of i_y and i_{y+1}.
    This means there are only four candidate swaps; just try all four and check if the resulting \text{pos} can be solved using a reflection.
    With four candidates and each one being checked in linear time, this is \mathcal{O}(N) overall.
  4. There’s exactly one ascent, say at i_x.
    Here, at a surface glance there are \mathcal{O}(N) candidate swaps: i_x with any other index, or i_{x+1} with any other index.
    However, most of them can be discarded: indeed, it can be proved that if we don’t perform the swap (i_x, i_{x+1}), then there are only two other potential swaps that can work: placing i_x in its correct place (so it’s no longer a bad index), or placing i_{x+1} in its correct place (again, so it’s no longer a bad index).
    Any other swap can never work.
    So, we obtain three potential swaps; again just try all of them in linear time each.

So, we obtain a small constant (\le 4) of potential swaps, and each one can be checked in linear time for a solution in \mathcal{O}(N) overall.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def calc(pos):
    n = len(pos)

    bad = []
    for i in range(n):
        if pos[i] != i: bad.append(i)
    
    incr = []
    if len(bad) == 0: return incr

    prv = bad[0]
    for i in bad[1:]:
        if pos[i] > pos[prv]:
            incr.append([prv, i])
        prv = i
    
    return incr

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n): a[i] -= 1

    pos = [0]*n
    for i in range(n): pos[a[i]] = i

    incr = calc(pos)    
    if len(incr) == 0:
        print('Yes')
        continue
    if len(incr) > 2:
        print('No')
        continue
    
    ans = 'No'
    if len(incr) == 2:
        # only swapping first element of first pair, second element of second pair can possibly work
        # must swap some element of first pair with some element of second
        for i in incr[0]:
            for j in incr[1]:
                pos[i], pos[j] = pos[j], pos[i]
                if len(calc(pos)) == 0: ans = 'Yes'
                pos[i], pos[j] = pos[j], pos[i]
    else:
        # swap the pair, or place i or i+1 in place
        x, y = incr[0]
        for i, j in [[x, y], [x, pos[x]], [y, pos[y]]]:
            pos[i], pos[j] = pos[j], pos[i]
            if len(calc(pos)) == 0: ans = 'Yes'
            pos[i], pos[j] = pos[j], pos[i]
    print(ans)