codeforces-scrape

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

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.