codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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