FARSWAPLEX - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a permutation P.
You are allowed to swap adjacent elements if they differ by at least 2.
Find the lexicographically minimal reachable permutation.

EXPLANATION:

We can only swap adjacent elements that differ by at least 2, which means that for any 1 \le x \lt N, the relative order of x and x+1 cannot be changed.
That is, if x appears before x+1 in P, then any reachable permutation will also have x appear before x+1, and similar logic holds for when x appears after x+1 in P.

Using this idea, we can try to build up final permutations by placing elements from 1 to N (and not by looking at positions.)

In particular, suppose we’ve already placed the elements 1, 2, \ldots, x in some order, and now want to place the element x+1.
Suppose also that x appears before x+1 in P.

Then, x+1 must be placed after x - but it can be placed in any position after x, since every element after x is smaller than x (recall that we only have 1, 2, \ldots, x currently), and so can be freely swapped with x+1 as we like.

This method of building up permutations leads to a greedy solution to find the lexicographic minimum.

Let’s start with just P = [1], and place the elements 2, 3, \ldots, N in order.
Let pos_x denote the position of x in P.

First, we want to place 2.
If pos_2 \lt pos_1, we must place it as [2, 1]. Otherwise, we must place it as [1, 2].
In either case, we have no choice.

Next, consider placing 3.
Here, things are more interesting:

  • If pos_3 \lt pos_2, 3 must appear before 2.
    However, 3 is larger than both 1 and 2, so ideally we don’t want it to appear before either of them.
    So, the optimal location to place 3 is immediately to the left of 2.
    That is, [1, 2] becomes [1, 3, 2] while [2, 1] becomes [3, 2, 1].
  • If pos_3 \gt pos_2, 3 must appear after 2.
    Here, it’s best to just place it at the end so that it’s after both 1 and 2.
    So [1, 2] becomes [1, 2, 3] and [2, 1] becomes [2, 1, 3].

In fact, this logic extends to placing any value x \ge 2.

  • If pos_x \lt pos_{x-1}, place x immediately to the left of x-1.
    This satisfies the relative position constraint, while also ensuring that x is to the right of as many smaller values as possible.
  • If pos_x \gt pos_{x-1}, place x at the very end, so that all smaller values appear before it.

It is very simple to implement this algorithm in \mathcal{O}(N^2) time (linear time per x), and the constraints allow for it so we have no reason not to just do that.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))

    pos = [0]*(n+1)
    for i in range(n): pos[p[i]] = i

    ans = [1]
    for i in range(2, n+1):
        for j in range(len(ans)):
            if ans[j] == i-1:
                if pos[i] < pos[i-1]:
                    ans = ans[:j] + [i, i-1] + ans[j+1:]
                else:
                    ans.append(i)
                break
    print(*ans)
2 Likes