codeforces-scrape

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

2254D.md (2670B)


      1 Source: https://codeforces.com/problemset/problem/2254/D
      2 
      3 D. Silhouette
      4 
      5 time limit per test
      6 
      7 2.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 Yousef has a secret array $a$ of $n$ strictly positive integers.
     22 
     23 For each element $a_i$, its shadow $b_i$ is the sum of all elements in $a$ that are strictly smaller than $a_i$. Formally:
     24 
     25 $$b_i = \sum_{\substack{1 \le j \le n\\ a_j \lt a_i}} a_j$$
     26 
     27 You are given the shadow array $b$. Your task is to reconstruct the lexicographically smallest valid array $a$ consisting of strictly positive integers that satisfies the above condition. If no such array exists, output $-1$.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.
     34 
     35 The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 2 \cdot 10^{14}$) — the shadow array.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$) — the lexicographically smallest valid array $a$ that satisfies the condition. If no valid array exists, output $-1$ instead.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 8
     49 
     50 1
     51 
     52 0
     53 
     54 5
     55 
     56 0 4 0 4 14
     57 
     58 3
     59 
     60 4 0 0
     61 
     62 3
     63 
     64 0 0 0
     65 
     66 3
     67 
     68 0 1 1
     69 
     70 4
     71 
     72 1 1 1 1
     73 
     74 7
     75 
     76 0 4 4 4 4 4 9
     77 
     78 5
     79 
     80 0 0 0 3 3
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 1
     87 
     88 2 5 2 5 6
     89 
     90 3 2 2
     91 
     92 1 1 1
     93 
     94 1 2 2
     95 
     96 -1
     97 
     98 -1
     99 
    100 1 1 1 2 2
    101 ```
    102 
    103 Note
    104 
    105 In the first test case, the answer is $a = [1]$. Since there is only one element, there are no strictly smaller elements, so its shadow is $0$. Thus $a=[1]$ is valid. It is also lexicographically smallest, because the only allowed values are positive integers, and $1$ is the smallest possible.
    106 
    107 In the second test case, the answer is $a = [2,5,2,5,6]$:
    108 
    109 * For each $2$, there is no smaller element in the array, so the shadow is $0$.
    110 * For each $5$, the strictly smaller elements are the two $2$'s, so the shadow is $2+2=4$.
    111 * For $6$, the strictly smaller elements are two $2$'s and two $5$'s, so the shadow is $2+2+5+5=14$.
    112 
    113 Therefore the shadow array is exactly $b = [0,4,0,4,14]$.
    114 
    115 In the third test case, the shadow array for $a = [3, 2, 2]$ is calculated as follows:
    116 
    117 * For $a_1 = 3$, the strictly smaller elements in the array are the two $2$s. Their sum is $2 + 2 = 4$. So, $b_1 = 4$.
    118 * For $a_2 = 2$, there are no strictly smaller elements in the array. So, $b_2 = 0$.
    119 * For $a_3 = 2$, there are no strictly smaller elements in the array. So, $b_3 = 0$.
    120 
    121 The resulting shadow array is $b = [4, 0, 0]$, which matches the input.