1637.md (12854B)
1 Source: https://codeforces.com/blog/entry/99883 2 3 We hope you enjoyed the contest! We recommend you to read all tutorials even if you solve the problem, maybe you will learn something new. 4 5 [1637A - Sorting Parts](/contest/1637/problem/A "Codeforces Global Round 19") 6 Idea: [__JustMe__](/profile/__JustMe__ "Master __JustMe__"). 7 8 **Hint 1** 9 10 What does happen if the array is already sorted? 11 12 **Hint 2** 13 14 What does happen if there are two indexes $i$ and $j$, such that $i \lt j$ and $a_i \gt a_j$? 15 16 **Tutorial** 17 18 Tutorial is loading... 19 20 **Solution** 21 22 ``` 23 #include <bits/stdc++.h> 24 using namespace std; 25 26 int main() { 27 int t; 28 cin >> t; 29 for (int i = 0; i < t; i++) { 30 int n; 31 cin >> n; 32 vector<int> a(n); 33 for (auto& u : a) 34 cin >> u; 35 if (!is_sorted(a.begin(), a.end())) 36 cout << "YES\n"; 37 else 38 cout << "NO\n"; 39 } 40 } 41 ``` 42 43 [1637B - MEX and Array](/contest/1637/problem/B "Codeforces Global Round 19") 44 Idea: [__JustMe__](/profile/__JustMe__ "Master __JustMe__") and [Mangooste](/profile/Mangooste "Grandmaster Mangooste"). 45 46 **Hint 1** 47 48 What does happen after replacing a segment of length greater than $1$ with segments of length $1$? 49 50 **Hint 2** 51 52 The cost of the array $b_1, b_2, \ldots, b_k$ equals to $k + \sum_{i=1}^{k} mex(${$b_i$}$)$. 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution** 59 60 ``` 61 #include <bits/stdc++.h> 62 using namespace std; 63 64 int main() { 65 int t; 66 cin >> t; 67 for (int i = 0; i < t; i++) { 68 int n; 69 cin >> n; 70 vector<int> a(n); 71 for (auto& u : a) 72 cin >> u; 73 74 int ans = 0; 75 for (int i = 0; i < n; i++) { 76 ans += (i + 1) * (n - i); 77 if (a[i] == 0) 78 ans += (i + 1) * (n - i); 79 } 80 cout << ans << '\n'; 81 } 82 } 83 ``` 84 85 [1637C - Andrew and Stones](/contest/1637/problem/C "Codeforces Global Round 19") 86 Idea: [TeaTime](/profile/TeaTime "Master TeaTime"). 87 88 **Hint 1** 89 90 The answer is $-1$ in two cases. If $n = 3$ and $a_2$ is odd. Also if for all $1 \lt i \lt n$: $a_i = 1$. 91 92 **Hint 2** 93 94 It is not optimal to add $1$ to an odd number more than once. 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 106 void solve() { 107 int n; 108 cin >> n; 109 vector<int> a(n); 110 for (auto &x : a) 111 cin >> x; 112 113 if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2 == 1)) { 114 cout << "-1\n"; 115 return; 116 } 117 118 long long answer = 0; 119 for (int i = 1; i < n - 1; i++) 120 answer += (a[i] + 1) / 2; 121 122 cout << answer << '\n'; 123 } 124 125 int main() { 126 ios::sync_with_stdio(false), cin.tie(nullptr); 127 int tests; 128 cin >> tests; 129 while (tests--) 130 solve(); 131 } 132 ``` 133 134 [1637D - Yet Another Minimization Problem](/contest/1637/problem/D "Codeforces Global Round 19") 135 Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste"). 136 137 **Hint 1** 138 139 Try to simplify the array cost formula. 140 141 **Hint 2** 142 143 The total cost of two arrays equals to $(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$. 144 145 **Hint 3** 146 147 Find all possible sums of the array $a$ after some operations. 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution** 154 155 ``` 156 #include <bits/stdc++.h> 157 using namespace std; 158 159 constexpr int MAXSUM = 100 * 100 + 10; 160 161 int sqr(int x) { 162 return x * x; 163 } 164 165 void solve() { 166 int n; 167 cin >> n; 168 vector<int> a(n), b(n); 169 for (auto& u : a) 170 cin >> u; 171 172 for (auto& u : b) 173 cin >> u; 174 175 int sumMin = 0, sumMax = 0, sumSq = 0; 176 for (int i = 0; i < n; i++) { 177 if (a[i] > b[i]) 178 swap(a[i], b[i]); 179 180 sumSq += sqr(a[i]) + sqr(b[i]); 181 sumMin += a[i]; 182 sumMax += b[i]; 183 } 184 185 bitset<MAXSUM> dp; 186 dp[0] = 1; 187 for (int i = 0; i < n; i++) 188 dp |= dp << (b[i] - a[i]); 189 190 int ans = sqr(sumMin) + sqr(sumMax); 191 for (int i = 0; i <= sumMax - sumMin; i++) 192 if (dp[i]) 193 ans = min(ans, sqr(sumMin + i) + sqr(sumMax - i)); 194 195 cout << sumSq * (n - 2) + ans << '\n'; 196 } 197 198 int main() { 199 int t; 200 cin >> t; 201 while (t--) 202 solve(); 203 } 204 ``` 205 206 [1637E - Best Pair](/contest/1637/problem/E "Codeforces Global Round 19") 207 Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste"). 208 209 **Hint 1** 210 211 Fix $x$ and iterate over all $cnt_y \le cnt_x$. It works in $O(n)$ summary. 212 213 **Hint 2** 214 215 When you fix $x$ and $cnt_y$, interate over all $y$ in the non increasing order while $x = y$ or the pair $(x, y)$ is bad. 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution** 222 223 ``` 224 #include <bits/stdc++.h> 225 using namespace std; 226 227 void solve() { 228 int n, m; 229 cin >> n >> m; 230 vector<int> a(n); 231 map<int, int> cnt; 232 for (auto &x : a) { 233 cin >> x; 234 cnt[x]++; 235 } 236 237 vector<pair<int, int>> bad_pairs; 238 bad_pairs.reserve(2 * m); 239 for (int i = 0; i < m; i++) { 240 int x, y; 241 cin >> x >> y; 242 bad_pairs.emplace_back(x, y); 243 bad_pairs.emplace_back(y, x); 244 } 245 sort(bad_pairs.begin(), bad_pairs.end()); 246 247 vector<vector<int>> occ(n); 248 for (auto &[x, c] : cnt) 249 occ[c].push_back(x); 250 251 for (auto &v : occ) 252 reverse(v.begin(), v.end()); 253 254 long long answer = 0; 255 for (int cnt_x = 1; cnt_x < n; cnt_x++) 256 for (int x : occ[cnt_x]) 257 for (int cnt_y = 1; cnt_y <= cnt_x; cnt_y++) 258 for (auto y : occ[cnt_y]) 259 if (x != y && !binary_search(bad_pairs.begin(), bad_pairs.end(), pair<int, int>{x, y})) { 260 answer = max(answer, 1ll * (cnt_x + cnt_y) * (x + y)); 261 break; 262 } 263 264 cout << answer << '\n'; 265 } 266 267 int main() { 268 ios::sync_with_stdio(false), cin.tie(nullptr); 269 int tests; 270 cin >> tests; 271 while (tests--) 272 solve(); 273 } 274 ``` 275 276 [1637F - Towers](/contest/1637/problem/F "Codeforces Global Round 19") 277 Idea: [TeaTime](/profile/TeaTime "Master TeaTime"). 278 279 **Hint 1** 280 281 Find the answer when heights of all vertices are equal to $1$. 282 283 **Hint 2** 284 285 Consider tree where all heights are either $1$ or $0$. What is the answer in this case? 286 287 **Tutorial** 288 289 Tutorial is loading... 290 291 **Solution** 292 293 ``` 294 #include <iostream> 295 #include <vector> 296 #include <algorithm> 297 #include <set> 298 #include <map> 299 300 using namespace std; 301 302 typedef long long ll; 303 304 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 305 306 ll n; 307 vector<vector<ll>> gr; 308 vector<ll> vec; 309 310 void input() { 311 cin >> n; 312 vec.resize(n); 313 for (auto& c : vec) cin >> c; 314 315 gr.resize(n); 316 317 for (int i = 0; i < n - 1; i++) { 318 ll u, v; 319 cin >> u >> v; 320 u--; v--; 321 gr[u].push_back(v); 322 gr[v].push_back(u); 323 } 324 } 325 326 ll sol() { 327 ll ans = 0; 328 329 set<pair<ll, ll>> leaves; 330 vector<pair<ll, ll>> srt; 331 vector<ll> degree(n); 332 333 srt.push_back({ 0, -1 }); 334 for (int i = 0; i < n; i++) { 335 degree[i] = gr[i].size(); 336 337 srt.push_back({ vec[i], i }); 338 if (gr[i].size() == 1) { 339 leaves.insert({vec[i], i}); 340 } 341 } 342 343 sort(srt.begin(), srt.end()); 344 345 for (int i = 1; i <= n; i++) { 346 while (leaves.size() > 0 && (*leaves.begin()).first < srt[i].first) { 347 ll v = (*leaves.begin()).second; 348 degree[v] = -2; 349 leaves.erase(leaves.begin()); 350 351 for (auto to : gr[v]) { 352 degree[to]--; 353 if (degree[to] == 1 || degree[to] == 0) leaves.insert({ vec[to], to }); 354 } 355 } 356 357 ans += max(2ll, ll(leaves.size())) * (srt[i].first - srt[i - 1].first); 358 } 359 360 return ans; 361 } 362 363 int main() { 364 fastInp; 365 366 input(); 367 cout << sol(); 368 369 return 0; 370 } 371 ``` 372 373 **Alternative solution** 374 375 ``` 376 #include <bits/stdc++.h> 377 using namespace std; 378 379 typedef long long ll; 380 381 int main() { 382 ios_base::sync_with_stdio(false); cin.tie(0); 383 int n; 384 cin >> n; 385 vector<int> h(n); 386 for (int i = 0; i < n; ++i) cin >> h[i]; 387 vector<vector<int>> g(n); 388 for (int i = 0; i + 1 < n; ++i) { 389 int u, v; 390 cin >> u >> v; 391 --u, --v; 392 g[u].push_back(v); 393 g[v].push_back(u); 394 } 395 int rt = 0; 396 for (int i = 0; i < n; ++i) { 397 if (h[i] > h[rt]) { 398 rt = i; 399 } 400 } 401 ll ans = 0; 402 function<int(int, int)> dfs = [&](int u, int p) { 403 int mx1 = 0, mx2 = 0; 404 vector<int> have; 405 for (auto v : g[u]) { 406 if (v != p) { 407 int cur = dfs(v, u); 408 if (cur > mx1) swap(cur, mx1); 409 if (cur > mx2) swap(cur, mx2); 410 } 411 } 412 if (p != -1) { 413 int delta = max(0, h[u] - mx1); 414 ans += delta; 415 mx1 += delta; 416 } else { 417 ans += max(0, h[u] - mx1) + max(0, h[u] - mx2); 418 } 419 return mx1; 420 }; 421 dfs(rt, -1); 422 cout << ans << '\n'; 423 } 424 ``` 425 426 [1637G - Birthday](/contest/1637/problem/G "Codeforces Global Round 19") 427 Idea: [EvgeniyPonasenkov](/profile/EvgeniyPonasenkov "Master EvgeniyPonasenkov"). 428 429 **Hint 1** 430 431 It's impossible to construct a sequence of operations only when $n = 2$. 432 433 **Hint 2** 434 435 Answer is the smallest power of two which is at least $n$. 436 437 **Hint 3** 438 439 Try to transform all numbers into the powers of two (maybe different). 440 441 **Tutorial** 442 443 Tutorial is loading... 444 445 **Solution** 446 447 ``` 448 #include <bits/stdc++.h> 449 using namespace std; 450 451 vector<pair<int, int>> ops; 452 vector<int> a; 453 454 void rec(int n, int coeff) { 455 if (n <= 2) { 456 for (int i = 1; i <= n; i++) 457 a.push_back(i * coeff); 458 return; 459 } 460 461 int p = 1; 462 while (p * 2 <= n) p *= 2; 463 464 if (p == n) { 465 a.push_back(n * coeff); 466 n--, p /= 2; 467 } 468 469 a.push_back(p * coeff); 470 for (int i = p + 1; i <= n; i++) { 471 a.push_back(2 * p * coeff); 472 ops.emplace_back(i * coeff, (2 * p - i) * coeff); 473 } 474 475 rec(2 * p - n - 1, coeff); 476 rec(n - p, coeff * 2); 477 } 478 479 void solve() { 480 int n; 481 cin >> n; 482 if (n == 2) { 483 cout << "-1\n"; 484 return; 485 } 486 487 ops.clear(); 488 a.clear(); 489 rec(n, 1); 490 sort(a.begin(), a.end()); 491 492 int answer = 1; 493 while (answer < n) 494 answer *= 2; 495 496 for (int i = 0;; i++) 497 if (a[i] == a[i + 1]) { 498 assert(a[i] != answer); 499 ops.emplace_back(a[i], a[i]); 500 a[i + 1] *= 2; 501 a.erase(a.begin() + i); 502 break; 503 } 504 505 for (auto x : a) 506 while (x != answer) { 507 ops.emplace_back(0, x); 508 ops.emplace_back(x, x); 509 x *= 2; 510 } 511 512 ops.emplace_back(0, answer); 513 cout << ops.size() << '\n'; 514 for (auto &[x, y] : ops) 515 cout << x << ' ' << y << '\n'; 516 } 517 518 int main() { 519 int tests; 520 cin >> tests; 521 while (tests--) 522 solve(); 523 } 524 ``` 525 526 [1637H - Minimize Inversions Number](/contest/1637/problem/H "Codeforces Global Round 19") 527 Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste"). 528 529 **Hint 1** 530 531 We have a proof that for each length, in the optimal sequence the following condition is satisfied: if the element $i$ is selected, then all elements $j \gt i$ and $p_j \lt p_i$ are also selected. 532 533 **Hint 2** 534 535 Let $d_i$ is a number by which the number of inversions will decrease after moving only the element with index $i$ to the beginning. Then, if sequence $seq$ is selected, then the number of inversions in a new permutation will be equal to $invs - \sum_{i \in seq} d_i + seqInvs - (\frac{|seq| \cdot (|seq| - 1)}{2} - seqInvs) = invs - \sum_{i \in seq} d_i + 2 \cdot seqInvs - \frac{|seq| \cdot (|seq| - 1)}{2}$. Here $invs$ — the number of inversions in the initial permutation, and $seqInvs$ — the number of inversions over all elements in the $seq$. 536 537 **Hint 3** 538 539 Assume that the number of inversions equals to $invs - \sum_{i \in seq} c_i - \frac{|seq| \cdot (|seq| - 1)}{2}$. What is $c_i$? 540 541 **Hint 4** 542 543 If $i \gt j$ and $p_i \gt p_j$ then $c_i \lt c_j$. So for the length $len$ it's optimal to choose $len$ maxmum elements by the value of $c_i$. 544 545 **Tutorial** 546 547 Tutorial is loading... 548 549 **Solution** 550 551 ``` 552 #include <bits/stdc++.h> 553 using namespace std; 554 555 struct binary_index_tree { 556 int n; 557 vector<int> bit; 558 559 binary_index_tree(int n) : n(n), bit(n + 1) {} 560 561 void increase(int pos) { 562 for (pos++; pos <= n; pos += pos & -pos) 563 bit[pos]++; 564 } 565 566 int query(int pref) const { 567 int sum = 0; 568 for (; pref; pref -= pref & -pref) 569 sum += bit[pref]; 570 571 return sum; 572 } 573 }; 574 575 void solve() { 576 int n; 577 cin >> n; 578 579 vector<int> d(n); 580 binary_index_tree bit(n); 581 long long inversions = 0; 582 583 for (int i = 0; i < n; i++) { 584 int p; 585 cin >> p; 586 p--; 587 588 d[i] = i - 2 * p; 589 inversions += i - bit.query(p); 590 bit.increase(p); 591 } 592 sort(d.rbegin(), d.rend()); 593 594 cout << inversions; 595 long long sum = 0; 596 for (int i = 0; i < n; i++) { 597 sum += d[i]; 598 cout << ' ' << inversions - sum - 1ll * i * (i + 1) / 2; 599 } 600 601 cout << '\n'; 602 } 603 604 int main() { 605 ios::sync_with_stdio(false), cin.tie(nullptr); 606 607 int tests; 608 cin >> tests; 609 while (tests--) 610 solve(); 611 } 612 ```