Permutation Minimization by Deque (Codeforces 1579E1)
Tags: Math, constructive algorithms

In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.A permutation $$$p$$$ of size $$$n$$$ is given. A permutation of size $$$n$$$ is an array of size $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1, 4, 3, 2]$$$ and $$$[4, 2, 1, 3]$$$ are correct permutations while $$$[1, 2, 4]$$$ and $$$[1, 2, 2]$$$ are not.Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements $$$[1, 5, 2]$$$ currently in the deque, adding an element $$$4$$$ to the beginning will produce the sequence $$$[\color{red}{4}, 1, 5, 2]$$$, and adding same element to the end will produce $$$[1, 5, 2, \color{red}{4}]$$$.The elements of the permutation are sequentially added to the initially empty deque, starting with $$$p_1$$$ and finishing with $$$p_n$$$. Before adding each element to the deque, you may choose whether to add it to the beginning or the end.For example, if we consider a permutation $$$p = [3, 1, 2, 4]$$$, one of the possible sequences of actions looks like this: $$$\quad$$$ 1.add $$$3$$$ to the end of the deque:deque has a sequence $$$[\color{red}{3}]$$$ in it;$$$\quad$$$ 2.add $$$1$$$ to the beginning of the deque:deque has a sequence $$$[\color{red}{1}, 3]$$$ in it;$$$\quad$$$ 3.add $$$2$$$ to the end of the deque:deque has a sequence $$$[1, 3, \color{red}{2}]$$$ in it;$$$\quad$$$ 4.add $$$4$$$ to the end of the deque:deque has a sequence $$$[1, 3, 2, \color{red}{4}]$$$ in it;Find the lexicographically smallest possible sequence of elements in the deque after the entire permutation has been processed. A sequence $$$[x_1, x_2, \ldots, x_n]$$$ is lexicographically smaller than the sequence $$$[y_1, y_2, \ldots, y_n]$$$ if there exists such $$$i \leq n$$$ that $$$x_1 = y_1$$$, $$$x_2 = y_2$$$, $$$\ldots$$$, $$$x_{i - 1} = y_{i - 1}$$$ and $$$x_i < y_i$$$. In other words, if the sequences $$$x$$$ and $$$y$$$ have some (possibly empty) matching prefix, and the next element of the sequence $$$x$$$ is strictly smaller than the corresponding element of the sequence $$$y$$$. For example, the sequence $$$[1, 3, 2, 4]$$$ is smaller than the sequence $$$[1, 3, 4, 2]$$$ because after the two matching elements $$$[1, 3]$$$ in the start the first sequence has an element $$$2$$$ which is smaller than the corresponding element $$$4$$$ in the second sequence.

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The next $$$2t$$$ lines contain descriptions of the test cases. The first line of each test case description contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — permutation size. The second line of the description contains $$$n$$$ space-separated integers $$$p_i$$$ ($$$1 \le p_i \le n$$$; all $$$p_i$$$ are all unique) — elements of the permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should contain $$$n$$$ space-separated integer numbers — the elements of the lexicographically smallest permutation that is possible to find in the deque after executing the described algorithm.

Note: One of the ways to get a lexicographically smallest permutation $$$[1, 3, 2, 4]$$$ from the permutation $$$[3, 1, 2, 4]$$$ (the first sample test case) is described in the problem statement.

Sample Inputs:
5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

Sample Outputs:
1 3 2 4 
1 2 3 
1 3 2 
1 2 
1 2

Solution (Python):
def solution_e1(l):
    result = []
    aux = [l[0]]
    tmpmin = l[0]
    for x in l[1:]:
        if x < tmpmin:
            tmpmin = x
            aux.append(x)
        else:
            result.append(x)
    return aux[::-1] + result
t = int(input())
for _ in range(t):
    try:
        ln = int(input())
        l = input()
        l = [int(x) for x in l.split(' ')]
        s = solution_e1(l)
        print(' '.join([str(c) for c in s]))
    except Exception as e:
        print(repr(e))

Solution (Python):
from collections import deque
for __ in range(int(input())):
    N = int(input())
    L = list(map(int, input().split()))
    Deque = deque([L[0]])
    L = L[1:]
    for x in L:
        if x <= Deque[0]:
            Deque.appendleft(x)
        else:
            Deque.append(x)
    print(' '.join((str(item) for item in Deque)))

Solution (Python):
from sys import stdin
from collections import deque

def read_input():
    n = int(stdin.readline())
    p = list(map(int, stdin.readline().split()))
    return (n, p)

def solve(n, p):
    answer = deque()
    for pi in p:
        if len(answer) == 0 or pi < answer[0]:
            answer.appendleft(pi)
        else:
            answer.append(pi)
    return ' '.join(map(str, answer))

def main():
    t = int(stdin.readline())
    for _ in range(t):
        (n, p) = read_input()
        answer = solve(n, p)
        print(answer)
if __name__ == '__main__':
    main()