codeforces-scrape

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

1976B.md (1725B)


      1 Source: https://codeforces.com/problemset/problem/1976/B
      2 
      3 B. Increase/Decrease/Copy
      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 two integer arrays: array $a$ of length $n$ and array $b$ of length $n+1$.
     22 
     23 You can perform the following operations any number of times in any order:
     24 
     25 * choose any element of the array $a$ and increase it by $1$;
     26 * choose any element of the array $a$ and decrease it by $1$;
     27 * choose any element of the array $a$, copy it and append the copy to the end of the array $a$.
     28 
     29 Your task is to calculate the minimum number of aforementioned operations (possibly zero) required to transform the array $a$ into the array $b$. It can be shown that under the constraints of the problem, it is always possible.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 Each test case consists of three lines:
     36 
     37 * the first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$);
     38 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$);
     39 * the third line contains $n + 1$ integers $b_1, b_2, \dots, b_{n + 1}$ ($1 \le b_i \le 10^9$).
     40 
     41 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, print a single integer — the minimum number of operations (possibly zero) required to transform the array $a$ into the array $b$.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 1
     55 
     56 2
     57 
     58 1 3
     59 
     60 2
     61 
     62 3 3
     63 
     64 3 3 3
     65 
     66 4
     67 
     68 4 2 1 2
     69 
     70 2 1 5 2 3
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 3
     77 1
     78 8
     79 ```
     80 
     81 Note
     82 
     83 In the first example, you can transform $a$ into $b$ as follows: $[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 3]$.