codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1579E1.md (3787B)


      1 Source: https://codeforces.com/problemset/problem/1579/E1
      2 
      3 E1. Permutation Minimization by Deque
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.
     22 
     23 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.
     24 
     25 Let us consider an empty [deque](https://tinyurl.com/pfeucbux) (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}]$.
     26 
     27 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.
     28 
     29 For example, if we consider a permutation $p = [3, 1, 2, 4]$, one of the possible sequences of actions looks like this:
     30 
     31 |  |  |  |
     32 | --- | --- | --- |
     33 | $\quad$ 1. | add $3$ to the end of the deque: | deque has a sequence $[\color{red}{3}]$ in it; |
     34 | $\quad$ 2. | add $1$ to the beginning of the deque: | deque has a sequence $[\color{red}{1}, 3]$ in it; |
     35 | $\quad$ 3. | add $2$ to the end of the deque: | deque has a sequence $[1, 3, \color{red}{2}]$ in it; |
     36 | $\quad$ 4. | add $4$ to the end of the deque: | deque has a sequence $[1, 3, 2, \color{red}{4}]$ in it; |
     37 
     38 Find the lexicographically smallest possible sequence of elements in the deque after the entire permutation has been processed.
     39 
     40 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 \lt 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.
     41 
     42 Input
     43 
     44 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     45 
     46 The next $2t$ lines contain descriptions of the test cases.
     47 
     48 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.
     49 
     50 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     51 
     52 Output
     53 
     54 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.
     55 
     56 Example
     57 
     58 Input
     59 
     60 ```
     61 5
     62 4
     63 3 1 2 4
     64 3
     65 3 2 1
     66 3
     67 3 1 2
     68 2
     69 1 2
     70 2
     71 2 1
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 1 3 2 4 
     78 1 2 3 
     79 1 3 2 
     80 1 2 
     81 1 2
     82 ```
     83 
     84 Note
     85 
     86 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.