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.