2072D.md (3680B)
1 Source: https://codeforces.com/problemset/problem/2072/D 2 3 D. For Wizards, the Exam Is Easy, but I Couldn't Handle It 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 Akito got tired of being a simple locksmith at a bank, so he decided to enroll in the Magical Academy and become the best wizard in the world! However, to enroll, he needed to solve a single problem on the exam, which the ambitious hero could not manage. 22 23 In the problem, he was given an array $a$ of length $n$. He needed to minimize the number of inversions$^{\text{∗}}$ in the array after applying the spell exactly once. The spell was simple; to apply it, Akito had to choose two numbers $l$ and $r$ such that $1 \le l \le r \le n$ and perform a cyclic shift of the subarray from $l$ to $r$ one position to the left. 24 25 More formally, Akito selects the subarray $[l, r]$ and modifies the array as follows: 26 27 * From the original array $[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_l }, \mathbf{ a_{l + 1} } , \mathbf{ \ldots }, \mathbf{ a_{r - 1} }, \mathbf{ a_r }, a_{r + 1}, \ldots, a_{n - 1}, a_n]$, he obtains the array $[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_{l + 1} }, \mathbf{ a_{l + 2} }, \mathbf{ \ldots }, \mathbf{ a_{r - 1} }, \mathbf{ a_{r} }, \mathbf{ a_{l} }, a_{r + 1}, \ldots, a_{n - 1}, a_{n}]$. 28 29 Akito is eager to start his studies, but he still hasn't passed the exam. Help him enroll and solve the problem! 30 31 $^{\text{∗}}$An inversion in an array $b$ of length $m$ is defined as a pair of indices $(i, j)$ such that $1 \le i \lt j \le m$ and $b_i \gt b_j$. For example, in the array $b = [3, 1, 4, 1, 5]$, the inversions are the pairs of indices $(1, 2)$, $(1, 4)$, $(3, 4)$. 32 33 Input 34 35 The first line of input contains a number $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 In the first line of each test case, there is a number $n$ ($1 \le n \le 2000$) — the length of the array $a$. 38 39 In the second line of each test case, there are $n$ numbers $a_i$ ($1 \le a_i \le 2000$) — the elements of the array $a$. 40 41 It is guaranteed that the sum of $n^2$ across all test cases does not exceed $4 \cdot 10^6$. 42 43 Output 44 45 For each test case, output two numbers $l$ and $r$ ($1 \le l \le r \le n$) — the boundaries of the subarray that should be chosen so that after applying the spell, the number of inversions in the array is minimized. 46 47 If there are multiple suitable pairs of boundaries, you may output any of them. 48 49 Example 50 51 Input 52 53 ``` 54 9 55 56 7 57 58 1 4 3 2 5 3 3 59 60 6 61 62 1 4 3 2 5 3 63 64 8 65 66 7 6 5 8 4 3 2 1 67 68 10 69 70 1 1 1 5 1 1 5 6 7 8 71 72 2 73 74 1337 69 75 76 4 77 78 2 1 2 1 79 80 3 81 82 998 244 353 83 84 3 85 86 1 2 1 87 88 9 89 90 1 1 2 3 5 8 13 21 34 91 ``` 92 93 Output 94 95 ``` 96 2 7 97 2 4 98 1 8 99 4 6 100 1 2 101 1 4 102 1 3 103 2 3 104 5 5 105 ``` 106 107 Note 108 109 In the first example, the array $[1, 4, 3, 2, 5, 3, 3]$ will turn into the array $[1, 3, 2, 5, 3, 3, 4]$. The inversions in it are $(2, 3)$, $(4, 5)$, $(4, 6)$ and $(4, 7)$. It can be shown that it is not possible to achieve fewer than $4$ inversions. 110 111 In the second example, the array $[1, 4, 3, 2, 5, 3]$ will turn into $[1, 3, 2, 4, 5, 3]$. The inversions in it are $(2, 3)$, $(4, 6)$, and $(5, 6)$. The pair $l = 2$ and $r = 6$ also works, then the array will turn into $[1, 3, 2, 5, 3, 4]$, which also has $3$ inversions — $(2, 3)$, $(4, 5)$, and $(4, 6)$. It can be shown that it is not possible to achieve fewer than $3$ inversions. 112 113 In the fourth example, choosing $l = 4$ and $r = 6$ transforms the array into $[1, 1, 1, 1, 1, 5, 5, 6, 7, 8]$. It is sorted, and therefore, there are no inversions. 114 115 In the last example, the array is initially sorted, so any operation on a segment of length at least $2$ will only increase the number of inversions.