codeforces-scrape

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

1301B.md (2967B)


      1 Source: https://codeforces.com/problemset/problem/1301/B
      2 
      3 B. Motarack's Birthday
      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 Dark is going to attend Motarack's birthday. Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.
     22 
     23 Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ($0 \leq k \leq 10^{9}$) and replaces all missing elements in the array $a$ with $k$.
     24 
     25 Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$) in the array $a$ after Dark replaces all missing elements with $k$.
     26 
     27 Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?
     28 
     29 Input
     30 
     31 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^{5}$) — the size of the array $a$.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 10 ^ {9}$). If $a_i = -1$, then the $i$-th integer is missing. It is guaranteed that at least one integer is missing in every test case.
     36 
     37 It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$.
     38 
     39 Output
     40 
     41 Print the answers for each test case in the following format:
     42 
     43 You should print two integers, the minimum possible value of $m$ and an integer $k$ ($0 \leq k \leq 10^{9}$) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$.
     44 
     45 Make sure that after replacing all the missing elements with $k$, the maximum absolute difference between adjacent elements becomes $m$.
     46 
     47 If there is more than one possible $k$, you can print any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 7
     55 5
     56 -1 10 -1 12 -1
     57 5
     58 -1 40 35 -1 35
     59 6
     60 -1 -1 9 -1 3 -1
     61 2
     62 -1 -1
     63 2
     64 0 -1
     65 4
     66 1 -1 3 -1
     67 7
     68 1 -1 7 5 2 -1 5
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 1 11
     75 5 35
     76 3 6
     77 0 42
     78 0 0
     79 1 2
     80 3 4
     81 ```
     82 
     83 Note
     84 
     85 In the first test case after replacing all missing elements with $11$ the array becomes $[11, 10, 11, 12, 11]$. The absolute difference between any adjacent elements is $1$. It is impossible to choose a value of $k$, such that the absolute difference between any adjacent element will be $\leq 0$. So, the answer is $1$.
     86 
     87 In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$.
     88 
     89 * $|a_1 - a_2| = |6 - 6| = 0$;
     90 * $|a_2 - a_3| = |6 - 9| = 3$;
     91 * $|a_3 - a_4| = |9 - 6| = 3$;
     92 * $|a_4 - a_5| = |6 - 3| = 3$;
     93 * $|a_5 - a_6| = |3 - 6| = 3$.
     94 
     95 So, the maximum difference between any adjacent elements is $3$.