codeforces-scrape

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

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$.