codeforces-scrape

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

1833D.md (3253B)


      1 Source: https://codeforces.com/problemset/problem/1833/D
      2 
      3 D. Flipper
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a permutation $p$ of length $n$.
     22 
     23 A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $\{2,3,1,5,4\}$ is a permutation, while $\{1,2,2\}$ is not (since $2$ appears twice), and $\{1,3,4\}$ is also not a permutation (as $n=3$, but the array contains $4$).
     24 
     25 To the permutation $p$, you need to apply the following operation exactly once:
     26 
     27 * First you choose a segment $[l, r]$ ($1 \le l \le r \le n$, a segment is a continuous sequence of numbers $\{p_l, p_{l+1}, \ldots, p_{r-1}, p_r\}$) and reverse it. Reversing a segment means swapping pairs of numbers $(p_l, p_r)$, $(p_{l+1}, p_{r-1})$, ..., $(p_{l + i}, p_{r - i})$ (where $l + i \le r - i$).
     28 * Then you swap the prefix and suffix: $[r+1, n]$ and $[1, l - 1]$ (note that these segments may be empty).
     29 
     30 For example, given $n = 5, p = \{2, \color{blue}{3}, \color{blue}{1}, 5, 4\}$, if you choose the segment $[l = 2, r = 3]$, after reversing the segment $p = \{\color{green}{2}, \color{blue}{1}, \color{blue}{3}, \color{green}{5}, \color{green}{4}\}$, then you swap the segments $[4, 5]$ and $[1, 1]$. Thus, $p = \{\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}\}$. It can be shown that this is the maximum possible result for the given permutation.
     31 
     32 You need to output the lexicographically maximum permutation that can be obtained by applying the operation described exactly once.
     33 
     34 A permutation $a$ is lexicographically greater than permutation $b$ if there exists an $i$ ($1 \le i \le n$) such that $a_j = b_j$ for $1 \le j \lt i$ and $a_i \gt b_i$.
     35 
     36 Input
     37 
     38 The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     39 
     40 Then the descriptions of the test cases follow.
     41 
     42 The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the size of the permutation.
     43 
     44 The second line of each test case contains $n$ integers: $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$ itself.
     45 
     46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.
     47 
     48 Output
     49 
     50 For each test case, output in a separate line the lexicographically maximum permutation of length $n$ that can be obtained from $p$ by applying the operation described in the problem exactly once.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 9
     58 
     59 5
     60 
     61 2 3 1 5 4
     62 
     63 9
     64 
     65 4 1 6 7 2 8 5 3 9
     66 
     67 4
     68 
     69 4 3 2 1
     70 
     71 2
     72 
     73 2 1
     74 
     75 6
     76 
     77 3 2 4 1 5 6
     78 
     79 7
     80 
     81 3 2 1 5 7 6 4
     82 
     83 10
     84 
     85 10 2 5 6 1 9 3 8 4 7
     86 
     87 4
     88 
     89 4 2 1 3
     90 
     91 1
     92 
     93 1
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 5 4 1 3 2 
    100 9 4 1 6 7 2 8 5 3 
    101 3 2 1 4 
    102 1 2 
    103 6 5 3 2 4 1 
    104 7 6 4 5 3 2 1 
    105 9 3 8 4 7 1 10 2 5 6 
    106 3 4 2 1 
    107 1
    108 ```
    109 
    110 Note
    111 
    112 The first example is explained in the problem statement.
    113 
    114 In the second example, the segment $[l = 9, r = 9]$ should be chosen.
    115 
    116 In the third example, the segment $[l = 1, r = 1]$ should be chosen.
    117 
    118 In the fourth example, the segment $[l = 1, r = 2]$ should be chosen.
    119 
    120 In the fifth example, the segment $[l = 5, r = 6]$ should be chosen.
    121 
    122 In the sixth example, the segment $[l = 4, r = 4]$ should be chosen.
    123 
    124 In the seventh example, the segment $[l = 5, r = 5]$ should be chosen.