2237B.md (3461B)
1 Source: https://codeforces.com/problemset/problem/2237/B 2 3 B. Annoying the Ghost 4 5 time limit per test 6 7 1.5 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 Ja the Ghost is playing with rubber ducks. He has $n$ piles of rubber ducks arranged in a row, where the $i$-th pile contains $a_i$ ducks. Quack the Duck gives Ja a strictly increasing sequence $b_1,b_2,\ldots,b_n$ and commands him to make the piles $a_1,a_2,\ldots,a_n$ become exactly this sequence. 22 23 Ja performs the process in the following two stages: 24 25 1. Ja may add any number of ducks to each pile. 26 27 Formally, for each pile $i$, he chooses a non-negative integer $x_i$ and replaces $a_i$ with $a_i+x_i$. 28 2. Ja may repeatedly swap two adjacent piles. 29 30 Formally, he may perform the following operation any number of times, possibly zero: choose an index $i$ such that $1\le i\le n-1$, and swap the values of $a_i$ and $a_{i+1}$. 31 32 A process is called valid if, after both stages end, the sequence of pile sizes is exactly $b_1,b_2,\ldots,b_n$. 33 34 Find the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $-1$. 35 36 Input 37 38 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows. 39 40 The first line of each test case contains an integer $n$ ($1\le n\le 2000$) — the number of piles of rubber ducks. 41 42 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the initial number of rubber ducks in each pile. 43 44 The third line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$) — the final number of rubber ducks in each pile. 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 a single integer — the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $-1$. 51 52 Example 53 54 Input 55 56 ``` 57 10 58 59 3 60 61 1 2 2 62 63 1 3 5 64 65 3 66 67 2 2 1 68 69 1 2 3 70 71 2 72 73 5 1 74 75 2 4 76 77 6 78 79 6 5 4 3 2 1 80 81 1 2 3 4 5 6 82 83 7 84 85 4 7 1 6 2 5 3 86 87 1 2 3 4 5 6 7 88 89 2 90 91 2 1 92 93 2 3 94 95 4 96 97 3 2 2 1 98 99 1 2 3 4 100 101 4 102 103 4 3 2 1 104 105 1 3 4 5 106 107 5 108 109 1 5 4 3 2 110 111 2 3 4 5 6 112 113 5 114 115 10 3 8 6 9 116 117 3 6 8 9 10 118 ``` 119 120 Output 121 122 ``` 123 0 124 125 2 126 127 -1 128 129 15 130 131 12 132 133 0 134 135 4 136 137 4 138 139 3 140 141 5 142 ``` 143 144 Note 145 146 In the first test case, Ja only needs the first stage. He can set $x_1=0,x_2=1,x_3=3$, so the piles become $1,3,5$. No swaps are needed, so the answer is $0$. 147 148 In the second test case, Ja needs both stages. He can set $x_1=0,x_2=1,x_3=0$, so the piles become $2,3,1$. Then he can perform two swaps: $$ [2,3,1]\to [2,1,3]\to [1,2,3]. $$ The pile with $1$ duck must move from the third position to the first position, so at least two swaps are necessary. Therefore the answer is $2$. 149 150 In the third test case, it is impossible. The first pile initially contains $5$ ducks, but every number in the target sequence is at most $4$. Since Ja can only add ducks and cannot remove them, this pile cannot become equal to any number in the target sequence. Therefore the answer is $-1$. 151 152 In the fourth test case, no ducks need to be added. Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $15$. 153 154 In the fifth test case, no ducks need to be added. Again, Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $12$.