2259.md (13137B)
1 Source: https://codeforces.com/blog/entry/156457 2 3 Thank y'all so much for participating! 4 5 [2259A - Школа языка Му](/contest/2259/problem/A "Codeforces Round 1119 (Div. 3)") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 int t; 19 cin >> t; 20 21 while (t--) { 22 int n, k; 23 cin >> n >> k; 24 25 string s; 26 cin >> s; 27 28 int ans = 0; 29 for (int i = 0; i < n / k; i++) { 30 bool has_non_nhoj_farm = false; 31 for (int j = i * k; j < (i + 1) * k; j++) { 32 if (s[j] == '0') has_non_nhoj_farm = true; 33 } 34 ans += !has_non_nhoj_farm; 35 } 36 37 cout << ans << "\n"; 38 } 39 } 40 ``` 41 42 **Difficulty** 43 44 Too hard 45 46 A bit on the harder side 47 48 Good difficulty 49 50 Easy 51 52 Too easy 53 54 **Quality** 55 56 Amazing 57 58 Good 59 60 So-so 61 62 Bad 63 64 Awful 65 66 [2259B - Minus Two](/contest/2259/problem/B "Codeforces Round 1119 (Div. 3)") 67 68 **Hint 1** 69 70 When comparing two numbers that are initially not equal, the only way they can become equal after some number of operations is if at least one of them has an operation performed on it when it is $ \lt 2$. 71 72 **Hint 2** 73 74 If two elements are equal at some point, they'll be equal no matter how many more operations are performed. Therefore, it suffices to look at the end behavior of each element. 75 76 **Solution** 77 78 Tutorial is loading... 79 80 **Code** 81 82 ``` 83 #include <bits/stdc++.h> 84 using namespace std; 85 86 int main() { 87 int t; 88 cin >> t; 89 90 while (t--) { 91 int n; 92 cin >> n; 93 94 vector<int> vec(n); for (auto &x: vec) cin >> x; 95 96 int mod_4[] {0, 0, 0, 0}; 97 for (auto &x: vec) mod_4[x%4]++; 98 cout << max({mod_4[0], mod_4[2], mod_4[1] + mod_4[3]}) << "\n"; 99 } 100 } 101 ``` 102 103 **Difficulty** 104 105 Too hard 106 107 A bit on the harder side 108 109 Good difficulty 110 111 Easy 112 113 Too easy 114 115 **Quality** 116 117 Amazing 118 119 Good 120 121 So-so 122 123 Bad 124 125 Awful 126 127 [2259C - 101](/contest/2259/problem/C "Codeforces Round 1119 (Div. 3)") 128 129 **Hint 1** 130 131 If a $-1$ is in between two $1$s, it would only hurt the answer to make it a $1$. 132 133 **Hint 2** 134 135 If a $-1$ is not in between two $1$ s, the $-1$ would only be included in a subarray satisfying the conditions if it was an endpoint. 136 137 **Solution** 138 139 Tutorial is loading... 140 141 **Code** 142 143 ``` 144 #include <bits/stdc++.h> 145 using namespace std; 146 147 int main() { 148 int t; 149 cin >> t; 150 151 while (t--) { 152 int n; 153 cin >> n; 154 155 vector<int> vec(n); for (auto &x: vec) cin >> x; 156 157 for (int i = 0; i < n; i++) { 158 if (vec[i] == -1) vec[i] = 1; 159 if (vec[i] == 1) break; 160 } 161 162 for (int i = n-1; i >= 0; i--) { 163 if (vec[i] == -1) vec[i] = 1; 164 if (vec[i] == 1) break; 165 } 166 167 168 for (auto &x: vec) cout << max(x, 0) << " "; 169 cout << "\n"; 170 } 171 } 172 ``` 173 174 **Difficulty** 175 176 Too hard 177 178 A bit on the harder side 179 180 Good difficulty 181 182 Easy 183 184 Too easy 185 186 **Quality** 187 188 Amazing 189 190 Good 191 192 So-so 193 194 Bad 195 196 Awful 197 198 [2259D - MEX мультимножеств](/contest/2259/problem/D "Codeforces Round 1119 (Div. 3)") 199 200 **Hint 1** 201 202 If there is only one $0$ in the array, then exactly one set will have a mex greater than zero 203 204 **Hint 2** 205 206 $MEX(A) = MEX(B), MEX(C) = 0$ satisfies the constraints. 207 208 **Solution** 209 210 Tutorial is loading... 211 212 **Code** 213 214 ``` 215 #include <bits/stdc++.h> 216 using namespace std; 217 218 int main() { 219 int t; 220 cin >> t; 221 222 while (t--) { 223 int n; 224 cin >> n; 225 226 vector<int> vec(n); for (auto &x: vec) cin >> x; 227 if (count(vec.begin(), vec.end(), 0) == 1) { 228 cout << "NO\n"; 229 continue; 230 } 231 cout << "YES\n"; 232 bool seen_zero = false; 233 for (int i = 0; i < n; i++) { 234 if (vec[i] != 0) cout << 'A'; 235 else if (seen_zero) cout << 'B'; 236 else { 237 seen_zero = true; 238 cout << 'C'; 239 } 240 } 241 cout << "\n"; 242 } 243 } 244 ``` 245 246 **Difficulty** 247 248 Too hard 249 250 A bit on the harder side 251 252 Good difficulty 253 254 Easy 255 256 Too easy 257 258 **Quality** 259 260 Amazing 261 262 Good 263 264 So-so 265 266 Bad 267 268 Awful 269 270 [2259E - Разрушение карты сокровищ (конструктивная версия)](/contest/2259/problem/E "Codeforces Round 1119 (Div. 3)") 271 272 **Hint 1** 273 274 If an element $x$ at index $i$ is not equal to $-1$, there must be a treasure at either island $i + x$ or $i - x$ 275 276 **Hint 2** 277 278 If an element $x$ at index $i$ is not equal to $-1$, there must no treasures in the exclusive range of indices ($i + x$, $i - x$) 279 280 **Solution** 281 282 Tutorial is loading... 283 284 **Code** 285 286 ``` 287 #include <bits/stdc++.h> 288 using namespace std; 289 #define ll long long 290 291 int main() { 292 int t; 293 cin >> t; 294 295 296 while (t--) { 297 int n; 298 cin >> n; 299 300 vector<int> vec(n); for (auto &x: vec) cin >> x; 301 302 vector<int> diff(n+1); 303 for (int i = 0; i < n; i++) { 304 if (vec[i] > 0) { 305 diff[max(0, i-vec[i]+1)]++; 306 diff[min(n, i+vec[i])]--; 307 } 308 } 309 vector<bool> restricted(n); 310 int curr_count = 0; 311 for (int i = 0; i < n; i++) { 312 curr_count += diff[i]; 313 restricted[i] = curr_count > 0; 314 } 315 bool possible = true; 316 for (int i = 0; i < n && possible; i++) { 317 if (vec[i] >= 0) { 318 if (i - vec[i] >= 0 && !restricted[i - vec[i]]) continue; 319 if (i + vec[i] < n && !restricted[i + vec[i]]) continue; 320 possible = false; 321 } 322 } 323 324 if (!possible) cout << -1 << "\n"; 325 else { 326 for (auto x: restricted) cout << !x; 327 cout << "\n"; 328 } 329 } 330 } 331 ``` 332 333 **Difficulty** 334 335 Too hard 336 337 A bit on the harder side 338 339 Good difficulty 340 341 Easy 342 343 Too easy 344 345 **Quality** 346 347 Amazing 348 349 Good 350 351 So-so 352 353 Bad 354 355 Awful 356 357 [2259F - Инверсии бинарной пузырьковой сортировки](/contest/2259/problem/F "Codeforces Round 1119 (Div. 3)") 358 359 **Hint 1** 360 361 Look at performing some bubbles and reverse bubbles on small arrays. How many elements are moved? 362 363 **Hint 2** 364 365 A bubble will result is the leftmost 1 being moved all the way to the right. Similarly, a reverse bubble will result in the rightmost 0 being moved all the way to the left. 366 367 **Hint 3** 368 369 Since prefix zeroes and suffix ones don't matter, if we continuously remove them, then a bubble removes the last element of the array and a reverse bubble removes the first element of the array. Is there a way to remove the first and last elements of an array in constant time? 370 371 **Solution** 372 373 Tutorial is loading... 374 375 **Code** 376 377 ``` 378 #include <bits/stdc++.h> 379 using namespace std; 380 381 #define ll long long 382 int main() { 383 int t; 384 cin >> t; 385 386 while (t--) { 387 int n; 388 cin >> n; 389 390 vector<int> vec(n); for (auto &x: vec) cin >> x; 391 string s; 392 cin >> s; 393 394 ll inversions = 0; 395 int cnt_ones = 0; 396 for (int i = 0; i < n; i++) { 397 cnt_ones += vec[i]; 398 if (vec[i] == 0) inversions += cnt_ones; 399 } 400 cout << inversions << " "; 401 402 deque<int> dq; 403 for (auto &x: vec) dq.push_back(x); 404 int cnt_zeroes = count(vec.begin(), vec.end(), 0); 405 for (int i = 0; i < n; i++) { 406 while (dq.size() > 0 && dq.front() == 0) { 407 dq.pop_front(); 408 cnt_zeroes--; 409 } 410 while (dq.size() > 0 && dq.back() == 1) dq.pop_back(); 411 if (dq.size() == 0) { 412 cout << 0 << " "; 413 continue; 414 } 415 if (s[i] == '0') { 416 inversions -= (dq.size() - cnt_zeroes); 417 dq.pop_back(); 418 cnt_zeroes--; 419 } 420 else { 421 inversions -= cnt_zeroes; 422 dq.pop_front(); 423 } 424 cout << inversions << " "; 425 } 426 cout << "\n"; 427 } 428 } 429 ``` 430 431 **Difficulty** 432 433 Too hard 434 435 A bit on the harder side 436 437 Good difficulty 438 439 Easy 440 441 Too easy 442 443 **Quality** 444 445 Amazing 446 447 Good 448 449 So-so 450 451 Bad 452 453 Awful 454 455 [2259G - Убрали индекс](/contest/2259/problem/G "Codeforces Round 1119 (Div. 3)") 456 457 **Hint 1** 458 459 Ignoring indexes 1 and $n$, if we remove index $i$, if we perform an operation on index $j$, all elements between $[i, j]$ will also have an operation performed on them. 460 461 **Hint 2** 462 463 If we remove index $i$, and we have to reduce the element at index $i+1$, $i+2$, etc, what will we subtract it to? 464 465 **Solution** 466 467 Tutorial is loading... 468 469 **Code** 470 471 ``` 472 #include <bits/stdc++.h> 473 using namespace std; 474 475 #define ll long long 476 int main() { 477 int t; 478 cin >> t; 479 480 while (t--) { 481 ll n, k; 482 cin >> n >> k; 483 484 vector<ll> vec(n); for (auto &x: vec) cin >> x; 485 vector<ll> vec_2(n); for (int i = 0; i < n; i++) vec_2[i] = vec[i] - i * k; 486 487 vector<ll> prefix(n); prefix[0] = vec[0]; 488 for (int i = 1; i < n; i++) prefix[i] = prefix[i-1] + vec[i]; 489 490 vector<ll> ans(n); 491 for (int i = 1; i < n-1; i++) { 492 int lo = i+1; 493 int hi = n-1; 494 while (lo <= hi) { 495 int mid = lo + (hi - lo) / 2; 496 if (vec_2[mid] <= (vec[i-1] - i*k)) hi = mid - 1; 497 else lo = mid + 1; 498 } 499 500 ll num_needed = (lo - i - 1); 501 ans[i] = (prefix[num_needed + i] - prefix[i]) - (k * (num_needed * (num_needed + 1))/2) - vec[i-1] * num_needed; 502 } 503 for (auto &x: ans) cout << x << " "; 504 cout << "\n"; 505 } 506 } 507 ``` 508 509 **Difficulty** 510 511 Too hard 512 513 A bit on the harder side 514 515 Good difficulty 516 517 Easy 518 519 Too easy 520 521 **Quality** 522 523 Amazing 524 525 Good 526 527 So-so 528 529 Bad 530 531 Awful 532 533 [2259H - Разрушение карты сокровищ (версия подсчёта)](/contest/2259/problem/H "Codeforces Round 1119 (Div. 3)") 534 535 Read the solution to problem E first 536 537 **Hint 1** 538 539 Let's consider all locations that we have not restricted: we can separate them into 3 categories: the position is forced to be a treasure, the position has no undestroyed that depend on it, and all other positions. 540 541 **Hint 2** 542 543 The islands that are considered "non-restricted" form a chain of locations, with each non-restricted chain having a treasure between them. What must be true of the locations in this chain such that no condition is violated? 544 545 **Hint 3** 546 547 For every pair of adjacent locations, there must be at least one treasure at one of those locations. 548 549 **Solution** 550 551 Tutorial is loading... 552 553 **Code** 554 555 ``` 556 #include <bits/stdc++.h> 557 using namespace std; 558 #define ll long long 559 560 const ll MOD = 1000000007; 561 const int MAX_N = 200055; 562 int main() { 563 int t; 564 cin >> t; 565 566 567 vector<ll> fibo(MAX_N); 568 fibo[1] = 1; 569 fibo[2] = 1; 570 for (int i = 3; i < MAX_N; i++) { 571 fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD; 572 } 573 574 while (t--) { 575 int n; 576 cin >> n; 577 578 vector<int> vec(n); for (auto &x: vec) cin >> x; 579 580 vector<int> diff(n+1); 581 for (int i = 0; i < n; i++) { 582 if (vec[i] > 0) { 583 diff[max(0, i-vec[i]+1)]++; 584 diff[min(n, i+vec[i])]--; 585 } 586 } 587 588 vector<bool> restricted(n); 589 vector<bool> forced(n); 590 vector<int> non_required; 591 int curr_count = 0; 592 for (int i = 0; i < n; i++) { 593 curr_count += diff[i]; 594 restricted[i] = curr_count > 0; 595 } 596 597 bool possible = true; 598 for (int i = 0; i < n; i++) { 599 if (vec[i] != -1) { 600 int cnt = 0; 601 cnt += (i - vec[i] >= 0 && !restricted[i - vec[i]]); 602 cnt += (i + vec[i] < n && !restricted[i + vec[i]]); 603 if (cnt == 0) { possible = false;} 604 if (cnt == 1 || vec[i] == 0) { 605 if (i + vec[i] < n) forced[i + vec[i]] = true; 606 if (i - vec[i] >= 0) forced[i - vec[i]] = true; 607 } 608 } 609 } 610 for (int i = 0; i < n; i++) { 611 if (!restricted[i] && !forced[i]) non_required.push_back(i); 612 } 613 if (!possible) { 614 cout << 0 << "\n"; 615 continue; 616 } 617 618 ll total = 1; 619 int chain_len = 1; 620 for (int i = 0; i < non_required.size(); i++) { 621 bool cond1 = i == non_required.size() - 1 || vec[(non_required[i] + non_required[i+1])/2] == (non_required[i+1] - non_required[i])/2; 622 bool cond2 = i == non_required.size() - 1 || (non_required[i+1] - non_required[i]) % 2 == 0; 623 //if (i != 1) cout << (non_required[i+1] - non_required[i]) << "\n"; 624 if (i == non_required.size() - 1 || !cond1 || !cond2) { 625 //cout << chain_len << "\n"; 626 total *= fibo[chain_len+2]; 627 total %= MOD; 628 chain_len = 1; 629 } 630 else chain_len++; 631 } 632 if (count(vec.begin(), vec.end(), -1) == n) { 633 total = (total + MOD - 1) % MOD; 634 } 635 cout << total << "\n"; 636 } 637 } 638 ``` 639 640 **Difficulty** 641 642 Too hard 643 644 A bit on the harder side 645 646 Good difficulty 647 648 Easy 649 650 Too easy 651 652 **Quality** 653 654 Amazing 655 656 Good 657 658 So-so 659 660 Bad 661 662 Awful