codeforces-scrape

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

1838B.md (3135B)


      1 Source: https://codeforces.com/problemset/problem/1838/B
      2 
      3 B. Minimize Permutation Subarrays
      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 You are given a permutation $p$ of size $n$. You want to minimize the number of subarrays of $p$ that are permutations. In order to do so, you must perform the following operation exactly once:
     22 
     23 * Select integers $i$, $j$, where $1 \le i, j \le n$, then
     24 * Swap $p_i$ and $p_j$.
     25 
     26 For example, if $p = [5, 1, 4, 2, 3]$ and we choose $i = 2$, $j = 3$, the resulting array will be $[5, 4, 1, 2, 3]$. If instead we choose $i = j = 5$, the resulting array will be $[5, 1, 4, 2, 3]$.
     27 
     28 Which choice of $i$ and $j$ will minimize the number of subarrays that are permutations?
     29 
     30 A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     31 
     32 An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     33 
     34 Input
     35 
     36 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     37 
     38 The first line of each test case contains a single integer $n$ ($3 \le n \le 2\cdot 10^5$) — the size of the permutation.
     39 
     40 The next line of each test case contains $n$ integers $p_1, p_2, \ldots p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct) — the elements of the permutation $p$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output two integers $i$ and $j$ ($1 \le i, j \le n$)  — the indices to swap in $p$.
     47 
     48 If there are multiple solutions, print any of them.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 8
     56 
     57 3
     58 
     59 1 2 3
     60 
     61 3
     62 
     63 1 3 2
     64 
     65 5
     66 
     67 1 3 2 5 4
     68 
     69 6
     70 
     71 4 5 6 1 2 3
     72 
     73 9
     74 
     75 8 7 6 3 2 1 4 5 9
     76 
     77 10
     78 
     79 7 10 5 1 9 8 3 2 6 4
     80 
     81 10
     82 
     83 8 5 10 9 2 1 3 4 6 7
     84 
     85 10
     86 
     87 2 3 5 7 10 1 8 6 4 9
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 2 3
     94 1 1
     95 5 2
     96 1 4
     97 9 5
     98 8 8
     99 6 10
    100 5 4
    101 ```
    102 
    103 Note
    104 
    105 For the first test case, there are four possible arrays after the swap:
    106 
    107 * If we swap $p_1$ and $p_2$, we get the array $[2, 1, 3]$, which has 3 subarrays that are permutations ($[1]$, $[2, 1]$, $[2, 1, 3]$).
    108 * If we swap $p_1$ and $p_3$, we get the array $[3, 2, 1]$, which has 3 subarrays that are permutations ($[1]$, $[2, 1]$, $[3, 2, 1]$).
    109 * If we swap $p_2$ and $p_3$, we get the array $[1, 3, 2]$, which has 2 subarrays that are permutations ($[1]$, $[1, 3, 2]$).
    110 * If we swap any element with itself, we get the array $[1, 2, 3]$, which has 3 subarrays that are permutations ($[1]$, $[1, 2]$, $[1, 2, 3]$).
    111 
    112 So the best swap to make is positions $2$ and $3$.
    113 
    114 For the third sample case, after we swap elements at positions $2$ and $5$, the resulting array is $[1, 4, 2, 5, 3]$. The only subarrays that are permutations are $[1]$ and $[1, 4, 2, 5, 3]$. We can show that this is minimal.