codeforces-scrape

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

1721C.md (2604B)


      1 Source: https://codeforces.com/problemset/problem/1721/C
      2 
      3 C. Min-Max Array Transformation
      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 an array $a_1, a_2, \dots, a_n$, which is sorted in non-descending order. You decided to perform the following steps to create array $b_1, b_2, \dots, b_n$:
     22 
     23 1. Create an array $d$ consisting of $n$ arbitrary non-negative integers.
     24 2. Set $b_i = a_i + d_i$ for each $b_i$.
     25 3. Sort the array $b$ in non-descending order.
     26 
     27 You are given the resulting array $b$. For each index $i$, calculate what is the minimum and maximum possible value of $d_i$ you can choose in order to get the given array $b$.
     28 
     29 Note that the minimum (maximum) $d_i$-s are independent of each other, i. e. they can be obtained from different possible arrays $d$.
     30 
     31 Input
     32 
     33 The first line contains the single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of arrays $a$, $b$ and $d$.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$; $a_i \le a_{i+1}$) — the array $a$ in non-descending order.
     38 
     39 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$; $b_i \le b_{i+1}$) — the array $b$ in non-descending order.
     40 
     41 Additional constraints on the input:
     42 
     43 * there is at least one way to obtain the array $b$ from the $a$ by choosing an array $d$ consisting of non-negative integers;
     44 * the sum of $n$ doesn't exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, print two lines. In the first line, print $n$ integers $d_1^{min}, d_2^{min}, \dots, d_n^{min}$, where $d_i^{min}$ is the minimum possible value you can add to $a_i$.
     49 
     50 Secondly, print $n$ integers $d_1^{max}, d_2^{max}, \dots, d_n^{max}$, where $d_i^{max}$ is the maximum possible value you can add to $a_i$.
     51 
     52 All $d_i^{min}$ and $d_i^{max}$ values are independent of each other. In other words, for each $i$, $d_i^{min}$ is just the minimum value among all possible values of $d_i$.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 4
     60 
     61 3
     62 
     63 2 3 5
     64 
     65 7 11 13
     66 
     67 1
     68 
     69 1000
     70 
     71 5000
     72 
     73 4
     74 
     75 1 2 3 4
     76 
     77 1 2 3 4
     78 
     79 4
     80 
     81 10 20 30 40
     82 
     83 22 33 33 55
     84 ```
     85 
     86 Output
     87 
     88 ```
     89 5 4 2
     90 11 10 8
     91 4000
     92 4000
     93 0 0 0 0
     94 0 0 0 0
     95 12 2 3 15
     96 23 13 3 15
     97 ```
     98 
     99 Note
    100 
    101 In the first test case, in order to get $d_1^{min} = 5$, we can choose, for example, $d = [5, 10, 6]$. Then $b$ $=$ $[2+5,3+10,5+6]$ $=$ $[7,13,11]$ $=$ $[7,11,13]$.
    102 
    103 For $d_2^{min} = 4$, we can choose $d$ $=$ $[9, 4, 8]$. Then $b$ $=$ $[2+9,3+4,5+8]$ $=$ $[11,7,13]$ $=$ $[7,11,13]$.