2254.md (24131B)
1 Source: https://codeforces.com/blog/entry/155666 2 3 Thank you for participating in the contest! I hope you enjoyed all problems :) Also, thanks to [reirugan](/profile/reirugan "Candidate Master reirugan") for proofreading the editorial. 4 5 **Rating Predictions** 6 7 | Predictor | A | B | C1 C2 | D | E | F | G | 8 | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [yse](/profile/yse "Candidate Master yse") | 800 | 800 | (900 — 1000) | 1200 | 1400 | 1700 | 2000 | 10 | [Wageeh](/profile/Wageeh "Expert Wageeh") | — | 1000 | (1300 — 1300) | 1500 | — | — | 1900 | 11 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 800 | (1000 — 1100) | 1300 | 1300 | 1900 | 2100 | 12 | [detective...dots](/profile/detective...dots "Expert detective...dots") | 800 | 900 | (1100 — 1100) | 1300 | 1400 | 1800 | 2100 | 13 | [Mr_Bald](/profile/Mr_Bald "Specialist Mr_Bald") | 800 | 900 | (1100 — 1200) | 1400 | 1500 | 1800 | — | 14 | [Argentum47](/profile/Argentum47 "Candidate Master Argentum47") | 800 | 900 | (1000 — 1200) | 1300 | 1400 | 1800 | 2000 | 15 16 **Rate the contest!** 17 18 * Excellent contest 19 * Good contest 20 * Average contest 21 * Bad contest 22 * Horrible contest 23 24 **Rate the difficulty!** 25 26 * Easy contest 27 * Normal contest 28 * Hard contest 29 30 #### [A — Riptide](https://codeforces.com/contest/2254/problem/A) 31 32 **Hint** 33 34 Assume $a \le b \le c$, does $b$ ever change? 35 36 **Solution** 37 38 For simplicity, let's assume $a \le b \le c$ (we can sort the input to achieve this). The operation decreases $c$ by $1$ and increases $a$ by $1$. Therefore, $a$ is getting closer to $b$ and $c$ is also getting closer to $b$. The round ends when $2$ players have the same value, so the answer is $\min(b - a, c - b)$ since if either $a$ or $c$ become equal to $b$, the game will end. 39 40 **Code (C++)** 41 42 ``` 43 #include <bits/stdc++.h> 44 using namespace std; 45 46 int main() { 47 int t; 48 cin >> t; 49 while(t--) { 50 vector<int> v(3); 51 for(int &x : v) cin >> x; 52 sort(v.begin(), v.end()); 53 cout << min(v[2] - v[1], v[1] - v[0]) << endl; 54 } 55 } 56 ``` 57 58 **Rate the problem!** 59 60 * Excellent problem 61 * Good problem 62 * Average problem 63 * Bad problem 64 * Horrible problem 65 66 #### [B — Evanescent](https://codeforces.com/contest/2254/problem/B) 67 68 **Hint** 69 70 If we perform the operation on any character in a maximal contiguous block of length $ \gt 1$, then $f(s') = f(s)$. 71 72 **Solution** 73 74 The function $f(s)$ converts every maximal contiguous block into a block of size $1$. Therefore, removing a character from a block does not change anything if the block will still exist. The only way we can delete the whole block is if it had a size of $1$. This allows to delete the sole character that exists in the block, additionally achieving $f(s') \lt f(s)$. 75 76 When deleting a block of size $1$, we should consider what happens when the left block touches the right block. If they both contain the same character, then they would merge into one block. Therefore, the answer would decrease by $2$ (our $1$-sized block got removed, and $2$ separate blocks got merged into one). 77 78 Otherwise, if the blocks do not contain the same character, then the answer would decrease by $1$ since nothing will happen other than removing the $1$-sized block. 79 80 **Code (C++)** 81 82 ``` 83 #include <bits/stdc++.h> 84 using namespace std; 85 86 int main() { 87 int t; 88 cin >> t; 89 while(t--) { 90 int n; 91 cin >> n; 92 string s; 93 cin >> s; 94 95 int ans = 1, x = 0; 96 for(int i = 1; i < n; i++) { 97 if(s[i] != s[i - 1]) ans++; 98 if(i == n - 1) break; 99 100 if(s[i] != s[i - 1] && s[i] != s[i + 1]) { 101 if(s[i + 1] == s[i - 1]) x = 2; 102 else x = max(x, 1); 103 } 104 } 105 106 cout << ans - x << endl; 107 } 108 } 109 ``` 110 111 **Rate the problem!** 112 113 * Excellent problem 114 * Good problem 115 * Average problem 116 * Bad problem 117 * Horrible problem 118 119 #### [C1 — Marenol (easy version)](https://codeforces.com/contest/2254/problem/C1) 120 121 **Hint 1** 122 123 The operation is equivalent to freely swapping $a_i$ with $a_{i+2}$ for any valid index $i$. 124 125 **Hint 2** 126 127 After the reduction from Hint 1, we can treat $a$ as two separate strings. 128 129 **Solution** 130 131 Notice that the operation can be treated as swapping $a_i$ with $a_{i+2}$, this works since the operation does not change the middle element, and only changes the first one and the third one. 132 133 Because an element can only move in steps of two, it can never change the parity of its index. Any character at an odd position will always remain at an odd position, and the same applies for even indices. 134 135 Since we have the power to swap the characters at odd indices endlessly (as many times as we want), we can rearrange them into any arrangement we want, independently of the characters at even indices. Therefore, the elements at odd positions in $a$ can match the elements at odd positions in $b$ if they have the same number of ones (or zeros). The same can be applied for even positions. 136 137 **Code (C++)** 138 139 ``` 140 #include <bits/stdc++.h> 141 using namespace std; 142 143 int main() { 144 int t; 145 cin >> t; 146 while(t--) { 147 int n; 148 cin >> n; 149 string a, b; 150 cin >> a >> b; 151 152 int cnta[2] = {}, cntb[2] = {}; 153 for(int i = 0; i < n; i++) { 154 cnta[i % 2] += a[i] == '1'; 155 cntb[i % 2] += b[i] == '1'; 156 } 157 158 cout << (cnta[0] == cntb[0] && cnta[1] == cntb[1] ? "YES" : "NO") << endl; 159 } 160 } 161 ``` 162 163 **Rate the problem!** 164 165 * Excellent problem 166 * Good problem 167 * Average problem 168 * Bad problem 169 * Horrible problem 170 171 #### [C2 — Marenol (hard version)](https://codeforces.com/contest/2254/problem/C2) 172 173 **Solution** 174 175 Building off the core observation from the easy version, we know that elements are strictly trapped in their own parity. Odd-indexed characters only interact with odd-indexed characters, and even with even. 176 177 The problem then boils down to a classic task: what is the minimum number of adjacent swaps needed to transform a binary array into another? 178 179 Since all '$\texttt{1}$'s are identical, they never need to leapfrog over each other. The optimal path is always for the $k$-th '$\texttt{1}$' in your starting array to walk directly to the position of the $k$-th '$\texttt{1}$' in your target array. 180 181 To implement this, just iterate through both strings and collect the positions of the '$\texttt{1}$'s in the odd indices into one list, and the positions of the '$\texttt{1}$'s in the even indices into another. If the lengths of the corresponding lists for $a$ and $b$ don't match, it's impossible to transform, so output $-1$. Otherwise, just sum up the absolute differences between the $k$-th elements of the starting and target lists for both the odd and even arrays. That sum, divided by $2$, is your exact minimum number of operations. We divide by $2$ because one operation moves characters by $2$ steps. 182 183 **Code (C++)** 184 185 ``` 186 #include <bits/stdc++.h> 187 using namespace std; 188 #define ll long long 189 190 int main() { 191 int t; 192 cin >> t; 193 while(t--) { 194 int n; 195 cin >> n; 196 string a, b; 197 cin >> a >> b; 198 199 ll ans = 0; 200 bool ok = true; 201 202 for(int k = 0; k < 2; k++) { 203 vector<int> p1, p2; 204 for(int i = k; i < n; i += 2) { 205 if(a[i] == '1') p1.push_back(i); 206 if(b[i] == '1') p2.push_back(i); 207 } 208 209 if(p1.size() != p2.size()) { 210 ok = false; 211 break; 212 } 213 214 for(int i = 0; i < p1.size(); i++) ans += abs(p1[i] - p2[i]); 215 } 216 217 if(!ok) cout << -1 << endl; 218 else cout << ans / 2 << endl; 219 } 220 } 221 ``` 222 223 **Rate the problem!** 224 225 * Excellent problem 226 * Good problem 227 * Average problem 228 * Bad problem 229 * Horrible problem 230 231 #### [D — Silhouette](https://codeforces.com/contest/2254/problem/D) 232 233 **Hint 1** 234 235 Equal values in $a$ will always have the exact same shadow, and larger elements always have strictly larger shadows. So if you sort the distinct values of $b$, they correspond in order to the distinct values of $a$: the group with the $i$-th smallest value has shadow equal to the $i$-th smallest distinct value in $b$. 236 237 **Hint 2** 238 239 Let $s_1 \lt s_2 \lt \dots \lt s_m$ be the distinct sorted values of $b$, and let group $i$ be all elements sharing the value corresponding to $s_i$. Then $s_i$ is the sum of all groups smaller than group $i$, and $s_{i+1}$ is that same sum plus group $i$ itself. So $s_{i+1} - s_i = c_i \cdot v_i$, where $c_i$ is the count of elements in group $i$ and $v_i$ is their value. 240 241 **Hint 3** 242 243 What must $s_1$ be? And once every $v_i$ is pinned down by the equation above, is there a group left with no equation constraining its value? What's the smallest legal choice for it? 244 245 **Solution** 246 247 It's easy to see that equal values in $a$ produce equal shadows. The converse also holds: distinct values in $a$ always produce distinct shadows, and moreover a larger value always produces a larger shadow. So if we sort the distinct values of $a$ as $v_1 \lt v_2 \lt \dots \lt v_k$ with frequencies $c_1, \dots, c_k$, then the shadow of group $i$ is simply the sum of all smaller groups, $S_{i-1} = \sum_{j \lt i} c_j v_j$, and these prefix sums satisfy $S_0 = 0 \lt S_1 \lt \dots \lt S_{k-1}$. In other words, the distinct values of $b$, sorted, correspond exactly and in order to these prefix sums. 248 249 This gives a direct reconstruction. Sort the distinct values of $b$ as $s_1 \lt s_2 \lt \dots \lt s_m$; since $S_0$ must be $0$, we need $s_1 = 0$, otherwise the answer is $-1$. The count of $s_i$ in $b$ gives $c_i$, the size of group $i$, and since $s_{i+1} - s_i = c_i \cdot v_i$, we can recover $v_i = \frac{(s_{i+1} - s_i)}{c_i}$. If this division isn't exact, or if the resulting $v_i$ doesn't exceed $v_{i-1}$, no valid array exists. The very last group has no such equation to pin it down, so to keep $a$ lexicographically smallest we assign it the smallest legal value, one more than the previous group's value. 250 251 Once every group's value is known, replace each $b_i$ by its group's value to get $a$. 252 253 **Code (C++)** 254 255 ``` 256 #include <bits/stdc++.h> 257 using namespace std; 258 #define ll long long 259 260 int main() { 261 int t; 262 cin >> t; 263 while(t--) { 264 int n; 265 cin >> n; 266 vector<ll> b(n); 267 map<ll, ll> freq; 268 269 for(int i = 0; i < n; i++) { 270 cin >> b[i]; 271 freq[b[i]]++; 272 } 273 274 if (!freq.count(0)) { 275 cout << -1 << endl; 276 continue; 277 } 278 279 map<ll, ll> ans; 280 ll prv_shadow = 0, prv_cnt = 0, lst = 0; 281 bool ok = true; 282 283 for(auto [cur_shadow, cur_cnt] : freq) { 284 if(cur_shadow != 0) { 285 ll diff = cur_shadow - prv_shadow; 286 287 if(diff % prv_cnt != 0) { 288 ok = false; 289 break; 290 } 291 292 ll u = diff / prv_cnt; 293 if(u <= lst) { 294 ok = false; 295 break; 296 } 297 298 ans[prv_shadow] = u; 299 lst = u; 300 } 301 302 prv_shadow = cur_shadow; 303 prv_cnt = cur_cnt; 304 } 305 306 if(!ok) { 307 cout << -1 << endl; 308 continue; 309 } 310 311 ans[prv_shadow] = lst + 1; 312 for(int i = 0; i < n; ++i) cout << ans[b[i]] << " \n"[i == n - 1]; 313 } 314 } 315 ``` 316 317 **Rate the problem!** 318 319 * Excellent problem 320 * Good problem 321 * Average problem 322 * Bad problem 323 * Horrible problem 324 325 #### [E — Chronostasis](https://codeforces.com/contest/2254/problem/E) 326 327 **Hint 1** 328 329 The problem states that $b_i = a_i - a_{i-1}$. This directly implies that $a_i = a_{i-1} + b_i$. If you assume $a_0 = 0$, you can view $a$ simply as the prefix sums of some permutation of $b$. 330 331 **Hint 2** 332 333 The standard way to achieve a lexicographically smallest sequence is to build it greedily from left to right, making $a_1$ as small as possible, then $a_2$ as small as possible, and so forth. 334 335 **Hint 3** 336 337 Since $a_{i-1}$ is fixed from the previous steps, minimizing $a_i$ means you must pick the smallest available $b_i$. However, the problem imposes a strict rule: every element in $a$ must be strictly positive ($a_i \ge 1$). How does this restrict your choice of $b_i$? 338 339 **Solution** 340 341 Let's rewrite the given operation backwards. We are told that $b_i = a_i - a_{i-1}$. By rearranging this, we get $a_i = a_{i-1} + b_i$. If we define $a_0 = 0$, the array $a$ is essentially just the prefix sums of some permutation of the array $b$. 342 343 We are asked to find a permutation of $b$ that produces an array $a$ satisfying two conditions: every $a_i$ must be strictly positive, and $a$ must be lexicographically smallest. 344 345 To construct the lexicographically smallest array $a$, we should build it greedily from left to right. Suppose we have already successfully constructed the prefix of $a$ up to $a_{i-1}$. To determine $a_i$, we need to choose an unused element from $b$ to act as $b_i$. Since $a_{i-1}$ is already fixed, minimizing $a_i$ is exactly the same as picking the smallest possible $b_i$. 346 347 However, we can't just pick the absolute minimum available element because we must guarantee that $a_i \ge 1$. Substituting our earlier equation, this means $a_{i-1} + b_i \ge 1$, which simplifies to $b_i \ge 1 - a_{i-1}$. 348 349 This gives us a clear greedy strategy. At each step $i$, we must select the smallest available element in $b$ that is greater than or equal to $1 - a_{i-1}$. To implement this efficiently, we can insert all elements of the given array $b$ into a multiset. We maintain a running sum variable to represent $a_{i-1}$ (initially $0$). At each step, we query the multiset for the `lower_bound` of $1 - a_{i-1}$. If the iterator returns the end of the multiset, it means no available element is large enough to keep the current value strictly positive. In this case, a valid array cannot be formed, and we immediately output $-1$. If a valid element is found, we add it to our running sum to compute $a_i$, store it in our answer array, and erase that element from the multiset. We repeat this process $n$ times. 350 351 **Code (C++)** 352 353 ``` 354 #include <bits/stdc++.h> 355 #define int long long 356 using namespace std; 357 358 void solve() { 359 int n, cur = 0; 360 cin >> n; 361 multiset<int> b; 362 for(int i = 0; i < n; i++) { 363 int x; 364 cin >> x; 365 b.insert(x); 366 } 367 368 vector<int> ans(n); 369 for(int i = 0; i < n; i++){ 370 auto it = b.lower_bound(1 - cur); 371 if(it == b.end()) return void(cout << -1 << '\n'); 372 cur += *it; 373 b.erase(it); 374 ans[i] = cur; 375 } 376 377 for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1]; 378 } 379 380 signed main() { 381 ios::sync_with_stdio(false); 382 cin.tie(NULL); 383 int t; 384 cin >> t; 385 while(t--) solve(); 386 } 387 ``` 388 389 **Rate the problem!** 390 391 * Excellent problem 392 * Good problem 393 * Average problem 394 * Bad problem 395 * Horrible problem 396 397 #### [F — Whiplash](https://codeforces.com/contest/2254/problem/F) 398 399 **Hint 1** 400 401 Try tracing the array elements after performing two consecutive operations, say on index $i$ and then on index $j$. If you look at the set of resulting values and ignore their order, how does it compare to the set of values you would get if you only performed a single operation on index $j$? 402 403 **Hint 2** 404 405 Any sequence of operations results in an array that is just a permutation of either the original array $a$, or the array $a$ after exactly one operation. 406 407 **Solution** 408 409 Let's analyze how a single operation affects the overall XOR sum of the array. Let $S_a$ be the XOR sum of all elements in $a$. When we choose an index $i$, we XOR $n-1$ elements with $a_i$. Since $n$ is even, $n-1$ is odd. The new XOR sum of the array will be $S_a \oplus (a_i \text{ XORed } n-1 \text{ times})$, which simplifies perfectly to $S_a \oplus a_i$. 410 411 Now, let's observe what happens if we perform multiple operations. Suppose we perform an operation on index $i$, followed by an operation on index $j$. After the first operation, the element at index $j$ becomes $a_j \oplus a_i$, and the element at index $i$ remains $a_i$. All other elements $a_k$ become $a_k \oplus a_i$. 412 413 During the second operation, we XOR everything (except index $j$) with the current value at index $j$, which is $a_j \oplus a_i$. 414 415 Let's look at the resulting values: 416 417 * For any other index $k$, the value becomes $(a_k \oplus a_i) \oplus (a_j \oplus a_i) = a_k \oplus a_j$. 418 * For index $i$, the value becomes $a_i \oplus (a_j \oplus a_i) = a_j$. 419 * For index $j$, the value remains $a_j \oplus a_i$. 420 421 If we look at this final set of values, it is exactly the same as if we had skipped the first operation and only performed a single operation on index $j$ from the very beginning. The order of the elements is different, but the set of values is identical. 422 423 This reveals the core property of the problem: no matter how many operations you perform, the resulting array (ignoring the order of elements) will either be identical to the original array $a$, or identical to the array $a$ after exactly one operation. 424 425 This gives us a straightforward solution. First, sort both arrays. If $a$ and $b$ are already identical, we output "YES" (0 operations needed). If they are not identical, we need to simulate exactly one operation. Which element $a_i$ should we use? We know from our first observation that the target XOR sum $S_b$ must equal $S_a \oplus a_i$. By rearranging this, the required element must be $a_i = S_a \oplus S_b$. We compute this target value $x = S_a \oplus S_b$. If $x$ does not exist in our initial array $a$, we can immediately output "NO". If it does exist, we find its index, apply the operation to array $a$, sort the modified array, and check if it now matches $b$. 426 427 **Code (C++)** 428 429 ``` 430 #include <bits/stdc++.h> 431 using namespace std; 432 433 signed main() { 434 int t; 435 cin >> t; 436 while(t--) { 437 int n; 438 cin >> n; 439 vector<int> a(n), b(n); 440 for(auto &it : a) cin >> it; 441 for(auto &it : b) cin >> it; 442 443 sort(a.begin(), a.end()); 444 sort(b.begin(), b.end()); 445 446 if(a == b) { 447 cout << "YES" << endl; 448 continue; 449 } 450 451 int x = 0; 452 for(auto it : a) x ^= it; 453 for(auto it : b) x ^= it; 454 455 int idx = -1; 456 for(int i = 0; i < n; i++) { 457 if(a[i] == x) { 458 idx = i; 459 break; 460 } 461 } 462 463 if(idx == -1) { 464 cout << "NO" << endl; 465 continue; 466 } 467 468 for(int i = 0; i < n; i++) { 469 if(i == idx) continue; 470 a[i] ^= x; 471 } 472 473 sort(a.begin(), a.end()); 474 cout << (a == b ? "YES" : "NO") << endl; 475 } 476 } 477 ``` 478 479 **Rate the problem!** 480 481 * Excellent problem 482 * Good problem 483 * Average problem 484 * Bad problem 485 * Horrible problem 486 487 #### [G — Nightcrawler](https://codeforces.com/contest/2254/problem/G) 488 489 **Hint 1** 490 491 Because no subset can contain branching paths, two distinct leaves can never belong to the same subset. If the tree has $\ell$ leaves, you need at least $\ell$ subsets. Any $k \lt \ell$ is impossible. For $k \ge \ell$, the condition is always satisfiable since you can always break paths into smaller singletons. 492 493 **Hint 2** 494 495 Try to build the solution bottom-up. Each leaf starts a path. When these paths meet at a parent node, the parent can only join one of them. To maximize the total score, which path's maximum should the parent node interact with? 496 497 **Hint 3** 498 499 It is always optimal for the parent to join the path that currently has the smallest maximum. If the parent's value is larger, it successfully increases that path's maximum, leaving the old maximum behind as a spare value. If the parent is smaller, the path is unaffected, and the parent itself becomes the spare value that we can use if we are allowed extra subsets. 500 501 **Solution** 502 503 The core restriction is that every subset must form a straight vertical chain (an ancestor-descendant path). This immediately tells us that two distinct leaves can never be placed in the same subset. Consequently, the minimum number of subsets $k$ we can ever form is exactly the number of leaves in the tree, which we will call $\ell$. For any $k \lt \ell$, a valid partition is impossible, and we output $-1$. For $k \ge \ell$, it is always possible because we can just break valid chains into individual singleton nodes. 504 505 Let's build the optimal chains from the bottom up. Every leaf initially forms its own chain where the maximum value is just the leaf's value. As we move up the tree, paths merge at a parent node $u$. The node $u$ must join exactly one of the chains coming from its descendants. 506 507 To maximize the overall sum of chain maximums, $u$ should greedily join the chain with the lowest current maximum. Let's say the smallest maximum among all incoming chains is $x$. If $a_u$ is greater than $x$, placing $u$ in this chain upgrades its maximum from $x$ to $a_u$. The old maximum $x$ doesn't disappear; it gets detached and becomes an extra node that we can use to form a new chain if we are allowed to use more than $\ell$ subsets. Conversely, if $a_u \le x$, placing $u$ in the chain doesn't improve the maximum at all, so $a_u$ itself becomes the detached spare node. 508 509 This process translates elegantly into a data structure approach. For each subtree, we can maintain the maximums of its active chains using a min-heap (a priority queue). When we process a node $u$, we merge all the heaps of its children. To do this efficiently, we always merge smaller heaps into larger heaps, a technique known as small-to-large merging. Once the children's paths are merged, we extract the absolute minimum element from $u$'s heap, compare it with $a_u$, push the larger of the two back into the active heap, and append the smaller one to a global list of extra available values. 510 511 By the time we finish processing the root, the root's heap will contain exactly $\ell$ elements, representing the maximums of the $\ell$ essential chains. The sum of these elements gives our optimal answer for exactly $\ell$ subsets. To find the answer for larger values of $k$, we simply sort our global list of extra values in descending order and greedily add the largest available extra to our running total for each additional subset allowed. 512 513 Because of the small-to-large merging, each element is moved between heaps at most $\mathcal{O}(\log n)$ times. Each heap operation takes logarithmic time, resulting in an overall time complexity of $\mathcal{O}(n \log^2 n)$, which comfortably passes the time limits. 514 515 **Code (C++)** 516 517 ``` 518 #include <bits/stdc++.h> 519 520 using namespace std; 521 #define ll long long 522 523 void solve() { 524 int n; 525 cin >> n; 526 527 vector<ll> a(n + 1); 528 for(int i = 1; i <= n; i++) cin >> a[i]; 529 530 vector<int> p(n + 1); 531 for(int i = 2; i <= n; i++) cin >> p[i]; 532 533 vector<priority_queue<ll, vector<ll>, greater<ll>>> pq(n + 1); 534 vector<ll> av; 535 536 for(int i = n; i >= 1; i--) { 537 if(pq[i].empty()) pq[i].push(a[i]); 538 else { 539 ll x = pq[i].top(); 540 pq[i].pop(); 541 pq[i].push(max(x, a[i])); 542 av.push_back(min(x, a[i])); 543 } 544 545 if(i > 1) { 546 int par = p[i]; 547 if(pq[par].size() < pq[i].size()) swap(pq[par], pq[i]); 548 549 while(!pq[i].empty()) { 550 pq[par].push(pq[i].top()); 551 pq[i].pop(); 552 } 553 } 554 } 555 556 int l = pq[1].size(); 557 ll sum = 0; 558 559 while(!pq[1].empty()) { 560 sum += pq[1].top(); 561 pq[1].pop(); 562 } 563 564 vector<ll> ans(n + 1, -1); 565 ans[l] = sum; 566 567 sort(av.rbegin(), av.rend()); 568 for(int i = 0; i < av.size(); i++) { 569 sum += av[i]; 570 ans[l + i + 1] = sum; 571 } 572 573 for(int k = 1; k <= n; k++) cout << ans[k] << " \n"[k == n]; 574 } 575 576 int main() { 577 int t; 578 cin >> t; 579 while(t--) solve(); 580 } 581 ``` 582 583 **Rate the problem!** 584 585 * Excellent problem 586 * Good problem 587 * Average problem 588 * Bad problem 589 * Horrible problem