2032.md (27339B)
1 Source: https://codeforces.com/blog/entry/135622 2 3 **README: Notice about solutions** 4 5 All editorial codes contain solutions wrapped in classes. I'll only paste the important part (`namespace solution` in C++, `class Solution` in Python 3) as plaintext in the solution code section (along with the corresponding AC submission link). You might want to see the code template here. 6 7 **C++ template** 8 9 ``` 10 #include <bits/stdc++.h> 11 using namespace std; 12 13 namespace solution { 14 bool hasMultipleTests = true; 15 16 void preprocess() { 17 // something 18 } 19 20 void input(int testcase) { 21 // something 22 } 23 24 void solve(int testcase) { 25 // something 26 } 27 } 28 29 int main() { 30 ios_base::sync_with_stdio(false); 31 cin.tie(NULL); 32 33 solution::preprocess(); 34 35 int t = 1; 36 if (solution::hasMultipleTests) cin >> t; 37 38 for (int testcase=1; testcase<=t; testcase++) { 39 solution::input(testcase); 40 solution::solve(testcase); 41 } 42 43 return 0; 44 } 45 ``` 46 47 **Python 3 template** 48 49 ``` 50 import sys 51 input = sys.stdin.readline 52 53 class Solution: 54 hasMultipleTests = True 55 56 @classmethod 57 def preprocess(cls): 58 pass 59 60 @classmethod 61 def input(cls, testcase): 62 pass 63 64 @classmethod 65 def solve(cls, testcase): 66 pass 67 68 # end Solution 69 70 if __name__ == '__main__': 71 Solution.preprocess() 72 73 t = int(input()) if Solution.hasMultipleTests else 1 74 for testcase in range(1, t+1): 75 Solution.input(testcase) 76 Solution.solve(testcase) 77 ``` 78 79 Also, per my own custom ever since 2019, solution codes will only be published **after** system testing, to ensure all codes used here guarantee AC. Thank you for your patience. 80 81 [2032A - Circuit](/contest/2032/problem/A "Codeforces Round 983 (Div. 2)") 82 83 Author: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 84 Development: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 85 Hinter: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 86 Editorialist: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 87 88 **Hint #1** 89 90 In which cases would a light be on? 91 92 **Hint #2A** 93 94 Imagine that you have $x$ white socks and $y$ black socks. What would you do to make the maximum pairs of matched socks? 95 96 **Hint #2B** 97 98 Imagine that you have $x$ white socks and $y$ black socks. What would you do to make the maximum pairs of unmatched socks? 99 100 **Tutorial** 101 102 Tutorial is loading... 103 104 **Solution (C++)** 105 106 Submission link: [289291089](/contest/2032/submission/289291089 "Submission 289291089 by AkiLotus") 107 108 **Plaintext** 109 110 ``` 111 namespace solution { 112 bool hasMultipleTests = true; 113 114 int n; 115 vector<int> a; 116 117 void preprocess() { 118 119 } 120 121 void input(int testcase) { 122 cin >> n; 123 a.clear(); 124 a.resize(n * 2); 125 for (auto &z: a) cin >> z; 126 } 127 128 void solve(int testcase) { 129 int cnt0 = 0; 130 131 for (auto &z: a) { 132 cnt0 += z; 133 } 134 135 cout << (cnt0 & 1) << " " << min(cnt0, n * 2 - cnt0) << endl; 136 } 137 } 138 ``` 139 140 **Solution (Python 3)** 141 142 Submission link: [289291082](/contest/2032/submission/289291082 "Submission 289291082 by AkiLotus") 143 144 **Plaintext** 145 146 ``` 147 class Solution: 148 hasMultipleTests = True 149 150 n: int = None 151 a: list = None 152 153 @classmethod 154 def preprocess(cls): 155 pass 156 157 @classmethod 158 def input(cls, testcase): 159 cls.n = int(input()) 160 cls.a = list(map(int, input().split())) 161 162 @classmethod 163 def solve(cls, testcase): 164 cnt0 = sum(cls.a) 165 166 print(cnt0 & 1, min(cnt0, cls.n*2 - cnt0)) 167 168 # end Solution 169 ``` 170 171 **Feedback** 172 173 * Didn't attempt 174 * Great problem 175 * Nice problem 176 * OK problem 177 * Bad problem 178 * Terrible problem 179 180 [2032B - Medians](/contest/2032/problem/B "Codeforces Round 983 (Div. 2)") 181 182 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 183 Development: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 184 Hinter: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 185 Editorialist: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 186 187 **Hint #1** 188 189 There is always exactly one solution for $n = 1$. For $n \ge 3$, for which $k$ should there be no solution at all? 190 191 **Hint #2A** 192 193 Try to find a solution with $k = 2$ and $k = 4$, assuming $n$ allows at least one solution to exist. Can you find a pattern and generalize it for all even $k$? 194 195 **Hint #2B** 196 197 Try to find a solution with $k = 3$ and $k = 5$, assuming $n$ allows at least one solution to exist. Can you find a pattern and generalize it for all odd $k$? 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Solution (C++)** 204 205 Submission link: [289291698](/contest/2032/submission/289291698 "Submission 289291698 by AkiLotus") 206 207 **Plaintext** 208 209 ``` 210 namespace solution { 211 bool hasMultipleTests = true; 212 213 int n, k; 214 215 void preprocess() { 216 217 } 218 219 void input(int testcase) { 220 cin >> n >> k; 221 } 222 223 void solve(int testcase) { 224 if (n == 1) {cout << "1\n1\n"; return;} 225 226 if (k == 1 || k == n) {cout << "-1\n"; return;} 227 228 int p2 = k - k % 2; 229 int p3 = k + 1 + k % 2; 230 cout << "3\n1 " << p2 << " " << p3 << endl; 231 } 232 } 233 ``` 234 235 **Solution (Python 3)** 236 237 Submission link: [289291693](/contest/2032/submission/289291693 "Submission 289291693 by AkiLotus") 238 239 **Plaintext** 240 241 ``` 242 class Solution: 243 hasMultipleTests = True 244 245 n: int = None 246 k: int = None 247 248 @classmethod 249 def preprocess(cls): 250 pass 251 252 @classmethod 253 def input(cls, testcase): 254 cls.n, cls.k = map(int, input().split()) 255 256 @classmethod 257 def solve(cls, testcase): 258 if cls.n == 1: return(print('1\n1')) 259 260 if cls.k in {1, cls.n}: return(print(-1)) 261 262 p2, p3 = cls.k - cls.k % 2, cls.k + 1 + cls.k % 2 263 print(f'3\n1 {p2} {p3}') 264 265 # end Solution 266 ``` 267 268 **Feedback** 269 270 * Didn't attempt 271 * Great problem 272 * Nice problem 273 * OK problem 274 * Bad problem 275 * Terrible problem 276 277 [2032C - Trinity](/contest/2032/problem/C "Codeforces Round 983 (Div. 2)") 278 279 Author: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 280 Development: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 281 Hinter: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 282 Editorialist: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 283 284 **Hint #1** 285 286 Without loss of generality, you can rewrite the triangle inequality into a much more compacted form if the side lengths are properly ordered. 287 288 **Hint #2A** 289 290 Given four integers $a \le b \le c \le d$, if $(a, b, d)$ are side lengths of a non-degenerate triangle, so does $(a, b, c)$. 291 292 **Hint #2B** 293 294 Given four integers $a \le b \le c \le d$, if $(a, b, d)$ are side lengths of a non-degenerate triangle, so does $(a, c, d)$. 295 296 **Hint #2C** 297 298 Given four integers $a \le b \le c \le d$, if $(a, b, d)$ are side lengths of a non-degenerate triangle, so does $(b, c, d)$. 299 300 **Hint #3** 301 302 To make a sorted array $[b_1, b_2, \ldots, b_m] \space (m \ge 3)$ satisfy the problem, we must ensure that $b_1 + b_2 \gt b_m$. 303 304 **Hint #4** 305 306 Fix the result array to have two minimas and one maxima at respectively $a_x$, $a_y$ and $a_z$. How many operations are required to do so? 307 308 **Hint #5** 309 310 Is there a fast and optimal way to try all possible $(a_x, a_y, a_z)$ triplets? 311 312 **Tutorial** 313 314 Tutorial is loading... 315 316 **Solution (C++)** 317 318 Submission link: [289292343](/contest/2032/submission/289292343 "Submission 289292343 by AkiLotus") 319 320 **Plaintext** 321 322 ``` 323 namespace solution { 324 bool hasMultipleTests = true; 325 326 int n; 327 vector<int> a; 328 329 void preprocess() { 330 331 } 332 333 void input(int testcase) { 334 cin >> n; 335 a.clear(); 336 a.resize(n); 337 for (auto &z: a) cin >> z; 338 } 339 340 void solve(int testcase) { 341 sort(a.begin(), a.end()); 342 343 int l = 0, ans = n - 2; 344 for (int r = 2; r < n; r++) { 345 while (r - l >= 2 && a[l] + a[l+1] <= a[r]) l++; 346 ans = min(ans, n - (r - l + 1)); 347 } 348 349 cout << ans << endl; 350 } 351 } 352 ``` 353 354 **Solution (Python 3)** 355 356 Submission link: [289292338](/contest/2032/submission/289292338 "Submission 289292338 by AkiLotus") 357 358 **Plaintext** 359 360 ``` 361 class Solution: 362 hasMultipleTests = True 363 364 n: int = None 365 a: list = None 366 367 @classmethod 368 def preprocess(cls): 369 pass 370 371 @classmethod 372 def input(cls, testcase): 373 cls.n = int(input()) 374 cls.a = list(map(int, input().split())) 375 376 @classmethod 377 def solve(cls, testcase): 378 cls.a.sort() 379 l, r, ans = 0, 2, cls.n - 2 380 while r < cls.n: 381 while r - l >= 2 and cls.a[l] + cls.a[l+1] <= cls.a[r]: l += 1 382 ans = min(ans, cls.n - (r - l + 1)) 383 r += 1 384 print(ans) 385 386 # end Solution 387 ``` 388 389 **Feedback** 390 391 * Didn't attempt 392 * Great problem 393 * Nice problem 394 * OK problem 395 * Bad problem 396 * Terrible problem 397 398 [2032D - Genokraken](/contest/2032/problem/D "Codeforces Round 983 (Div. 2)") 399 400 Author: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 401 Development: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 402 Hinter: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 403 Editorialist: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 404 405 **Hint #1** 406 407 There are many specific constraints on the system tree. 408 409 First, notice that $1 \le x \le y \le n-1$ if and only if $p_x \le p_y$. Draw a few trees with this constraint and start pointing your finger on the nodes from $0$ to $n-1$. Notice the pattern your finger is making. 410 411 **Hint #2** 412 413 Incorporate hint #1 with the fact that the "tentacles" of the Genokraken are just paths. Try to draw more detailed conclusion about that pattern. 414 415 **Hint #3A** 416 417 Is there a way to know how many tentacles there are? 418 419 **Hint #3B** 420 421 What use could we make of the fact that node $1$ has **exactly two** adjacent nodes? 422 423 **Hint #4** 424 425 The query limit is very small. Is there a way to query that the information obtained in each query should (at least partially) determine a node? 426 427 **Hint #5** 428 429 For each "tentacle", can we know when its path has ended? How many queries should it take? 430 431 **Tutorial** 432 433 Tutorial is loading... 434 435 **Solution (C++)** 436 437 Submission link: [289292866](/contest/2032/submission/289292866 "Submission 289292866 by AkiLotus") 438 439 **Plaintext** 440 441 ``` 442 namespace datastruct { 443 // A doubly-linked list that only supports modify and (pseudo) deletion at pointer 444 class DeleteOnly_DLL { 445 public: 446 vector<int> values; 447 vector<int> prev; 448 vector<int> next; 449 int pointer; 450 451 DeleteOnly_DLL(int size) { 452 values.resize(size); 453 prev.resize(size); 454 next.resize(size); 455 456 for (int i = 0; i < size; i++) { 457 prev[i] = (i + size - 1) % size; 458 next[i] = (i + 1) % size; 459 } 460 461 pointer = 0; 462 } 463 464 int current() { 465 return values[pointer]; 466 } 467 468 // Set value at pointer and move pointer to next 469 void set_and_move(int val) { 470 values[pointer] = val; 471 pointer = next[pointer]; 472 } 473 474 // "Delete" node and move pointer to next 475 void erase() { 476 if (prev[pointer] != -1) { 477 next[prev[pointer]] = next[pointer]; 478 } 479 if (next[pointer] != -1) { 480 prev[next[pointer]] = prev[pointer]; 481 } 482 483 int next_id = next[pointer]; 484 prev[pointer] = next[pointer] = -1; 485 pointer = next_id; 486 } 487 }; 488 } 489 490 namespace solution { 491 bool hasMultipleTests = true; 492 493 int n; 494 495 int ask(int a, int b) { 496 cout << "? " << a << " " << b << endl; 497 cout.flush(); 498 499 int res; cin >> res; 500 return res; 501 } 502 503 void answer(vector<int> &p) { 504 cout << "!"; 505 for (int i=1; i<n; i++) { 506 cout << " " << p[i]; 507 } 508 cout << endl; 509 cout.flush(); 510 } 511 512 void preprocess() { 513 514 } 515 516 void input(int testcase) { 517 cin >> n; 518 } 519 520 void solve(int testcase) { 521 vector<int> p(n, -1); 522 p[1] = 0; 523 524 int r = 2; 525 while (true) { 526 int response = ask(1, r); 527 if (response == -1) exit(2226); 528 529 if (response == 1) { 530 p[r] = 0; 531 r++; 532 } 533 else break; 534 } 535 536 int tentacle_count = r - 1; 537 538 datastruct::DeleteOnly_DLL tentacles = datastruct::DeleteOnly_DLL(tentacle_count); 539 for (int i = 0; i < tentacle_count; i++) { 540 tentacles.set_and_move(i + 1); 541 } 542 543 p[r] = tentacles.current(); 544 tentacles.set_and_move(r); 545 r++; 546 547 while (r < n) { 548 int response = ask(tentacles.current(), r); 549 if (response == -1) exit(2226); 550 551 if (response == 1) { 552 tentacles.erase(); 553 } 554 else { 555 p[r] = tentacles.current(); 556 tentacles.set_and_move(r); 557 r++; 558 } 559 } 560 561 answer(p); 562 } 563 } 564 ``` 565 566 **Solution (Python 3)** 567 568 Submission link: [289292865](/contest/2032/submission/289292865 "Submission 289292865 by AkiLotus") 569 570 **Plaintext** 571 572 ``` 573 class DeleteOnly_DLL: 574 def __init__(self, size: int): 575 self.values = [None for _ in range(size)] 576 self.prev = [(i + size - 1) % size for i in range(size)] 577 self.next = [(i + 1) % size for i in range(size)] 578 self.pointer = 0 579 580 def current(self): 581 return self.values[self.pointer] 582 583 # Set value at pointer and move pointer to next 584 def set_and_move(self, val): 585 self.values[self.pointer] = val 586 self.pointer = self.next[self.pointer] 587 588 # "Delete" node and move pointer to next 589 def erase(self): 590 if self.prev[self.pointer] != -1: 591 self.next[self.prev[self.pointer]] = self.next[self.pointer] 592 if self.next[self.pointer] != -1: 593 self.prev[self.next[self.pointer]] = self.prev[self.pointer] 594 595 next_id = self.next[self.pointer] 596 self.prev[self.pointer] = self.next[self.pointer] = -1 597 self.pointer = next_id 598 599 # end DeleteOnly_DLL 600 601 class Solution: 602 hasMultipleTests = True 603 604 n: int = None 605 606 @classmethod 607 def ask(cls, a: int, b: int): 608 print(f'? {a} {b}', flush=True) 609 return int(input()) 610 611 @classmethod 612 def answer(cls, p: list): 613 print(f'! {" ".join(map(str, p[1:]))}', flush=True) 614 615 @classmethod 616 def preprocess(cls): 617 pass 618 619 @classmethod 620 def input(cls, testcase): 621 cls.n = int(input()) 622 623 @classmethod 624 def solve(cls, testcase): 625 p = [-1 for _ in range(cls.n)] 626 p[1] = 0 627 628 r = 2 629 while True: 630 response = cls.ask(1, r) 631 if response == -1: exit(2226) 632 633 if response == 1: 634 p[r] = 0 635 r += 1 636 else: break 637 638 tentacle_count = r - 1 639 640 tentacles = DeleteOnly_DLL(size = tentacle_count) 641 for i in range(tentacle_count): 642 tentacles.set_and_move(i + 1) 643 644 p[r] = tentacles.current() 645 tentacles.set_and_move(r) 646 r += 1 647 648 while r < cls.n: 649 response = cls.ask(tentacles.current(), r) 650 if response == -1: exit(2226) 651 652 if response == 1: 653 tentacles.erase() 654 else: 655 p[r] = tentacles.current() 656 tentacles.set_and_move(r) 657 r += 1 658 659 cls.answer(p) 660 661 # end Solution 662 ``` 663 664 **Feedback** 665 666 * Didn't attempt 667 * Great problem 668 * Nice problem 669 * OK problem 670 * Bad problem 671 * Terrible problem 672 673 [2032E - Balanced](/contest/2032/problem/E "Codeforces Round 983 (Div. 2)") 674 675 Author: [thanhchauns2](/profile/thanhchauns2 "Master thanhchauns2") 676 Development: [thanhchauns2](/profile/thanhchauns2 "Master thanhchauns2"), [Sagita_Phoenix](/profile/Sagita_Phoenix "Specialist Sagita_Phoenix") 677 Hinter: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 678 Editorialist: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 679 680 **Hint #1** 681 682 Why is $n$ odd? Does it imply anything of the availability of a solution? 683 684 **Hint #2** 685 686 $n = 1$ is trivial. Try to solve this problem if $n = 3$ and $a_1 = a_3$. 687 688 **Hint #3** 689 690 Try to solve this problem for any array with $n = 3$. Is there any way to solve this without going pass a state of $a_1 = a_3$ (or $a_1 = a_2$ or $a_2 = a_3$)? 691 692 **Hint #4** 693 694 Assume that $n = 5$, $a_1 = a_5$ and $a_2 = a_3 = a_4$. Now refer to hint #2, can you see any similarity in the solution? 695 696 **Hint #5** 697 698 Refer to hint #4. What would happen if we apply an operation to index $2$ and another to index $4$? 699 700 **Hint #6** 701 702 For any array with $n = 5$, how would you convert it into the form stated in hint #4? 703 704 **Hint #7** 705 706 Refer to hint #6. How would you make $a_1 = a_5$ and $a_2 = a_4$? Does the fact that $n$ is odd help in any way? 707 708 **Hint #8** 709 710 Can you draw a generalized conclusion? 711 712 **Tutorial** 713 714 Tutorial is loading... 715 716 **Solution (C++)** 717 718 Submission link: [289293300](/contest/2032/submission/289293300 "Submission 289293300 by AkiLotus") 719 720 **Plaintext** 721 722 ``` 723 namespace solution { 724 bool hasMultipleTests = true; 725 726 int n; 727 vector<int> a; 728 729 void apply_prefixes(vector<long long> &prefixes, vector<long long> &v) { 730 for (int i = 2; i < n * 2; i++) { 731 prefixes[i] += prefixes[i - 2]; 732 } 733 734 for (int i = 0; i < n * 2; i++) { 735 v[i % n] += prefixes[i]; 736 } 737 } 738 739 void construct_trench(vector<long long> &arr, vector<long long> &v) { 740 vector<long long> prefixes(n * 2, 0LL); 741 vector<long long> delta(n, 0LL); 742 743 for (int i = 0; i < n / 2; i++) { 744 long long diff = arr[n - 1 - i] - (arr[i] + delta[i]); 745 746 delta[i] += 2 * diff; 747 delta[i + 1] += diff; 748 749 prefixes[n - i] += diff; 750 prefixes[n + i + 2] -= diff; 751 } 752 753 apply_prefixes(prefixes, v); 754 755 for (int i = 0; i < n; i++) { 756 arr[i] += v[i] * 2; 757 arr[(i + 1) % n] += v[i]; 758 arr[(i + n - 1) % n] += v[i]; 759 } 760 } 761 762 void construct_plateau(vector<long long> &arr, vector<long long> &v) { 763 vector<long long> prefixes(n * 2, 0LL); 764 vector<long long> delta(n, 0LL); 765 766 for (int i = n / 2 - 1; i >= 0; i--) { 767 long long diff = arr[i] - (arr[i + 1] + delta[i + 1]); 768 769 delta[i] += diff; 770 771 prefixes[i + 1] += diff; 772 prefixes[n - i] -= diff; 773 } 774 775 apply_prefixes(prefixes, v); 776 } 777 778 void preprocess() { 779 780 } 781 782 void input(int testcase) { 783 cin >> n; 784 a.clear(); 785 a.resize(n); 786 for (auto &z: a) cin >> z; 787 } 788 789 void solve(int testcase) { 790 if (n == 1) { 791 cout << "0\n"; 792 return; 793 } 794 795 vector<long long> v(n, 0LL); 796 vector<long long> arr(n); 797 for (int i = 0; i < n; i++) { 798 arr[i] = 1LL * a[i]; 799 } 800 801 construct_trench(arr, v); 802 construct_plateau(arr, v); 803 804 long long offset = *ranges::min_element(v); 805 806 for (auto &z: v) cout << z - offset << " "; 807 cout << endl; 808 } 809 } 810 ``` 811 812 **Solution (Python 3)** 813 814 Submission link: [289293299](/contest/2032/submission/289293299 "Submission 289293299 by AkiLotus") 815 816 **Plaintext** 817 818 ``` 819 class Solution: 820 hasMultipleTests = True 821 822 n: int = None 823 a: list = None 824 825 @classmethod 826 def apply_prefixes(cls, prefixes, v): 827 for i in range(2, cls.n*2): 828 prefixes[i] += prefixes[i - 2] 829 830 for i in range(cls.n*2): 831 v[i % cls.n] += prefixes[i] 832 833 @classmethod 834 def construct_trench(cls, arr, v): 835 prefixes = [0 for _ in range(cls.n * 2)] 836 delta = [0 for _ in range(cls.n)] 837 838 for i in range(cls.n // 2): 839 diff = arr[cls.n - 1 - i] - (arr[i] + delta[i]) 840 841 delta[i] += 2 * diff 842 delta[i + 1] += diff 843 844 prefixes[cls.n - i] += diff 845 prefixes[cls.n + i + 2] -= diff 846 847 cls.apply_prefixes(prefixes, v) 848 849 for i in range(cls.n): 850 arr[i] += v[i] * 2 851 arr[(i + 1) % cls.n] += v[i] 852 arr[(i + cls.n - 1) % cls.n] += v[i] 853 854 @classmethod 855 def construct_plateau(cls, arr, v): 856 prefixes = [0 for _ in range(cls.n * 2)] 857 delta = [0 for _ in range(cls.n)] 858 859 for i in range(cls.n // 2 - 1, -1, -1): 860 diff = arr[i] - (arr[i + 1] + delta[i + 1]) 861 862 delta[i] += diff 863 864 prefixes[i + 1] += diff 865 prefixes[cls.n - i] -= diff 866 867 cls.apply_prefixes(prefixes, v) 868 869 @classmethod 870 def preprocess(cls): 871 pass 872 873 @classmethod 874 def input(cls, testcase): 875 cls.n = int(input()) 876 cls.a = list(map(int, input().split())) 877 878 @classmethod 879 def solve(cls, testcase): 880 if cls.n == 1: 881 return(print(0)) 882 883 v = [0 for _ in range(cls.n)] 884 885 cls.construct_trench(cls.a, v) 886 cls.construct_plateau(cls.a, v) 887 888 offset = min(v) 889 v = list(map(lambda x: x - offset, v)) 890 891 print(*v) 892 893 # end Solution 894 ``` 895 896 **Alternative tutorial (Kuroni, rephrased by AkiLotus)** 897 898 We have some observations here. Our only allowed operation is $[1, 2, 1]$, but by stacking it in the right way (and normalizing the differences) we could obtain simpler operations. In details: 899 900 * We can apply operation $[-1, -1]$ to index $i$ (decrease values at index $i$ and $i+1$ by $1$) by applying operation $[1, 2, 1]$ to index $i+2$, $i+4$, and so on until $i-1$ (please treat these addition/subtraction of indices in a cyclic array context). Doing so will increase every index's value by $2$, except $i$ and $i+1$ only get increase by $1$, so relatively, indices $i$ and $i+1$ got their values lowered by $1$ compared to the rest. 901 * We can apply operation $[1]$ to index $i$ (increase value at index $i$ by $1$) by applying operation $[-1, -1]$ to index $i+1$, $i+3$, and so on until $i-1$. Proof for this is trivial. 902 903 **Feedback** 904 905 * Didn't attempt 906 * Great problem 907 * Nice problem 908 * OK problem 909 * Bad problem 910 * Terrible problem 911 912 [2032F - Peanuts](/contest/2032/problem/F "Codeforces Round 983 (Div. 2)") 913 914 Author: [MofK](/profile/MofK "Grandmaster MofK") 915 Development: [MofK](/profile/MofK "Grandmaster MofK"), [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 916 Hinter: [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 917 Editorialist: [MofK](/profile/MofK "Grandmaster MofK"), [AkiLotus](/profile/AkiLotus "Candidate Master AkiLotus") 918 919 **Hint #1** 920 921 Try to solve if all pockets are in the same box. Does the problem seem familiar? 922 923 **Hint #2** 924 925 There's one kind of cases for a box that its game has a fixed move sequence, and thus a fixed outcome. What is it? 926 927 **Hint #3** 928 929 Let's take the cases found in hint #2 out of the equation from here on. Is there any way for a player to win in two consecutive boxes? 930 931 **Hint #4** 932 933 If a player can win a box if both play optimally to win, can they also lose it if both play optimally to lose? 934 935 **Tutorial** 936 937 Tutorial is loading... 938 939 **Solution (C++)** 940 941 Submission link: [289293663](/contest/2032/submission/289293663 "Submission 289293663 by AkiLotus") 942 943 **Plaintext** 944 945 ``` 946 namespace solution { 947 bool hasMultipleTests = true; 948 949 int n; 950 vector<int> a; 951 952 const int MAXN = 1000000; 953 const int MOD = 998244353; 954 int pow2[MAXN]; 955 956 void preprocess() { 957 pow2[0] = 1; 958 for (int i = 1; i < MAXN; i++) { 959 pow2[i] = (2LL * pow2[i-1]) % MOD; 960 } 961 } 962 963 void input(int testcase) { 964 cin >> n; 965 a.clear(); 966 a.resize(n); 967 for (auto &z: a) cin >> z; 968 } 969 970 void solve(int testcase) { 971 if (*ranges::max_element(a) == 1) { 972 cout << (n & 1 ? pow2[n-1] : 0) << endl; 973 return; 974 } 975 976 int ans = 0; 977 978 // The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control 979 // if and only if before it is an even amount of pockets 980 int alice_at_critical = 1; 981 int prefix_1 = 0; 982 while (a[prefix_1] == 1) { 983 prefix_1++; 984 if (prefix_1 % 2 == 0) { 985 alice_at_critical = (alice_at_critical + pow2[prefix_1 - 1]) % MOD; 986 } 987 } 988 989 int grundy = (prefix_1 & 1); 990 for (int r = prefix_1; r < n; r++) { 991 grundy ^= a[r]; 992 993 if (!grundy) continue; 994 995 int post_critical = (r < n - 1 ? pow2[n - 2 - r] : 1); 996 int pre_critical = (grundy == 1 ? pow2[prefix_1] : alice_at_critical); 997 998 ans += (1LL * pre_critical * post_critical) % MOD; 999 ans %= MOD; 1000 } 1001 1002 cout << ans << endl; 1003 } 1004 } 1005 ``` 1006 1007 **Solution (Python 3)** 1008 1009 Submission link: [289293585](/contest/2032/submission/289293585 "Submission 289293585 by AkiLotus") 1010 1011 **Plaintext** 1012 1013 ``` 1014 class Solution: 1015 hasMultipleTests = True 1016 1017 n: int = None 1018 a: list = None 1019 1020 MAXN: int = 1000000 1021 MOD: int = 998244353 1022 pow2: list = None 1023 1024 @classmethod 1025 def preprocess(cls): 1026 cls.pow2 = [None for _ in range(cls.MAXN)] 1027 for i in range(cls.MAXN): 1028 cls.pow2[i] = 1 if i == 0 else (2 * cls.pow2[i-1]) % cls.MOD 1029 1030 @classmethod 1031 def input(cls, testcase): 1032 cls.n = int(input()) 1033 cls.a = list(map(int, input().split())) 1034 1035 @classmethod 1036 def solve(cls, testcase): 1037 if max(cls.a) == 1: 1038 return(print(cls.pow2[cls.n-1] if cls.n & 1 else 0)) 1039 1040 ans = 0 1041 1042 # The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control 1043 # if and only if before it is an even amount of pockets 1044 alice_at_critical = 1 1045 prefix_1 = 0 1046 while cls.a[prefix_1] == 1: 1047 prefix_1 += 1 1048 1049 if prefix_1 % 2 == 0: 1050 alice_at_critical = (alice_at_critical + cls.pow2[prefix_1 - 1]) % cls.MOD 1051 1052 grundy = prefix_1 & 1 1053 for r in range(prefix_1, cls.n): 1054 grundy ^= cls.a[r] 1055 1056 if grundy == 0: continue 1057 1058 post_critical = cls.pow2[cls.n - 2 - r] if r < cls.n - 1 else 1 1059 pre_critical = cls.pow2[prefix_1] if grundy == 1 else alice_at_critical 1060 1061 ans = (ans + pre_critical * post_critical) % cls.MOD 1062 1063 print(ans) 1064 1065 # end Solution 1066 ``` 1067 1068 **Feedback** 1069 1070 * Didn't attempt 1071 * Great problem 1072 * Nice problem 1073 * OK problem 1074 * Bad problem 1075 * Terrible problem