2252.md (21541B)
1 Source: https://codeforces.com/blog/entry/155741 2 3 Thank you for participating in Codeforces Round 1115 (Div. 2)! We hope you enjoyed the problems. 4 5 The round was prepared by [Bufu](/profile/Bufu "Candidate Master Bufu") and [TomitaMatei](/profile/TomitaMatei "Master TomitaMatei"), and coordinated by [cry](/profile/cry "International Master cry"). 6 7 --- 8 9 #### [2252A - Boss Fight](/contest/2252/problem/A "Codeforces Round 1115 (Div. 2)") 10 11 **Solution** 12 13 The boss's shield permanently activates and blocks all subsequent damage only when two cards of the exact same value are played back-to-back. Importantly, the card that actually triggers the shield still deals its normal damage. 14 15 This means we want to play as many cards as possible *before* being forced to place two identical cards adjacent to each other. We should only do this on the very last card we play. 16 17 Let the most frequent card in our hand have a damage value of $X$, and let its frequency be $F$. Let the number of all *other* cards be $O = n - F$. 18 19 To maximize the number of $X$ cards we can play, we must use the $O$ "other" cards as separators. By placing an "other" card between every $X$ card, we can form an alternating sequence like this: 20 21 $X, \text{other}_1, X, \text{other}_2, \ldots, X, \text{other}_O, X$ 22 23 This allows us to safely play $O + 1$ copies of $X$ without triggering the shield. 24 25 Finally, to squeeze out the maximum possible damage, we can play exactly one more $X$ card at the very end of this sequence: 26 27 $X, \text{other}_1, X, \text{other}_2, \ldots, X, \text{other}_O, X, \mathbf{X}$ 28 29 This final $X$ triggers the shield, but it still deals its normal damage. All remaining cards in our hand will deal $0$, but that doesn't matter because we have already used all of our "other" cards. 30 31 Thus, the maximum number of $X$ cards we can successfully play is $(O + 1) + 1 = O + 2$. Of course, if $F \lt O + 2$, we simply play all $F$ of our $X$ cards without any issues. 32 33 The maximum number of majority cards we can play is $\min(F, O + 2)$. Since we always play every single "other" card, the maximum total damage is: 34 35 $\text{Sum of all "other" cards} + X \cdot \min(F, O + 2)$ 36 37 **Time complexity:** $\mathcal{O}(n)$. 38 39 **Code (C++)** 40 41 ``` 42 #include <iostream> 43 #include <vector> 44 #include <map> 45 #include <algorithm> 46 47 using namespace std; 48 49 void solve() { 50 int n; 51 cin >> n; 52 long long total_sum = 0; 53 map<int, int> freq; 54 55 int max_f = 0; 56 int maj_val = 0; 57 58 for (int i = 0; i < n; i++) { 59 int x; 60 cin >> x; 61 total_sum += x; 62 freq[x]++; 63 if (freq[x] > max_f) { 64 max_f = freq[x]; 65 maj_val = x; 66 } 67 } 68 69 int others = n - max_f; 70 71 int max_majority_played = min(max_f, others + 2); 72 73 long long ans = (total_sum - 1LL * max_f * maj_val) + 1LL * max_majority_played * maj_val; 74 cout << ans << "\n"; 75 } 76 77 int main() { 78 ios_base::sync_with_stdio(false); 79 cin.tie(NULL); 80 int t; cin >> t; 81 while(t--) { 82 solve(); 83 } 84 return 0; 85 } 86 ``` 87 88 --- 89 90 #### [2252B - Always Changing](/contest/2252/problem/B "Codeforces Round 1115 (Div. 2)") 91 92 **Solution** 93 94 Let $n_0$ and $n_1$ be the number of `0`s and `1`s in the initial string. Let $k_0$ and $k_1$ be the number of `0`s and `1`s in the final alternating string. Let $c_0$ and $c_1$ be the number of `0`s and `1`s we deleted. 95 96 Because our deletions must strictly alternate, the difference between the number of deleted `0`s and `1`s can be at most $1$. Thus, $|c_0 - c_1| \le 1$. We know that $c_0 = n_0 - k_0$ and $c_1 = n_1 - k_1$. 97 98 Let $\Delta n = n_0 - n_1$ and $\Delta k = k_0 - k_1$. Substituting our equations, the condition $|c_0 - c_1| \le 1$ translates to: 99 100 $|\Delta n - \Delta k| \le 1$ 101 102 Since the final string is strictly alternating, $\Delta k$ can only be $-1$, $0$, or $1$. This means that if $|\Delta n| \gt 2$, it is mathematically impossible to satisfy the inequality, and we should output $-1$. 103 104 If it is possible ($|\Delta n| \le 2$), we want to maximize the length of our final string (which minimizes deletions). We can first greedily "compress" the initial string by removing all adjacent duplicate characters (e.g., `00011001` becomes `0101`). Let the length of this compressed alternating string be $L$, and let $\Delta L$ be the difference between the number of `0`s and `1`s in it. 105 106 To ensure our sequence of deletions is valid, we must satisfy the condition $|\Delta n - \Delta k| \le 1$, meaning our final $\Delta k$ must be in the range $[\Delta n - 1, \Delta n + 1]$. We can safely remove any number of characters from the *beginning* or the *end* of our compressed alternating string, and it will remain alternating. Each character we remove shifts $\Delta L$ by exactly $+1$ or $-1$. 107 108 Thus, to fix the parity and enter the valid range, the minimum number of characters we must drop from the ends of our compressed string is exactly the mathematical distance from $\Delta L$ to the range $[\Delta n - 1, \Delta n + 1]$. This distance is exactly $\max(0, |\Delta n - \Delta L| - 1)$. 109 110 The total number of deleted characters is the number of characters removed during compression $(n - L)$, plus the characters removed from the ends to fix the parity. Final answer: $(n - L) + \max(0, |\Delta n - \Delta L| - 1)$. 111 112 **Time complexity:** $\mathcal{O}(n)$. 113 114 **Code (C++)** 115 116 ``` 117 #include <iostream> 118 #include <string> 119 #include <cmath> 120 #include <algorithm> 121 122 using namespace std; 123 124 void solve() { 125 int n; cin >> n; 126 string s; cin >> s; 127 128 int n0 = 0, n1 = 0; 129 for (char c : s) { 130 if (c == '0') n0++; 131 else n1++; 132 } 133 134 int delta_n = n0 - n1; 135 if (abs(delta_n) > 2) { 136 cout << -1 << "\n"; 137 return; 138 } 139 140 int L = 1; 141 int L0 = (s[0] == '0' ? 1 : 0); 142 int L1 = (s[0] == '1' ? 1 : 0); 143 144 for (int i = 1; i < n; i++) { 145 if (s[i] != s[i - 1]) { 146 L++; 147 if (s[i] == '0') L0++; 148 else L1++; 149 } 150 } 151 152 int delta_L = L0 - L1; 153 int ans = (n - L) + max(0, abs(delta_n - delta_L) - 1); 154 cout << ans << "\n"; 155 } 156 157 int main() { 158 ios_base::sync_with_stdio(false); 159 cin.tie(NULL); 160 161 int t; cin >> t; 162 while(t--) { 163 solve(); 164 } 165 166 return 0; 167 } 168 ``` 169 170 --- 171 172 #### [2252C - Risky Tower](/contest/2252/problem/C "Codeforces Round 1115 (Div. 2)") 173 174 **Solution** 175 176 The tower collapses if all $m$ pieces of any single level are removed. This guarantees that the answer is at most $m$. 177 178 Let's write the condition to collapse a specific row $k$ via damage. The sum of destabilization factors of the removed pieces from rows $i \ge k$ must satisfy: 179 180 $\sum a_{i,j} \ge v_k$ 181 182 To satisfy this inequality using the minimum number of pieces, we must greedily select pieces with the largest $a_{i,j}$ from rows at and below $k$. 183 184 Since the answer will never exceed $m$, we only need to keep track of at most $m$ pieces at any time. We can process the grid from the bottom row ($n$) to the top row ($1$), maintaining a priority queue or sorted list of the largest $m$ destabilization factors $a_{i,j}$ seen so far. 185 186 At each row $k$, we insert its $m$ pieces into our active pool, discard all but the largest $m$ elements overall, and find the minimum number of largest elements that sum to at least $v_k$. The minimum number of pieces required across all rows $k$, bounded by $m$, is our answer. 187 188 **Time complexity:** $\mathcal{O}(n \cdot m \log m)$ 189 190 **Code (C++)** 191 192 ``` 193 #include <iostream> 194 #include <vector> 195 #include <algorithm> 196 197 using namespace std; 198 199 void solve() { 200 int n, m; 201 cin >> n >> m; 202 vector<long long> v(n + 1); 203 for(int i = 1; i <= n; i++) cin >> v[i]; 204 205 vector<vector<long long>> a(n + 1, vector<long long>(m)); 206 for(int i = 1; i <= n; i++) { 207 for(int j = 0; j < m; j++) { 208 cin >> a[i][j]; 209 } 210 } 211 212 int min_ans = m; 213 vector<long long> best; 214 215 for(int k = n; k >= 1; k--) { 216 for(int j = 0; j < m; j++) { 217 best.push_back(a[k][j]); 218 } 219 220 sort(best.rbegin(), best.rend()); 221 222 if ((int)best.size() > m) { 223 best.resize(m); 224 } 225 226 long long current_sum = 0; 227 int pieces = 0; 228 229 for(long long val : best) { 230 current_sum += val; 231 pieces++; 232 if (current_sum >= v[k]) { 233 min_ans = min(min_ans, pieces); 234 break; 235 } 236 } 237 } 238 239 cout << min_ans << "\n"; 240 } 241 242 int main() { 243 ios_base::sync_with_stdio(false); 244 cin.tie(NULL); 245 int t; cin >> t; 246 while(t--) { 247 solve(); 248 } 249 return 0; 250 } 251 ``` 252 253 --- 254 255 #### [2252D - Array Replacement](/contest/2252/problem/D "Codeforces Round 1115 (Div. 2)") 256 257 **Solution** 258 259 Let's consider the difference array $d$, where $d_i = a_{i+1} - a_i$ for all $1 \le i \lt n$. 260 261 Consider what happens to the array $a$ when we perform an operation on index $i$. The triplet $(a_{i-1}, a_i, a_{i+1})$ becomes $(a_{i-1}, a_{i-1} - a_i + a_{i+1}, a_{i+1})$. Let's see how this affects our difference array $d$: 262 263 * The new $d_{i-1}$ becomes $(a_{i-1} - a_i + a_{i+1}) - a_{i-1} = a_{i+1} - a_i$, which is exactly the old $d_i$. 264 * The new $d_i$ becomes $a_{i+1} - (a_{i-1} - a_i + a_{i+1}) = a_i - a_{i-1}$, which is exactly the old $d_{i-1}$. 265 266 Thus, performing the operation on index $i$ is exactly equivalent to **swapping** $d_{i-1}$ and $d_i$! 267 268 However, we can only perform this operation if $a_{i-1}$ and $a_{i+1}$ have the same parity. Notice that $a_{i+1} - a_{i-1} = (a_{i+1} - a_i) + (a_i - a_{i-1}) = d_i + d_{i-1}$. For $a_{i-1}$ and $a_{i+1}$ to have the same parity, their difference $d_i + d_{i-1}$ must be an even number. The sum of two integers is even if and only if they have the **same parity**. 269 270 Therefore, the condition that $a_{i-1}$ and $a_{i+1}$ have the same parity is equivalent to saying $d_{i-1}$ and $d_i$ have the same parity. 271 272 This means we can swap any two adjacent elements in the difference array $d$ as long as they share the same parity. This allows us to independently sort any contiguous subsegment of $d$ that consists entirely of even numbers, or entirely of odd numbers. 273 274 To construct the lexicographically smallest array $a$, we simply group contiguous elements of $d$ that share the same parity, sort each group in non-decreasing order, and then reconstruct the array $a$ starting from $a_1$. 275 276 **Time complexity:** $\mathcal{O}(n \log n)$. 277 278 **Code (C++)** 279 280 ``` 281 #include <iostream> 282 #include <vector> 283 #include <algorithm> 284 #include <cmath> 285 286 using namespace std; 287 288 void solve() { 289 int n; 290 cin >> n; 291 vector<long long> a(n); 292 for (int i = 0; i < n; i++) { 293 cin >> a[i]; 294 } 295 296 vector<long long> d(n - 1); 297 for (int i = 0; i < n - 1; i++) { 298 d[i] = a[i + 1] - a[i]; 299 } 300 301 for (int i = 0; i < n - 1; ) { 302 int j = i; 303 while (j < n - 1 && (d[j] & 1) == (d[i] & 1)) { 304 j++; 305 } 306 sort(d.begin() + i, d.begin() + j); 307 i = j; 308 } 309 310 cout << a[0] << " "; 311 long long cur = a[0]; 312 for (int i = 0; i < n - 1; i++) { 313 cur += d[i]; 314 cout << cur << " "; 315 } 316 cout << "\n"; 317 } 318 319 int main() { 320 ios_base::sync_with_stdio(false); 321 cin.tie(NULL); 322 int t; cin >> t; 323 while(t--) { 324 solve(); 325 } 326 return 0; 327 } 328 ``` 329 330 --- 331 332 #### [2252E - Generational Triplets](/contest/2252/problem/E "Codeforces Round 1115 (Div. 2)") 333 334 **Solution** 335 336 From the arithmetic progression condition, 337 338 $2b = a + c.$ 339 340 From the XOR condition, 341 342 $b = a \oplus c.$ 343 344 Substituting the second equation into the first gives 345 346 $2(a \oplus c) = a + c.$ 347 348 Let $x$ be the bitwise AND of $a$ and $c$, i.e. `x = a&c`. Recall the standard bitwise addition identity 349 350 $a + c = (a \oplus c) + 2x.$ 351 352 Therefore, 353 354 $a \oplus c = 2x.$ 355 356 Equivalently, in bitwise notation, `a^c = 2(a&c)`. 357 358 Thus, it is enough to count pairs $(a,c)$ such that $a \lt c \le n$ and `a^c = 2(a&c)`. 359 360 For every such pair, $b$ is uniquely determined as $a \oplus c$. Also, $a \lt b \lt c$ follows from the two original conditions. We only need to enforce $a \lt c$: if $a=c$, then the equation becomes $0=2a$, which is impossible because $a \ge 1$. 361 362 We solve this with digit DP, processing bits from $60$ down to $0$. Let the state be 363 364 $\mathrm{dp}[\mathrm{bit}][\mathrm{cLess}][\mathrm{aLess}][\mathrm{need}].$ 365 366 * `bit`: the bit currently being processed. 367 * `cLess`: whether the already processed prefix of $c$ is strictly smaller than the corresponding prefix of $n$. 368 * `aLess`: whether the already processed prefix of $a$ is strictly smaller than the corresponding prefix of $c$. 369 * `need`: the value required for the current bit of `a&c`, determined by the XOR value at the previous, more significant bit. 370 371 At each state, try all four choices for the current bits of $a$ and $c$. A transition is valid when: 372 373 1. The chosen prefix of $c$ does not exceed the prefix of $n$. 374 2. The chosen prefix of $a$ does not exceed the prefix of $c$. 375 3. The current bit of `a&c` equals `need`. 376 377 For the next lower bit, the new value of `need` is the XOR of the current bits of $a$ and $c$. This represents the one-bit left shift in `a^c = 2(a&c)`. 378 379 After processing all bits, the state contributes $1$ exactly when `need` is $0$ and `aLess` is true, which guarantees $a \lt c$. 380 381 **Time complexity:** $\mathcal{O}(\log n)$ per test case. 382 383 **Code (C++)** 384 385 ``` 386 #include <iostream> 387 #include <vector> 388 #include <cstring> 389 390 using namespace std; 391 392 long long dp[65][2][2][2]; 393 long long n; 394 395 const int MOD = 1000000007; 396 397 long long solve_dp(int bit, int c_less, int a_less, int need) { 398 if (bit < 0) { 399 if (need == 0 && a_less == 1) return 1; 400 return 0; 401 } 402 403 if (dp[bit][c_less][a_less][need] != -1) { 404 return dp[bit][c_less][a_less][need]; 405 } 406 407 long long ans = 0; 408 int n_bit = (n >> bit) & 1; 409 410 for (int a_bit = 0; a_bit <= 1; a_bit++) { 411 for (int c_bit = 0; c_bit <= 1; c_bit++) { 412 // Check constraint against n 413 if (c_less && c_bit > n_bit) continue; 414 415 // Check constraint a <= c (since we need a < c eventually) 416 if (!a_less && a_bit > c_bit) continue; 417 418 // Check the "need" condition for (a & c) 419 if (need == 1 && (a_bit & c_bit) == 0) continue; 420 if (need == 0 && (a_bit & c_bit) == 1) continue; 421 422 int next_c_less = c_less && (c_bit == n_bit); 423 int next_a_less = a_less || (a_bit < c_bit); 424 int next_need = a_bit ^ c_bit; // The next bit's & must match this bit's ^ 425 426 ans = (ans + solve_dp(bit - 1, next_c_less, next_a_less, next_need)) % MOD; 427 } 428 } 429 430 return dp[bit][c_less][a_less][need] = ans; 431 } 432 433 void solve() { 434 cin >> n; 435 memset(dp, -1, sizeof(dp)); 436 // Start at bit 60, c is constrained by n, a is not yet less than c, need = 0 437 cout << solve_dp(60, 1, 0, 0) << "\n"; 438 } 439 440 int main() { 441 ios_base::sync_with_stdio(false); 442 cin.tie(NULL); 443 int t; cin >> t; 444 while(t--) { 445 solve(); 446 } 447 return 0; 448 } 449 ``` 450 451 --- 452 453 #### [2252F - Spectral Components](/contest/2252/problem/F "Codeforces Round 1115 (Div. 2)") 454 455 **Solution** 456 457 Let's solve the problem independently for a single color $c$ with $M$ vertices. 458 459 First, consider the case where $k = 1$. The optimal component is a single vertex, which mathematically corresponds to the **centroid** of the $M$ vertices. For any edge $e$ in the tree, let $m_{\mathrm{in}}[e]$ and $m_{\mathrm{out}}[e]$ be the number of color $c$ vertices on either side of the edge. The number of paths from color $c$ vertices that must cross edge $e$ to reach the centroid is exactly $w[e] = \min(m_{\mathrm{in}}[e], m_{\mathrm{out}}[e])$. Thus, the total distance to the centroid is: 460 461 $D(\mathrm{centroid}) = \sum w[e]$ 462 463 where the sum is over all edges $e$ in the tree. 464 465 When $k \gt 1$, we must choose a connected component $S$ of $k$ vertices (which contains exactly $k - 1$ edges). Notice that if an edge $e$ is entirely inside $S$, no path from any colored vertex to $S$ needs to cross it (the distance is absorbed into the component). If an edge is outside $S$, exactly $w[e]$ paths still cross it. Thus, the cost of any valid component $S$ containing the centroid is: 466 467 $\mathrm{Cost}(S) = D(\mathrm{centroid}) - \sum_{e \in S} w[e]$ 468 469 To minimize $\mathrm{Cost}(S)$, we must **maximize** the sum of $w[e]$ for the $k - 1$ edges we pick. A crucial property of tree centroids is that $w[e]$ is monotonically decreasing as you move away from the centroid. Because of this monotonicity, if we simply greedily pick the $k - 1$ edges with the globally maximum $w[e]$ values in the entire tree, they are mathematically guaranteed to form a connected component containing the centroid! 470 471 However, calculating this naively for all colors takes $\mathcal{O}(N^2)$. To achieve the required time complexity, we process all colors using **Virtual Trees** (also known as Auxiliary Trees): 472 473 1. For each color $c$, build a Virtual Tree of its $M$ vertices in $\mathcal{O}(M \log M)$ time using LCA. 474 2. Run a bottom-up DP on the Virtual Tree to find $m_{\mathrm{in}}$ for each virtual subtree. 475 3. A virtual edge $(u, v)$ represents a compressed path of $L = \operatorname{depth}[v] - \operatorname{depth}[u]$ real edges. Because there are no other vertices of color $c$ branching off this path, every single real edge on this path shares the exact same weight: $w' = \min(m_{\mathrm{in}}, m_c - m_{\mathrm{in}})$. 476 4. For color $c$, collect the pairs (weight = $w'$, count = $L$) for all virtual edges. 477 5. Sort these pairs by weight descending, and greedily pick up to $K - 1$ edges to subtract from the total sum of all $w[e]$. 478 479 Since the sum of sizes of all Virtual Trees over all colors is $\mathcal{O}(n)$, the overall time complexity is $\mathcal{O}(n \log n)$. 480 481 **Code (C++)** 482 483 ``` 484 #include <iostream> 485 #include <vector> 486 #include <algorithm> 487 488 using namespace std; 489 490 const int LOG = 19; 491 int n; 492 vector<int> C, K; 493 vector<vector<int>> adj; 494 vector<int> tin, tout, depth; 495 vector<vector<int>> up; 496 int timer = 0; 497 498 void dfs(int v, int p, int d) { 499 tin[v] = ++timer; 500 depth[v] = d; 501 up[v][0] = p; 502 for (int i = 1; i < LOG; i++) { 503 up[v][i] = up[up[v][i - 1]][i - 1]; 504 } 505 for (int u : adj[v]) { 506 if (u != p) dfs(u, v, d + 1); 507 } 508 tout[v] = ++timer; 509 } 510 511 bool is_ancestor(int u, int v) { 512 return tin[u] <= tin[v] && tout[u] >= tout[v]; 513 } 514 515 int get_lca(int u, int v) { 516 if (is_ancestor(u, v)) return u; 517 if (is_ancestor(v, u)) return v; 518 for (int i = LOG - 1; i >= 0; i--) { 519 if (!is_ancestor(up[u][i], v)) u = up[u][i]; 520 } 521 return up[u][0]; 522 } 523 524 void solve() { 525 cin >> n; 526 C.assign(n + 1, 0); 527 K.assign(n + 1, 0); 528 adj.assign(n + 1, vector<int>()); 529 tin.assign(n + 1, 0); 530 tout.assign(n + 1, 0); 531 depth.assign(n + 1, 0); 532 up.assign(n + 1, vector<int>(LOG, 1)); 533 timer = 0; 534 535 vector<vector<int>> colors(n + 1); 536 for (int i = 1; i <= n; i++) { 537 cin >> C[i]; 538 colors[C[i]].push_back(i); 539 } 540 for (int i = 1; i <= n; i++) cin >> K[i]; 541 542 for (int i = 0; i < n - 1; i++) { 543 int u, v; 544 cin >> u >> v; 545 adj[u].push_back(v); 546 adj[v].push_back(u); 547 } 548 549 dfs(1, 1, 0); 550 551 vector<long long> ans(n + 1, -1); 552 vector<int> cnt(n + 1, 0); 553 554 for (int c = 1; c <= n; c++) { 555 if (colors[c].empty()) continue; 556 557 int M_c = colors[c].size(); 558 int K_c = K[c]; 559 560 vector<int> nodes = colors[c]; 561 sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; }); 562 563 int sz = nodes.size(); 564 for (int i = 0; i < sz - 1; i++) { 565 nodes.push_back(get_lca(nodes[i], nodes[i+1])); 566 } 567 568 sort(nodes.begin(), nodes.end(), [](int a, int b) { return tin[a] < tin[b]; }); 569 nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end()); 570 571 for (int u : colors[c]) cnt[u] = 1; 572 573 vector<int> st; 574 vector<pair<int, int>> vt_edges; 575 for (int u : nodes) { 576 while (!st.empty() && !is_ancestor(st.back(), u)) st.pop_back(); 577 if (!st.empty()) vt_edges.push_back({st.back(), u}); 578 st.push_back(u); 579 } 580 581 long long total_dist = 0; 582 vector<pair<long long, long long>> edge_weights; // {weight, count} 583 584 for (int i = (int)vt_edges.size() - 1; i >= 0; i--) { 585 int p = vt_edges[i].first; 586 int u = vt_edges[i].second; 587 cnt[p] += cnt[u]; 588 589 long long w = min((long long)cnt[u], (long long)M_c - cnt[u]); 590 long long L = depth[u] - depth[p]; 591 total_dist += w * L; 592 edge_weights.push_back({w, L}); 593 } 594 595 sort(edge_weights.rbegin(), edge_weights.rend()); 596 597 long long saved = 0; 598 long long needed = K_c - 1; 599 for (auto& ew : edge_weights) { 600 long long take = min(needed, ew.second); 601 saved += take * ew.first; 602 needed -= take; 603 if (needed == 0) break; 604 } 605 606 ans[c] = total_dist - saved; 607 for (int u : nodes) cnt[u] = 0; 608 } 609 610 for (int i = 1; i <= n; i++) { 611 cout << ans[i] << (i == n ? "" : " "); 612 } 613 cout << "\n"; 614 } 615 616 int main() { 617 ios_base::sync_with_stdio(false); 618 cin.tie(NULL); 619 int t; cin >> t; 620 while(t--) { 621 solve(); 622 } 623 return 0; 624 } 625 ```