codeforces-scrape

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

2261.md (58870B)


      1 Source: https://codeforces.com/blog/entry/157917
      2 
      3 **Rating predictions**
      4 
      5 | Predictor | A | B | C | D1 | D2 | E | F1 | F2 | G | H |
      6 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | Predicted | 486 | 927 | 839 | 1160 | 2236 | 1694 | 2406 | 3639 | 2607 | 3250 |
      8 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 900 | 1100 | 1400 | 2600 | 2000 | 2500 | 3500 | 2900 | 3400 |
      9 | [ttamx](/profile/ttamx "Grandmaster ttamx") | 800 | 1000 | 1200 | 1400 | 2500 | 1800 | 2100 | 3500 | 2800 | 3100 |
     10 | [ItzsleepyXD](/profile/ItzsleepyXD "Expert ItzsleepyXD") | ? | ? | 1000 | ? | ? | ? | 2100 | 2800 | ? | ? |
     11 | [simplelife](/profile/simplelife "Expert simplelife") | 800 | 1000 | 1100 | 1500 | ? | 1900 | 2300 | 3500 | ? | 3000 |
     12 | [wakanda-forever](/profile/wakanda-forever "Candidate Master wakanda-forever") | 900 | 1000 | 1100 | ? | ? | 2000 | 2100 | ? | ? | ? |
     13 | [Marszpace](/profile/Marszpace "Master Marszpace") | 800 | 1000 | 1100 | 1500 | ? | 1900 | ~2200 | ? | ? | ? |
     14 | [Argentum47](/profile/Argentum47 "Candidate Master Argentum47") | 800 | 1200 | 1200 | 1600 | ? | 1900 | 2300 | ? | ? | 2700 |
     15 | [omsincoconut](/profile/omsincoconut "Candidate Master omsincoconut") | 800 | 1100 | 1300 | ? | ? | ? | 2400 | 3500 | 2600 | 3100 |
     16 | [Stathis](/profile/Stathis "Master Stathis") | 900 | 1200 | 1300 | 1600 | 2700 | 1800 | 2200 | 3500 | 2600 | 2800 |
     17 | [ReverseFlash081](/profile/ReverseFlash081 "Candidate Master ReverseFlash081") | 900 | 1100 | 1100 | 1400 | 2500 | 1900 | ? | ? | ? | ? |
     18 | [samsoom](/profile/samsoom "Expert samsoom") | 800 | 1000 | 1100 | 1400 | 2300 | 1800 | ? | ? | ? | ? |
     19 | [SkyMagic](/profile/SkyMagic "Pupil SkyMagic") | 800 | 900 | 1000 | ? | ? | 1500 | ? | ? | 800 | 3100 |
     20 | [nik_exists](/profile/nik_exists "Expert nik_exists") | 800 | 1000 | 1000 | ? | ? | 1700 | ? | ? | ? | ? |
     21 | [yse](/profile/yse "Candidate Master yse") | 800 | 900 | 1000 | 1200 | 2200 | 1900 | 2500 | 3400 | 2900 | 3200 |
     22 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 900 | 1000 | 1400 | 2500 | 2100 | 2600 | 3500 | 2900 | 3100 |
     23 
     24 [2261A - Hey, It's Me, Souvlakity](/contest/2261/problem/A)
     25 
     26 Author: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")   
     27  Preparation, Editorial: [Marszpace](/profile/Marszpace "Master Marszpace")
     28 
     29 **Hint 1**
     30 
     31 The number of integers Souvlakity initially has is the same as the number of integers he has at the end of the game.
     32 
     33 **Hint 2**
     34 
     35 Consider cases based on the amount of integers Souvlakity has.
     36 
     37 **Solution**
     38 
     39 The number of integers Souvlakity initially owns is equal to the number of integers he owns at the end of the game. This is because during each pair of consecutive turns (Souvlakity's turn and then Kalamakity's turn), Souvlakity gives away exactly one integer but also receives exactly one integer.
     40 
     41 Let $k$ be the number of integers that Souvlakity owns at the beginning of the game.
     42 
     43 * If $k=1$, Souvlakity will own a single integer at the end of the game, so his score is $0$.
     44 * If $k=2$, no matter which integer Souvlakity chooses to give away in round 1, Kalamakity can give him an integer adjacent to the one he kept. His score is $1$, and Kalamakity can force this score at the end of the game by always giving Souvlakity the same integer back.
     45 * If $k\ge3$, Souvlakity can give away any integer that is not his minimum or maximum, and his score does not decrease. Kalamakity can also keep returning the integer that Souvlakity just gave him, and therefore Souvlakity's score does not increase. At the end, Souvlakity will have the same maximum and minimum as he did at the beginning of the game, with the score of $\max(S)-\min(S)$.
     46 
     47 Therefore we only need to find $k$, $\max(S)$ and $\min(S)$ which is doable in $O(n)$.
     48 
     49 **Code**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 using namespace std;
     54 
     55 int main () {
     56   ios_base::sync_with_stdio(0); cin.tie(0);
     57   int T;
     58   cin >> T;
     59   while (T--) {
     60     int n;
     61     string s;
     62     cin >> n >> s;
     63     int c = count(s.begin(), s.end(), '1');
     64     if (c <= 2) {
     65       cout << c-1 << '\n';
     66       continue;
     67     }
     68     int l = s.find('1'), r = s.rfind('1');
     69     cout << r-l << '\n';
     70   }
     71 }
     72 ```
     73 
     74 **Rate The Problem!**
     75 
     76 * Good Problem
     77 * Okay Problem
     78 * Bad Problem
     79 * Didn't Solve
     80 
     81 [2261B - What's the Capital of France?](/contest/2261/problem/B)
     82 
     83 Author, Preparation, Editorial: [omsincoconut](/profile/omsincoconut "Candidate Master omsincoconut")
     84 
     85 **Hint 1**
     86 
     87 What is the maximum possible answer?
     88 
     89 **Hint 2**
     90 
     91 Only the minimum and maximum value in the array matters.
     92 
     93 **Hint 3**
     94 
     95 Think about solving from the highest bit.
     96 
     97 **Solution**
     98 
     99 Denote $\operatorname{msb}(x)$ as the position of the most significant bit of $x$, where the $0$-th bit is the least significant bit.
    100 
    101 The maximum value cannot increase, so $\operatorname{msb}(answer) = \operatorname{msb}(\max(a)) = b$.
    102 
    103 If $\operatorname{msb}(\min(a)) \lt b$, then we can increase the minimum value to be $2^b - 1$ by repeatedly incrementing some entry in the array that is adjacent to a larger entry and less than $2^b - 1$. This results in the answer being exactly $2^{b+1} - 1$.
    104 
    105 What if $\operatorname{msb}(\min(a)) = b$ though? Then we cannot do anything to that bit or the bits higher. We can just ignore the $\operatorname{msb}$ bit and all higher bits. Repeat this until the bit of the maximum and minimum entries of the array does not match.
    106 
    107 Hence, the answer is $\max(a) \operatorname{OR}(2^{k+1} - 1)$ where $k = \operatorname{msb}(\max(a) \operatorname{XOR} \min(a))$ if $\max(a) \neq \min(a)$, and simply $\max(a)$ otherwise.
    108 
    109 **Code**
    110 
    111 ```
    112 #include<bits/stdc++.h>
    113 using namespace std;
    114 
    115 int main() {
    116     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    117     int t;cin>>t;
    118     while(t--) {
    119         int n;cin>>n;
    120         int mx=INT_MIN,mn=INT_MAX;
    121         for (int i = 0; i < n; i++) {
    122             int a;cin >> a;
    123             mx = max(mx,a);
    124             mn = min(mn,a);
    125         }
    126         if (mx == mn) cout << mx << '\n';
    127         else {
    128             cout << (((1<<(32-__builtin_clz(mx^mn)))-1)|mx) << '\n';
    129         }
    130     }
    131 }
    132 ```
    133 
    134 **Rate The Problem!**
    135 
    136 * Good Problem
    137 * Okay Problem
    138 * Bad Problem
    139 * Didn't Solve
    140 
    141 [2261C - I Know About a Million Things](/contest/2261/problem/C)
    142 
    143 Author, Preparation, Editorial: [Marszpace](/profile/Marszpace "Master Marszpace")
    144 
    145 **Hint 1**
    146 
    147 For each state, does the actual value of the integers in the array matter? What matters for each state?
    148 
    149 **Hint 2**
    150 
    151 Only the counts of odd and even integers matter. In which state can Larpity win?
    152 
    153 **Hint 3**
    154 
    155 Consider states you know Larpity (as the second player) win. Think how Moggity (as the first player) can give Larpity that first-player-losing state.
    156 
    157 **Solution**
    158 
    159 Only the counts of odd and even integers matter, not the values themselves, because whether a move can be done is based on the parity of their sum, and that parity only depends on the parity of the elements. Therefore, we can represent every input (and game state) with $(E,O)$, where $E$ is the number of even integers and $O$ is the number of odd integers.
    160 
    161 Firstly, we can observe that Larpity wins when the input is in state $(1,1)$ or $(0,3)$. Here's why:
    162 
    163 * For $(1,1)$ (for example, the integers $2,3$, as given in one of the samples), Moggity cannot remove both of the integers, and he must remove one. Larpity removes the remaining one, and Moggity faces an empty array.
    164 * For $(0,3)$ (for example, the integers $1,3,5$), Moggity cannot remove all three of the integers. If he removes one integer, Larpity can remove the other two, and Moggity faces an empty array. If he removes two integers, Larpity can remove the other one, and Moggity once again faces an empty array.
    165 
    166 Therefore, for these two cases, Larpity wins.
    167 
    168 Then, we will show that, in any other cases, Moggity will win.
    169 
    170 * Consider the case where $O$ is even (including $O=0$), i.e. there is an even number of odd integers. The sum over the entire array is even, so Moggity can remove the entire array and win on the first turn.
    171 * Consider the case where $O$ is $1$. If $E$ is $0$, then Moggity can remove the single odd integer and win. If $E$ is $1$, this is the state $(1,1)$ where Moggity loses. If $E\geq2$, Moggity can remove $E-1$ even integers, and force Larpity to face the state $(1,1)$. Larpity must remove one integer, and cannot remove two, and so Larpity will lose, and Moggity will win.
    172 * Consider the case where $O$ is $3$. If $E$ is $0$, we know Moggity loses. If $E\geq1$, Moggity can remove all even integers, and again, force Larpity to face a losing position of $(0,3)$. Larpity must remove one or two integers, and cannot remove three, so Larpity will lose, and once again Moggity will win.
    173 * Consider the case when $O$ is odd and $O\geq 5$, Moggity can remove all even integers (if any), and $O-3$ odd integers. This leaves Larpity with the state of $(0,3)$, and once again, Larpity will lose.
    174 
    175 Thus, Larpity wins if and only if the array is exactly one odd and one even integer, or exactly three odd integers (i.e. $(E,O)=(1,1)$ or $(0,3)$) and Moggity wins in all other cases.
    176 
    177 The total time complexity is $O(n)$ for scanning over all elements and counting the odd and even elements.
    178 
    179 **Code (C++)**
    180 
    181 ```
    182 /*
    183  * And in that light, I find deliverance.
    184  * TASK : WorldQuant Round 1 : I Know A Million Things (feat. Gessou by Chroma and rintaro soma, from CHUNITHM)
    185  * AUTHOR : Marszpace
    186 */
    187 
    188 #include<bits/stdc++.h>
    189 using namespace std;
    190 
    191 void solve(){
    192   int n;
    193   cin >> n;
    194   int cnt[2]={};
    195   for(int i=0;i<n;i++){
    196     int a;
    197     cin >> a;
    198     cnt[a%2]++;
    199   }
    200   if((cnt[1]==1 && cnt[0]==1) || (cnt[1]==3 && cnt[0]==0)){
    201     cout << "Larpity\n";
    202     return;
    203   }
    204   cout << "Moggity\n";
    205   return;
    206 }
    207 
    208 int main(){
    209   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    210   int tt;
    211   cin >> tt;
    212   while(tt--){
    213     solve();
    214   }
    215   return 0;
    216 }
    217 ```
    218 
    219 **Rate The Problem!**
    220 
    221 * Good Problem
    222 * Okay Problem
    223 * Bad Problem
    224 * Didn't Solve
    225 
    226 [2261D1 - Come Be My Friend, Don't Be So Scared (Easy Version)](/contest/2261/problem/D1)
    227 
    228 Author, Preparation: [omsincoconut](/profile/omsincoconut "Candidate Master omsincoconut") Editorial:[Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    229 
    230 **Hint 1**
    231 
    232 All the spots being distinguishable means that the reports for any two spots are different from at least one detector.
    233 
    234 **Hint 2**
    235 
    236 Each detector is an interval. It can only change in two endpoints. Come up with a lower bound for $k$ from this, and then come up with a construction that achieves this lower bound.
    237 
    238 **Solution**
    239 
    240 Since $m=0$, there are no existing detectors.
    241 
    242 When $n=1$, the answer is $0$.
    243 
    244 First, we find a lower bound of the answer.
    245 
    246 Suppose we install $k$ detectors. Each detector covers an interval, so its answer changes at most twice as we move from left to right: once from $0$ to $1$ and once from $1$ to $0$.
    247 
    248 To distinguish all $n$ spots, at least one detector must return a different report for every two consecutive spots. Thus, at least $n-1$ changes are required.
    249 
    250 Additionally, the first and last spots cannot both have all-zero reports (unless $n=1$). Therefore, at least one extra change is required at one of the endpoints.
    251 
    252 Therefore, a lower bound on $k$ is $k\ge\left\lceil\frac n2\right\rceil.$
    253 
    254 Next, we provide a construction using $k=\lceil\frac{n}{2}\rceil$ detectors for $n \ge 1$.
    255 
    256 Install $k$ detectors, where detector $i$ covers $[i,i+k-1].$ All of these intervals are valid because $2k-1 \le n$.
    257 
    258 For $1 \le i \le k$, a new interval is started for each $i$. Therefore, they are pairwise distinct.
    259 
    260 For $k+1 \le i \lt 2k$, one interval ends for each $i$. Therefore, they are also pairwise distinct among each other. To prove that the signals for these $k$ signals are different from the first $k$ spots, we notice that the first interval includes all of the first $k$ spots, but none of these $k$.
    261 
    262 If $n$ is even, this leaves spot $n$, which will return false for all detectors. Since this is the only spot for this, we can also distinguish hiding spot $n$.
    263 
    264 **Code**
    265 
    266 ```
    267 // 
    268 
    269 #include <bits/stdc++.h>
    270 using namespace std;
    271 
    272 using ll = long long;
    273 using pi = pair<int, int>;
    274 
    275 void solve(void){
    276     
    277     int n;
    278     cin >> n;
    279     int m;
    280     cin >> m;
    281     if(n==1){
    282         cout << 0 << endl;
    283         return;
    284     }
    285     vector<pair<int,int>> ans;
    286     
    287     vector<pair<int,int>> act;
    288     cout << (n+1)/2 << endl;
    289     int mid = (n+1)/2;
    290     
    291     
    292     for(int i=0; i<mid; i++){
    293         cout << i+1 << " " << i+mid << endl;
    294     }
    295 }
    296 
    297 int main(void) {
    298     ios_base::sync_with_stdio(false);
    299     cin.tie(NULL);
    300 
    301     int t;
    302     cin >> t;
    303     while(t--) solve();
    304     
    305     return 0;
    306 }
    307 ```
    308 
    309 **Rate The Problem!**
    310 
    311 * Good Problem
    312 * Okay Problem
    313 * Bad Problem
    314 * Didn't Solve
    315 
    316 [2261D2 - Come Be My Friend, Don't Be So Scared (Hard Version)](/contest/2261/problem/D2)
    317 
    318 Author, Preparation: [omsincoconut](/profile/omsincoconut "Candidate Master omsincoconut") Editorial:[Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    319 
    320 **Hint 1**
    321 
    322 First, find a way to calculate some representation of all detector reports for each spot.
    323 
    324 **Hint 2**
    325 
    326 If two spots currently have the same detector report, they need to be distinguished by a new detector.
    327 
    328 **Hint 3**
    329 
    330 Suppose we represent spots with the same report as intervals. The intervals are pairwise either disjoint or one is fully encased in another. Use this to come up with a lower bound similar to the lower bound in D1.
    331 
    332 **Solution**
    333 
    334 First, we need a way to quickly calculate the set of given detectors for each hiding spot. One way to do this is with XOR hashing. Denote $h_i$ as some number representing the set of detectors that are active in hiding spot $i$. With a detector at $[l,r]$, we can XOR every number in the range from $l$ to $r$ by the same random number (this can be sped up with prefix XOR). At the end, with high probability, if $h_i=h_j$, then it means that the same set of intervals contain both positions $i$ and $j$, and if $h_i\ne h_j$, then different sets of intervals contain $i$ and $j$.
    335 
    336 For every pair of $(i,j)$ with $h_i=h_j$, some new detector must cover exactly one of these two spots. Equivalently, exactly one of its two endpoints must lie between $i$ and $j$. If there are three indices $i \lt j \lt k$ with $h_i=h_j=h_k$, a new detector endpoint must be added between both $i$ and $j$, and $j$ and $k$. Therefore, for each index $i$, it suffices to compute the smallest $j$ with $h_j=h_i$ and $j \gt i$. Call this number $nxt_i$.
    337 
    338 This creates $O(n)$ different intervals between $(i,nxt_i)$. The next observation is that these intervals are either nested or disjoint: they cannot intersect without one containing the other.
    339 
    340 **Proof**
    341 
    342 Suppose otherwise. Then there exist indices $i \lt j \lt nxt_i \lt nxt_j$.
    343 
    344 Since $h_i=h_{nxt_i}$ and $h_j=h_{nxt_j}$, the sets of existing detectors covering $i$ and $nxt_i$ are identical, as are those covering $j$ and $nxt_j$.
    345 
    346 Furthermore, $h_i\ne h_j$, since $nxt_i$ is the first occurrence of $h_i$ after $i$.
    347 
    348 Therefore, there exists some detector that covers exactly one of $i$ and $j$.
    349 
    350 If it covers $i$ but not $j$, it must also cover $nxt_i$, contradicting that its interval is contiguous.
    351 
    352 Otherwise, it covers $j$ but not $i$. It must also cover $nxt_j$, but not $nxt_i$, again contradicting contiguity.
    353 
    354 Thus, two intervals cannot partially overlap, so they must be either nested or disjoint.
    355 
    356 If a smaller interval $(j,nxt_j)$ is completely contained inside a larger interval $(i,nxt_i)$, then the smaller interval forces a new detector endpoint inside it. This also satisfies the necessary endpoint condition for the larger interval. Therefore, we can ignore all intervals that contain another interval.
    357 
    358 Since the original intervals are either nested or disjoint, the remaining intervals are pairwise disjoint. Let there be $q$ such intervals. Each requires at least one new detector endpoint, so at least $q$ endpoints are necessary.
    359 
    360 We can greedily place one endpoint inside each of these intervals, for example, immediately before its right endpoint. This gives the minimum possible number of internal endpoints, $q$.
    361 
    362 However, just placing an endpoint inside every interval is not sufficient. If both endpoints of some new detector lie between two spots with the same existing report, that detector cannot distinguish them. We need to pair the endpoints carefully, using the same construction as D1.
    363 
    364 Suppose the selected endpoints are $b_1 \lt b_2 \lt \cdots \lt b_q$, where endpoint $b_i$ represents a change between spots $b_i$ and $b_i+1$. These divide the hiding spots into $q+1$ regions.
    365 
    366 As in D1, we can make the new reports of all these regions pairwise distinct, except possibly the first and last regions.
    367 
    368 If $q$ is odd, we add an endpoint before spot $1$, making the total number of endpoints even.
    369 
    370 If $q$ is even, we can pair the $q$ endpoints directly. In this case, the first and last regions both have all new detectors inactive, while every other region has a unique report.
    371 
    372 Therefore, if some existing report appears in both the first and last regions, we need one more detector. We do this by adding endpoints before spot $1$ and after spot $n$.
    373 
    374 Now, let all the endpoints in increasing order be $c_1 \lt c_2 \lt \cdots \lt c_{2k}$, where $k$ is the number of new detectors. For every $1\le i\le k$, install a detector covering $[c_i+1,c_{i+k}]$.
    375 
    376 This is exactly the construction from D1: the first $k$ endpoints start detectors one by one, and the last $k$ endpoints end them in the same order. Therefore, all regions have distinct new reports, except possibly the first and last when no extra endpoint is added.
    377 
    378 In particular, any two spots with the same existing report lie in different regions, since at least one selected endpoint lies between every two consecutive occurrences of that report. Since these regions have different new reports (unless they are the first and last regions, which we handle separately), all spots can be distinguished.
    379 
    380 Note that whether some existing report appears in both the first and last regions does not depend on where we choose the endpoints inside the remaining intervals. Indeed, such a report must occur at or before the left endpoint of the first remaining interval and at or after the right endpoint of the last remaining interval. Otherwise, we would obtain two intervals that partially overlap, contradicting our earlier observation.
    381 
    382 Thus, for $q \gt 0$, the answer is
    383 
    384 $\boxed{ \begin{cases} \lceil q/2\rceil+1, & \text{if }q\text{ is even and the first and last regions}\\ &\text{contain a common existing report},\\ \lceil q/2\rceil, & \text{otherwise}. \end{cases} }$
    385 
    386 If $q=0$, all existing reports are already distinct, so the answer is $0$.
    387 
    388 To see why this is optimal, the $q$ disjoint intervals require at least $q$ internal endpoints. If $q$ is odd, this already requires at least $\lceil q/2\rceil$ detectors.
    389 
    390 If $q$ is even and the first and last regions contain a common report, using only $q/2$ detectors would force all their endpoints to be internal, with exactly one endpoint in each of the $q$ disjoint intervals. In particular, none of these detectors could distinguish the two occurrences of that common report, since all their endpoints would lie between those occurrences. Hence, one additional detector is necessary.
    391 
    392 Therefore, our construction matches the lower bound and is optimal.
    393 
    394 Finally, all intervals, the greedy endpoints, and the construction can be found in $O(n+m)$ expected time using hashing.
    395 
    396 **Code**
    397 
    398 ```
    399 #include<bits/stdc++.h>
    400 
    401 using namespace std;
    402 
    403 #define pb push_back
    404 #define eb emplace_back
    405 #define mp make_pair
    406 #define mt make_tuple
    407 #define fi first
    408 #define se second
    409 
    410 #define ALL(a) a.begin(),a.end()
    411 #define RALL(a) a.rbegin(),a.rend()
    412 #define SORT(a) sort(ALL(a))
    413 #define RSORT(a) sort(RALL(a))
    414 #define REV(a) reverse(ALL(a))
    415 #define UNI(a) a.erase(unique(ALL(a)),a.end())
    416 #define SZ(a) (int)(a.size())
    417 #define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
    418 #define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
    419 #define MIN(a) *min_element(ALL(a))
    420 #define MAX(a) *max_element(ALL(a))
    421 
    422 using ll = long long;
    423 using db = long double;
    424 using i128 = __int128_t;
    425 using u32 = uint32_t;
    426 using u64 = uint64_t;
    427 
    428 const int INF=INT_MAX/2;
    429 const ll LINF=LLONG_MAX/4;
    430 const db DINF=numeric_limits<db>::infinity();
    431 const int MOD=998244353;
    432 const int MOD2=1000000007;
    433 const db EPS=1e-9;
    434 const db PI=acos(db(-1));
    435 
    436 template<class T>
    437 using PQ = priority_queue<T,vector<T>,greater<T>>;
    438 
    439 #define vv(T,a,n,...) vector<vector<T>> a(n,vector<T>(__VA_ARGS__))
    440 #define vvv(T,a,n,m,...) vector<vector<vector<T>>> a(n,vector<vector<T>>(m,vector<T>(__VA_ARGS__)))
    441 #define vvvv(T,a,n,m,k,...) vector<vector<vector<vector<T>>>> a(n,vector<vector<vector<T>>>(m,vector<vector<T>>(k,vector<T>(__VA_ARGS__))))
    442 
    443 template<class T,class U>
    444 bool chmin(T &a,U b){return b<a?a=b,1:0;}
    445 template<class T,class U>
    446 bool chmax(T &a,U b){return a<b?a=b,1:0;}
    447 template<class T,class U>
    448 T SUM(const U &a){return accumulate(ALL(a),T{});}
    449 
    450 static inline u64 rng64(){
    451     static u64 x=(u64)(chrono::steady_clock::now().time_since_epoch().count())*10150724397891781847ULL;
    452     const u64 c=0xd07ebc63274654c7ull;
    453     x+=c;
    454     __uint128_t t=(__uint128_t)x*(x^c);
    455     return t^(t>>64);
    456 }
    457 
    458 void runcase(){
    459     int n,m;
    460     cin >> n >> m;
    461     vector<u64> a(n);
    462     for(int i=0;i<m;i++){
    463         int l,r;
    464         cin >> l >> r;
    465         l--;
    466         u64 h=rng64();
    467         a[l]^=h;
    468         if(r<n)a[r]^=h;
    469     }
    470     for(int i=1;i<n;i++)a[i]^=a[i-1];
    471     map<u64,int> last;
    472     vector<int> dp(n),pre(n,-1);
    473     deque<int> dq{0};
    474     last[a[0]]=0;
    475     int st=n,ed=-1;
    476     for(int i=1;i<n;i++){
    477         dp[i]=dp[dq.front()]+1;
    478         pre[i]=dq.front();
    479         if(last.count(a[i])){
    480             int p=last[a[i]];
    481             st=min(st,p);
    482             ed=i;
    483             while(!dq.empty()&&dq.front()<=p){
    484                 dq.pop_front();
    485             }
    486         }
    487         if(!dq.empty()&&chmin(dp[i],dq.front())){
    488             pre[i]=dq.front();
    489         }
    490         while(!dq.empty()&&dp[i]<dp[dq.back()]){
    491             dq.pop_back();
    492         }
    493         dq.emplace_back(i);
    494         last[a[i]]=i;
    495     }
    496     vector<int> pos;
    497     for(int i=dq.front();i>0;i=pre[i]){
    498         pos.emplace_back(i);
    499     }
    500     if(ed!=-1&&a[st]==a[ed]){
    501         pos.emplace_back(st);
    502     }
    503     if(SZ(pos)%2==1)pos.emplace_back(n);
    504     SORT(pos);
    505     int h=SZ(pos)/2;
    506     cout << h << "\n";
    507     for(int i=0;i<h;i++){
    508         cout << pos[i]+1 << " " << pos[i+h] << "\n";
    509     }
    510 }
    511 
    512 int main(){
    513     cin.tie(nullptr)->sync_with_stdio(false);
    514     int t(1);
    515     cin >> t;
    516     while(t--)runcase();
    517 }
    518 ```
    519 
    520 **Rate The Problem!**
    521 
    522 * Good Problem
    523 * Okay Problem
    524 * Bad Problem
    525 * Didn't Solve
    526 
    527 [2261E - What Does the Cow Say?](/contest/2261/problem/E)
    528 
    529 Author, Preparation, Editorial: [yse](/profile/yse "Candidate Master yse")
    530 
    531 **Hint 1**
    532 
    533 Represent the string using $c[i]$, the number of consecutive opening brackets before the $i$-th closing bracket.
    534 
    535 **Hint 2**
    536 
    537 Consider prefix blocks and middle windows separately.
    538 
    539 **Solution**
    540 
    541 Let $m = \frac{n}{2}$ and number the closing brackets $1, \dots, m$ from left to right. Let $c[i]$ be the number of consecutive $\texttt{(}$ directly before the $i$-th $\texttt{)}$; this is $0$ if that $\texttt{)}$ follows another $\texttt{)}$.
    542 
    543 An operation on an occurrence of $\texttt{()}$ deletes one $\texttt{(}$ and one $\texttt{)}$ from the middle of the string, then adds a $\texttt{(}$ at the very front and a $\texttt{)}$ at the very end. In terms of $c$, it removes one closing bracket, merges the run of $\texttt{(}$ before it with the run after it, and sends one $\texttt{(}$ to the far left. The final block of consecutive $\texttt{(}$ is either a prefix of the string or a window in the middle, so we handle the two cases separately.
    544 
    545 Let's look at the first case, where the block is a prefix. Suppose the block ends at the $i$-th closing bracket.
    546 
    547 1. Perform the operation on closing brackets $1, 2, \dots, i-1$, in this order. Each operation deletes a $\texttt{)}$ and sends its $\texttt{(}$ to the front, which is still inside the prefix. After $i-1$ operations, the first $i$ closing brackets have collapsed into a single block of $c[1] + \dots + c[i]$ opening brackets.
    548 2. We have $k - (i-1)$ operations left. Each one, applied to a $\texttt{()}$ outside the prefix, sends a new $\texttt{(}$ to the front and extends the block by $1$. The block can never exceed $m$, the total number of $\texttt{(}$.
    549 
    550 Hence, for every $i$ with $i - 1 \le k$, a prefix achieves $\min\bigl(m,\; c[1] + \dots + c[i] + k - (i-1)\bigr)$.
    551 
    552 Now let's look at the second case, where the block is a window in the middle. Suppose the block consists of closing brackets $l, \dots, r$ with $l \gt 1$. Merging it takes $r - l$ operations, so we need $r - l \le k$. Operations outside the window only add $\texttt{(}$ at the front, which cannot help a block that is not a prefix, so all operations should be spent on the window. Each operation inside the window sends one $\texttt{(}$ out of the window, so each removed $\texttt{)}$ costs the window one $\texttt{(}$. The size of the merged block is therefore
    553 
    554 $\sum_{j=l}^{r} c[j] - (r - l) = \sum_{j=l}^{r} \left(c[j] - 1\right) + 1,$
    555 
    556 where the $+1$ appears because the last closing bracket $r$ is not operated on.
    557 
    558 Define $\text{psum}[i] = \sum_{j \le i} (c[j] - 1)$ with $\text{psum}[0] = 0$. The best window ending at $r$ has value
    559 
    560 $\text{psum}[r] - \min_{\max(0,\, r-k-1) \,\le\, p \,\le\, r-1} \text{psum}[p] + 1,$
    561 
    562 where $p = l - 1$. Since $c[j] - 1$ can be negative, the best window is not always as long as allowed, and this is handled correctly by taking the minimum over the whole range of allowed $p$. A sliding-window minimum (monotonic deque) computes it in $\mathcal{O}(n)$ total.
    563 
    564 **Code (C++)**
    565 
    566 ```
    567 #include <bits/stdc++.h>
    568 
    569 using namespace std;
    570 #define int long long
    571 
    572 void solve() {
    573     int n, k;
    574     cin >> n >> k;
    575     string s;
    576     cin >> s;
    577 
    578     int m = n / 2;
    579     vector<int> c;
    580     c.push_back(0);
    581     
    582     int run = 0;
    583     for(int i = 0; i < n; i++) {
    584         if(s[i] == '(') run++;
    585         else {
    586             c.push_back(run);
    587             run = 0;
    588         }
    589     }
    590 
    591     int mx = 0, cur = 0;
    592     for(int i = 1; i <= m; i++) {
    593         cur += c[i];
    594         if(i - 1 <= k) mx = max(mx, min(m, cur + k - (i - 1)));
    595     }
    596 
    597     vector<int> a(m + 1), pre(m + 1);
    598     for(int i = 1; i <= m; i++) {
    599         a[i] = c[i] - 1;
    600         pre[i] = pre[i - 1] + a[i];
    601     }
    602 
    603     deque<int> dq;
    604     for(int y = 1; y <= m; y++) {
    605         int x = y - 1;
    606         while(!dq.empty() && pre[dq.back()] >= pre[x]) dq.pop_back();
    607         dq.push_back(x);
    608         while(!dq.empty() && dq.front() < y - (k + 1)) dq.pop_front();
    609         mx = max(mx, min(m, pre[y] - pre[dq.front()] + 1));
    610     }
    611 
    612     cout << mx << "\n";
    613 }
    614  
    615 signed main() {
    616     int t;
    617     cin >> t;
    618     while(t--) solve();
    619 }
    620 ```
    621 
    622 **Rate The Problem!**
    623 
    624 * Good Problem
    625 * Okay Problem
    626 * Bad Problem
    627 * Didn't Solve
    628 
    629 [2261F1 - Plegma II: Ask Me Any Cell (Easy Version)](/contest/2261/problem/F1)
    630 
    631 Author, Preparation, Editorial: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")
    632 
    633 **Hint 1**
    634 
    635 Solve in 1D: the grid is one row and $n$ columns, and $k = n$.
    636 
    637 **Hint 2**
    638 
    639 Extend your 1D solution to 2D.
    640 
    641 **Solution**
    642 
    643 Note that Circuity must take one of four actions. It would be great if we would use $S$ to always send a $2$ bit integer, regardless of how big the subgrid is.
    644 
    645 First, let's see how to solve the $1$-dimensional version: if we only have a single row. We must send a $1$ bit integer (delete left or right). The best way to do this is using parity. For example, if the parity is odd, then do action $\texttt{L}$, if the parity is even do action $\texttt{R}$. Then, the construction would be quite simple:
    646 
    647 * If the target cell is not cell $1$, then place all $0$s, except for the cell to the left of the target cell. For example, if the target cell is cell $4$, we would use the grid $\texttt{001000...}$. The idea is that when a $1$ is removed, the parity changes, so our direction does too.
    648 * Obviously, if the target cell is cell $1$, send a row full of $0$s.
    649 
    650 Here, we would use $A = \texttt{RLRL...}$ (though we only ever use indices $0$ and $1$).
    651 
    652 Extend to full grid:
    653 
    654 We use two phases. In the first phase, we locate the target's row. In the second phase, we implement the 1D solution and we are done.
    655 
    656 Note that the 1D solution only uses at most one $1$. So the next idea is to use a lot of $1$s to identify whether we are in the first phase or the second phase of the solution. Specifically:
    657 
    658 * If there are $S = 0$ or $S = 1$, we are in phase $2$ of solution (1D),
    659 * If $S \gt 1$, we are in phase $1$ of solution ($2D$) and need to remove either $\texttt{U}$ or $\texttt{D}$.
    660 
    661 For phase 1, we will again use parity in the exact same way as the 1D solution. Note that a row full of $1$s has an even amount of $1$s and does not affect parity. If $S$ is odd, we remove the up row, otherwise the down row. To do this, first we fix the target row as we would fix it in the 1D version. Then, depending on whether we had to use one $1$ or no $1$s, we can place two $0$s appropriately on the row below and on the row above.
    662 
    663 For example, if the target cell is $(2, 2)$, we would use something like:
    664 
    665 $\texttt{1111111...}$ (even sum)
    666 
    667 $\texttt{1000000...}$ (odd sum)
    668 
    669 $\texttt{0111111...}$ (odd sum)
    670 
    671 $\texttt{1111111...}$ (even sum)
    672 
    673 $\texttt{...}$ (even sum)
    674 
    675 Since the sum is even, we keep removing from below until we remove row $3$. The parity flips, so now we remove from the top. Then we are left with a single row with only one $1$ and so we use the 1D solution.
    676 
    677 Another example, if the target cell is $(2, 1)$:
    678 
    679 $\texttt{01111...}$ (odd sum)
    680 
    681 $\texttt{00000...}$ (even sum)
    682 
    683 $\texttt{11111...}$ (even sum)
    684 
    685 $\texttt{...}$ (even sum)
    686 
    687 If the target is cell $(1, 2)$:
    688 
    689 $\texttt{10000...}$
    690 
    691 $\texttt{01111...}$
    692 
    693 $\texttt{11111...}$
    694 
    695 $\texttt{...}$
    696 
    697 If it is cell $(1, 1)$:
    698 
    699 $\texttt{00000...}$
    700 
    701 $\texttt{11111...}$
    702 
    703 $\texttt{11111...}$
    704 
    705 $\texttt{...}$
    706 
    707 And so on. Note that the only special cases are when $r = 1$ or $r = n$, which are very easy to take care of. This solution uses at most $N+1$ zeros.
    708 
    709 Also, $A$ looks something like $\texttt{RLDUDUDUDU...}$, so implementation should be quite simple.
    710 
    711 **Code**
    712 
    713 ```
    714 #include <bits/stdc++.h>
    715 using namespace std;
    716 
    717 void solve_ez() {
    718     cout << "001\n101\n111\n\n";
    719     cout << "100\n110\n011\n\n";
    720     cout << "111\n010\n010\n\n";
    721     cout << "111\n111\n110\n\n";
    722     cout << "111\n100\n010\n\n";
    723     cout << "111\n011\n000\n\n";
    724     cout << "000\n110\n000\n\n";
    725     cout << "111\n111\n111\n\n";
    726     cout << "110\n111\n011\n\n";
    727     cout << "RDUDLLRURU\n";
    728 }
    729 
    730 void encode(int n, int r, int c) {
    731     vector<vector<int>> g(n+1, vector<int>(n+1, 1));
    732     for (int i = 1; i <= n; i++) g[r][i] = 0;
    733     if (c > 1) {
    734         g[r][c-1] = 1;
    735         if (r < n) g[r+1][1] = 0;
    736     }
    737     else {
    738         if (r > 1) g[r-1][1] = 0;
    739     }
    740     for (int i = 1; i <= n; i++) {
    741         for (int j = 1; j <= n; j++) {
    742             cout << g[i][j];
    743         }
    744         cout << "\n";
    745     }
    746     cout << "\n";
    747 }
    748 
    749 int main() {
    750     ios_base::sync_with_stdio(0);
    751     cin.tie(0);
    752     int n; cin >> n;
    753     if (n == 3) {
    754         solve_ez();
    755         return 0;
    756     }
    757     for (int r = 1; r <= n; r++) {
    758         for (int c = 1; c <= n; c++) {
    759             encode(n, r, c);
    760         }
    761     }
    762     cout << "RL";
    763     for (int s = 2; s <= n*n; s++) {
    764         if (s & 1) cout << "U";
    765         else cout << "D";
    766     }
    767     cout << "\n";
    768 }
    769 ```
    770 
    771 **Rate The Problem!**
    772 
    773 * Good Problem
    774 * Okay Problem
    775 * Bad Problem
    776 * Didn't Solve
    777 
    778 [2261F2 - Plegma II: Ask Me Any Cell (Hard Version)](/contest/2261/problem/F2)
    779 
    780 Author, Preparation, Editorial: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")
    781 
    782 **Hint 1**
    783 
    784 The answer is $f(n) = 3$ for every $n \ge 3$.
    785 
    786 **Hint 2**
    787 
    788 Circuity only sees $S = hw - z$, where $h \times w$ is the current rectangle and $z$ the number of zeros in it. The rectangle shrinks in a predictable way, so the number of zeros is the only thing you really control: think of it as a mode that you can switch down at any time by putting a zero into the strip that is about to be deleted.
    789 
    790 **Solution**
    791 
    792 Let us first understand what Circuity actually sees. At any moment it looks at some $h \times w$ rectangle; if this rectangle contains $z$ zeros, it senses $S = hw - z$ and performs $A_S$. The pair $(h, w)$ changes in a completely predictable way along any route, so the only thing Verity really controls is $z$. Zeros never appear, and a zero disappears exactly when the strip containing it is deleted. This suggests flipping the point of view: instead of designing grids, we design a *route* (which strips are deleted and in which order) together with a *schedule* telling how many zeros should be present before each move. Any non-increasing schedule can be realised. Whenever the count has to drop, we put the extra zeros into the strip that the current move deletes (deleted strips are disjoint, so there is always room), and if one zero is supposed to survive until the end, we put it into the target cell. So the number of zeros is a "mode" that we can switch down whenever we like, and the decoder reads the mode through $S$. From now on we only talk about routes and schedules. We write $\texttt{U}, \texttt{D}, \texttt{L}, \texttt{R}$ for deleting the top row, bottom row, left column and right column, and we will use repeatedly that a corner of the grid stays the same corner of every rectangle that contains it; for example, an execution whose target is a top corner can never perform $\texttt{U}$.
    793 
    794 The answer is $f(n) = 3$ for all $n \ge 3$. We first show how to do it with three zeros and then why two are not enough.
    795 
    796 **Upper bound: three zeros suffice.**
    797 
    798 The natural plan is to fix the rows first and the columns afterwards. While the rectangle is $h \times n$, three zeros give $S = nh - 3$ and two zeros give $S = nh - 2$; these values are different for different $h$, so we can simply declare that three zeros mean $\texttt{U}$ and two zeros mean $\texttt{D}$, and Verity can move the top or the bottom border as he likes by choosing when to drop the third zero.
    799 
    800 The column stage is where one has to be a bit careful. In an $h \times w$ rectangle with $z$ zeros we sense $hw - z$, and we again want two modes, one for $\texttt{L}$ and one for $\texttt{R}$, whose values never coincide for different widths. If we shrank all the way down to one row this would fail: $1 \times w$ with two zeros and $1 \times (w - 1)$ with one zero both give $S = w - 2$. With three rows there is no such problem, because $3w - 3$, $3w - 2$ and $3w - 1$ have different remainders modulo $3$, so three different modes fit without any conflict. This is why we stop the vertical stage at three rows, and it remains to understand what a $3 \times 1$ column can do with the small values $S \in {0, 1, 2}$.
    801 
    802 If the column contains two zeros, it senses $1$. We set $A_1 = \texttt{U}$; the remaining $2 \times 1$ column contains two zeros ($S = 0$) or one ($S = 1$), and with $A_0 = A_1 = \texttt{U}$ the bottom cell survives either way. If the column contains one zero, it senses $2$. We set $A_2 = \texttt{D}$; the remaining $2 \times 1$ column contains one zero ($S = 1$, move $\texttt{U}$, the middle cell survives) or none ($S = 2$, move $\texttt{D}$, the top cell survives). So entering the final column with two zeros means "bottom cell", and entering it with one zero lets us choose between the top and the middle cell. To enter with two zeros, the column stage must perform $\texttt{R}$ first with three zeros and $\texttt{L}$ afterwards with two; to enter with one zero, it performs $\texttt{L}$ first with two zeros and $\texttt{R}$ afterwards with one. Altogether the decoder is
    803 
    804 $A_0 = A_1 = \texttt{U}$, $A_2 = \texttt{D}$; $A_{3w-3} = \texttt{R}$, $A_{3w-2} = \texttt{L}$, $A_{3w-1} = \texttt{R}$ for $2 \le w \le n$; $A_{nh-3} = \texttt{U}$, $A_{nh-2} = \texttt{D}$ for $4 \le h \le n$,
    805 
    806 and everything else is arbitrary. The three groups use $S \in {0, 1, 2}$, $3 \le S \le 3n - 1$ and $S \ge 4n - 3$, and $4n - 3 \gt 3n - 1$ for $n \ge 3$, so nothing overlaps.
    807 
    808 Now the encoding of a target $(r, c)$ just follows this plan. Let $a = \min(r - 1, n - 3)$ and $p = r - a$. We first perform $\texttt{U}$ $a$ times with three zeros and then $\texttt{D}$ $n - 3 - a$ times with two zeros, which leaves exactly the rows $a + 1, a + 2, a + 3$, and the target is the $p$-th of them; by the choice of $a$ we have $p \in {1, 2, 3}$, and $p = 3$ happens only for $r = n$. If $p \le 2$ we perform $\texttt{L}$ $c - 1$ times with two zeros, then $\texttt{R}$ $n - c$ times with one zero, and we are in a $3 \times 1$ column with one zero: we perform $\texttt{D}$, dropping the zero if $p = 1$ and keeping it if $p = 2$, and the last move finishes in the right cell as explained above. If $p = 3$ we perform $\texttt{R}$ $n - c$ times with three zeros, then $\texttt{L}$ $c - 1$ times with two zeros, and the column with two zeros ends in the bottom cell by itself. For $n = 3$ the vertical stage is empty and everything else is identical. Every schedule starts with at most three zeros, so $f(n) \le 3$.
    809 
    810 **Lower bound: two zeros are not enough.**
    811 
    812 With at most two zeros there are only three modes, and the trouble comes from the very end of the execution: the last few moves of every target sense tiny values of $S$, and the same $A_1, A_2, \dots$ have to serve targets lying in different directions. We make this precise by proving a statement that is much stronger than what we need: for any $n \ge 2$ and any decoder, it is impossible to encode all four corners of the grid with at most two zeros each. We call the four executions TL, TR, BL, BR after their target corners, and we say that an execution is $2$-dimensional while its rectangle has $h, w \ge 2$.
    813 
    814 **Proof**
    815 
    816 Disclaimer: It should be intuitive that $2$ is insufficient due to the corners, but here's the whole proof for fun. *Definitely* written by me without any help from any entities whatsoever...
    817 
    818 Assume that all four corners are reachable. Rotating the whole picture if necessary, we may assume $A_2 = \texttt{U}$. The strategy is to look at the executions near their end, where the sensed values are small, and to pin down $A_1, \dots, A_8$ one after another until the bottom-right corner becomes impossible.
    819 
    820 Consider TL (the same reasoning works for TR). It can never sense $S = 2$, because $\texttt{U}$ would kill its target. Before its last move the rectangle has two cells, so there $S \le 2$ and hence $S \le 1$. Take the first moment at which $S \le 1$. The previous value was neither $2$ nor at most $1$, so it was at least $3$, which means that the move in between removed at least two ones. Such a move is only possible from a $2$-dimensional rectangle, and the new rectangle contains at most two zeros and at most one $1$, so at most three cells. Going through the sizes, either a $2 \times 2$ with one zero ($S = 3$) became a two-cell rectangle keeping its zero, or a $3 \times 2$ or $2 \times 3$ with two zeros ($S = 4$) became a three-cell rectangle keeping both zeros; in both cases the new value is exactly $S = 1$. So both TL and TR execute $A_1$ inside a $1$-dimensional rectangle. The only action that kills neither top corner is $\texttt{D}$, hence $A_1 = \texttt{D}$, and since $\texttt{D}$ must be legal there, that rectangle is a column. Therefore the move into it deleted a column of a $2 \times 2$ (sensing $3$) or of a $3 \times 2$ (sensing $4$); for TL this move is $\texttt{R}$ and for TR it is $\texttt{L}$, so ${A_3, A_4} = {\texttt{L}, \texttt{R}}$. Reflecting left and right if necessary, $A_3 = \texttt{L}$ and $A_4 = \texttt{R}$. But now TL cannot use the $2 \times 2$ option, since $A_3 = \texttt{L}$ kills it, and we obtain the key fact $(\ast)$: *TL starts with two zeros, keeps both of them until it reaches a $3 \times 2$ rectangle, and then plays $A_4 = \texttt{R}$*. For $n = 2$ this is already impossible, so from now on $n \ge 3$.
    821 
    822 Before going on, let us record what the four known actions imply for executions with few zeros. First, consider an execution with no zeros at all that starts from a $2$-dimensional rectangle. In a zero-free row or column of length at least $3$ it would sense both $3$ and $2$, but $A_3 = \texttt{L}$ and $A_2 = \texttt{U}$ cannot both be legal in the same row or column. So the execution first becomes $1$-dimensional as a two-cell rectangle, which must be a column because $A_2 = \texttt{U}$, and its bottom cell survives; the rectangle just before that is an all-ones $2 \times 2$ in which $A_4 = \texttt{R}$ keeps the left column. We get fact (A): *a zero-free execution from a $2$-dimensional rectangle can only end in the bottom-left corner of that rectangle, and it passes through an all-ones $2 \times 2$.*
    823 
    824 Next, executions with at most one zero. A row of length at least $2$ fails, because it eventually senses $1$ or $2$ and both $\texttt{D}$ and $\texttt{U}$ are illegal in a row. A column of height at least $4$ fails, because it senses $3$ at some point and $\texttt{L}$ is illegal in a column. A column of height $3$ cannot end in its top cell: with one zero it senses $2$ and plays $\texttt{U}$, with no zero it senses $3$. Finally, by (A), an execution with one zero whose target is a right corner cannot afford to lose its zero while it is still $2$-dimensional. Put together, this is fact (B), and it has two consequences we will use: *a one-zero execution to TR must reach a $2 \times 2$ with one zero and then play $\texttt{L}$, and a one-zero execution to BR enters its final column at height $2$ or $3$.* One more small fact (C): *if a one-zero execution aiming at a right corner is in a $2 \times w$ rectangle, then $A_{2j-1} = \texttt{L}$ for every $2 \le j \le w$*, because it cannot delete a row (that would leave a row of length at least $2$), it cannot play $\texttt{R}$, and it keeps its zero, so in each $2 \times j$ it senses $2j - 1$ and has to play $\texttt{L}$.
    825 
    826 Now we can determine how many zeros each corner uses. Two opposite corners cannot start with the same number of zeros, because they would sense the same $S$ at the start and the common first move would kill one of them. More generally, two executions that are in the same state (same rectangle, same number of zeros) make the same move, so two executions can only diverge at a move where one of them loses a zero. By $(\ast)$ TL uses two zeros, so BR does not, and BR cannot use zero zeros by (A); hence BR uses exactly one zero. If TR also used one zero, then TR and BR would both keep their zero while $2$-dimensional, so they would make identical moves, which can only be $\texttt{L}$; they would enter a column of height $n \ge 3$ with at most one zero, and by (B) TR cannot survive that. Hence TR uses exactly two zeros, and consequently its opposite corner BL uses at most one. Finally, TL and TR both start with two zeros and move identically (only $\texttt{D}$ is allowed, so the width stays $n \ge 3$) until one of them loses a zero; by $(\ast)$ it is not TL, and TR cannot lose both zeros by (A). So right after that move we have a successful one-zero TR execution starting from an $h \times n$ rectangle, and $h \ge 3$ because TL still has to reach a $3 \times 2$.
    827 
    828 This one-zero TR execution determines $A_5$. By (B) it cannot enter a column while its height is at least $3$, so at some point it goes from height $3$ to height $2$ at some width $w \ge 2$. If $w = 2$ this is a $3 \times 2$ with one zero, $S = 5$, and the move is $\texttt{D}$; if $w \ge 3$ it then lives in a $2 \times w$ strip and (C) gives $A_5 = \texttt{L}$. So $A_5 \in {\texttt{D}, \texttt{L}}$. On the other hand BR, which has one zero, either goes from height $3$ to $2$ while $2$-dimensional, which at width $2$ needs $A_5 = \texttt{U}$ and at width at least $3$ gives $A_5 = \texttt{L}$ by (C), or it enters its final column at height $3$, i.e. from a $3 \times 2$ with one zero, which needs $A_5 = \texttt{L}$. So $A_5 \in {\texttt{U}, \texttt{L}}$, and together $A_5 = \texttt{L}$.
    829 
    830 The next value to look at is $A_6$, and we claim $A_6 \in {\texttt{U}, \texttt{R}}$. Suppose not. By (A), a zero-free execution starting from a $2$-dimensional rectangle of width at least $3$ has to enter its all-ones $2 \times 2$ from an all-ones $3 \times 2$ by $\texttt{U}$ or from an all-ones $2 \times 3$ by $\texttt{R}$, both with $S = 6$, which is now impossible; a zero-free row of length at least $3$ fails as well. So under our assumption no zero-free execution from a rectangle of width at least $3$ can succeed. Then BL must use exactly one zero, and BL and BR move identically (only $\texttt{U}$, so the width stays $n \ge 3$) until one of them loses its zero, which has to happen while they are $2$-dimensional since a $1 \times n$ row fails. But the execution that loses its zero becomes a zero-free execution of width $n \ge 3$, which we have just excluded. This contradiction proves $A_6 \in {\texttt{U}, \texttt{R}}$.
    831 
    832 From here $A_7$ and $A_8$ follow quickly. By $(\ast)$, TL reaches a $3 \times 2$ with two zeros, and the rectangle before it is either a $4 \times 2$, sensing $6$ and needing $\texttt{D}$, which we just excluded, or a $3 \times 3$, sensing $7$ and needing $\texttt{R}$. So $A_7 = \texttt{R}$. Going back to the one-zero TR execution and the width $w$ at which it goes from height $3$ to $2$: $w = 2$ would need $A_5 = \texttt{D}$, but $A_5 = \texttt{L}$, and $w \ge 4$ would need $A_7 = \texttt{L}$ by (C), but $A_7 = \texttt{R}$. So $w = 3$, the rectangle is a $3 \times 3$ with one zero, it senses $8$, and the move is $\texttt{D}$. So $A_8 = \texttt{D}$.
    833 
    834 Now BR has nowhere to go. It has exactly one zero, and every move decreases $h + w$ by one, from $2n \ge 6$ down to $2$, so at some moment $h + w = 6$. By (B) this rectangle is not a $1 \times 5$ or $5 \times 1$, so it is a $2 \times 4$, a $3 \times 3$ or a $4 \times 2$, and it still contains the zero. It therefore senses $7$, $8$ or $7$ and performs $A_7 = \texttt{R}$, $A_8 = \texttt{D}$ or $A_7 = \texttt{R}$, each of which kills the bottom-right corner. This contradiction finishes the proof.
    835 
    836 So with two zeros some corner is always unreachable, which gives $f(n) \ge 3$, and together with the construction $f(n) = 3$. The solution runs in $O(n^3)$, which is just the size of the output.
    837 
    838 **Code**
    839 
    840 ```
    841 #include <bits/stdc++.h>
    842 using namespace std;
    843  
    844 int n;
    845 string mv;
    846 vector<int> zc;
    847  
    848 void add(char ch, int cnt, int z) {
    849     for (int i = 0; i < cnt; i++) {
    850         mv += ch;
    851         zc.push_back(z);
    852     }
    853 }
    854  
    855 int route(int r, int c) {
    856     mv = "";
    857     zc.clear();
    858     int up = min(r - 1, n - 3);
    859     add('U', up, 3);
    860     add('D', n - 3 - up, 2);
    861     int p = r - up;
    862     if (p == 3) {
    863         add('R', n - c, 3);
    864         add('L', c - 1, 2);
    865         add('U', 2, 2);
    866         return 1;
    867     }
    868     add('L', c - 1, 2);
    869     add('R', n - c, 1);
    870     add('D', 1, 1);
    871     if (p == 1) {
    872         add('D', 1, 0);
    873         return 0;
    874     }
    875     add('U', 1, 1);
    876     return 1;
    877 }
    878  
    879 int main() {
    880     cin >> n;
    881     for (int r = 1; r <= n; r++) {
    882         for (int c = 1; c <= n; c++) {
    883             int last = route(r, c);
    884             vector<string> g(n, string(n, '1'));
    885             int x1 = 0, x2 = n - 1, y1 = 0, y2 = n - 1;
    886             for (int i = 0; i < (int)mv.size(); i++) {
    887                 int nxt = i + 1 < (int)mv.size() ? zc[i + 1] : last;
    888                 int k = zc[i] - nxt;
    889                 if (mv[i] == 'U') {
    890                     for (int j = 0; j < k; j++) g[x1][y1 + j] = '0';
    891                     x1++;
    892                 } else if (mv[i] == 'D') {
    893                     for (int j = 0; j < k; j++) g[x2][y1 + j] = '0';
    894                     x2--;
    895                 } else if (mv[i] == 'L') {
    896                     for (int j = 0; j < k; j++) g[x1 + j][y1] = '0';
    897                     y1++;
    898                 } else {
    899                     for (int j = 0; j < k; j++) g[x1 + j][y2] = '0';
    900                     y2--;
    901                 }
    902             }
    903             if (last) g[r - 1][c - 1] = '0';
    904             for (int i = 0; i < n; i++) cout << g[i] << '\n';
    905         }
    906     }
    907     string a(n * n + 1, 'U');
    908     a[2] = 'D';
    909     for (int w = 2; w <= n; w++) {
    910         a[3 * w - 3] = 'R';
    911         a[3 * w - 2] = 'L';
    912         a[3 * w - 1] = 'R';
    913     }
    914     for (int h = 4; h <= n; h++) {
    915         a[n * h - 3] = 'U';
    916         a[n * h - 2] = 'D';
    917     }
    918     cout << a << '\n';
    919 }
    920 ```
    921 
    922 **Rate The Problem!**
    923 
    924 * Good Problem
    925 * Okay Problem
    926 * Bad Problem
    927 * Didn't Solve
    928 
    929 [2261G - 1 2 3 and XOR, Where Did Everybody Go?](/contest/2261/problem/G)
    930 
    931 Author, Preparation, Editorial: [chromate00](/profile/chromate00 "Expert chromate00")
    932 
    933 **Hint 1**
    934 
    935 You do not need to know the entire array $a$ to find $f(a)$. In fact, you can compute $f(a)$ by only knowing the XOR and AND over elements $a$.
    936 
    937 **Hint 2**
    938 
    939 Finding how many values XOR $x$ lie in $[l,r]$ is a simple trie problem. Solving this over a prefix is also simple due to offline processing or persistence.
    940 
    941 **Hint 3**
    942 
    943 Prefix ANDs of an array contain very few values, and they can be maintained efficiently even if we add values in the front.
    944 
    945 **Solution**
    946 
    947 Let's first consider how $f(a)$ for a static array $a$ is calculated.
    948 
    949 For some $0 \le b \lt 25$, let's assume the $b$-th binary digit of the XOR is $1$, but the same binary digit of some element is $0$. Then, we can increment that element until that digit becomes $1$, and then the $b$ lowest bits of the new values would be $0$ so we can change all lower digits of the XOR to $0$ as well. Therefore, assuming the XOR of the array was $X$ and the AND of the array was $A$, the following pseudocode accurately calculates $f(a)$:
    950 
    951 ```
    952 X = xor(a)
    953 A = and(a)
    954 for bit from 24 to 0:
    955   if((X&(1<<bit)) and !(A&(1<<bit))):
    956     break
    957   ans+=X&(1<<bit)
    958 return ans
    959 ```
    960 
    961 We denote the value returned by the pseudocode as $g(X,A)$. Let $P_i = a_1 \oplus \ldots \oplus a_i$ (with $P_0 = 0$), so the subarray $[l, r]$ has XOR $P_r \oplus P_{l-1}$, and $A(l, r)$ denotes its AND. We want to sweep $r$ from $1$ to $n$ and compute $\sum_{l \le r} g(P_r \oplus P_{l-1}, A(l, r))$ for each $r$.
    962 
    963 We fix $r$ first. As $l$ decreases, $A(l,r)$ can only lose bits, so there are at most $\log A + 1$ distinct values of $A(l,r)$. We call the blocks of contiguous $l$ whose $A(l,r)$ are identical a *batch*. $A$ is fixed in a batch, so we need $\sum_{q \in Q} g(P_r \oplus q, A)$ where $Q$ is the multiset of $P_{l-1}$ over all $l$ in the batch.
    964 
    965 For each batch, insert every $q \in Q$ into a binary trie from the highest bit down, but walk it differently depending on $A$:
    966 
    967 * at a bit where $A$ has a $1$, every $q$ goes to the same child, and that child records how many inserted $q$ have a $1$ at this bit;
    968 * at a bit where $A$ has a $0$, $q$ goes to the child given by its own bit, as in an ordinary trie.
    969 
    970 To evaluate the sum, walk down with $P_r$. At a bit $b$ where $A$ has a $1$, the bit of $X = P_r \oplus q$ is $1$ exactly when $q$'s bit differs from $P_r$'s, so we add $2^b$ times the number of such $q$ below the current node, which the recorded count gives directly. At a bit where $A$ has a $0$, every $q$ whose bit differs from $P_r$'s makes $X$'s bit $1$ and stops contributing, so we only continue into the child matching $P_r$'s bit (and stop if it does not exist). This is a single root-to-leaf path, so each batch is answered in $O(\log A)$.
    971 
    972 When the right endpoint moves from $r$ to $r+1$, we maintain the batches as follows.
    973 
    974 1. every batch's AND becomes $A$ AND $a_{r+1}$; a batch whose AND changed is rebuilt, because its trie depends on $A$;
    975 2. adjacent batches that now have equal ANDs are merged, inserting the values of the smaller one into the trie of the larger one;
    976 3. a new batch ${r + 1}$ with AND $a_{r+1}$ and $Q = {P_r}$ is added (or $P_r$ joins the last batch if its AND equals $a_{r+1}$).
    977 
    978 The AND of a fixed left endpoint loses a bit every time it changes, so each value is rebuilt at most $\log A$ times, for $O(n \log^2 A)$ in total. By small-to-large, each value is moved at most $\log n$ times, for $O(n \log n \log A)$. Each step queries $O(\log A)$ batches in $O(\log A)$ each. This is $O(n \log A (\log n + \log A))$ time and $O(n \log A)$ memory.
    979 
    980 **Code**
    981 
    982 ```
    983 #include <bits/stdc++.h>
    984 
    985 using i64 = long long;
    986 
    987 constexpr int B = 25;
    988 
    989 int cnt[1 << B];
    990 
    991 void solve() {
    992     int n;
    993     std::cin >> n;
    994     std::vector<int> a(n);
    995     for (int i = 0; i < n; i++) std::cin >> a[i];
    996     i64 ans = 0;
    997     std::vector next(n + 1, std::array<int, B>());
    998     std::vector ord(n, std::array<char, B>());
    999     next[n].fill(n);
   1000     for (int i = n - 1; i >= 0; i--) {
   1001         next[i] = next[i + 1];
   1002         for (int b = 0; b < B; b++) if (~a[i] >> b & 1) next[i][b] = i;
   1003         std::iota(ord[i].begin(), ord[i].end(), 0);
   1004         std::sort(ord[i].begin(), ord[i].end(), [&](char x, char y) { return next[i][x] < next[i][y]; });
   1005     }
   1006     std::vector<std::vector<std::pair<int, int>>> occ(n + 1);
   1007     for (int b = 0; b < B; b++) {
   1008         int c = 0;
   1009         for (int i = n - 1; i >= 0; i--) {
   1010             c ^= a[i];
   1011             if (a[i] >> b & 1) {
   1012                 int v = 0;
   1013                 for (int j = b; j < B; j++) if (next[i][j] != i) v |= 1 << j;
   1014                 for (int j = 0; j < B; ) {
   1015                     int k = j;
   1016                     bool f = false;
   1017                     while (k < B && next[i][ord[i][j]] == next[i][ord[i][k]]) {
   1018                         if (ord[i][k] >= b) f = true;
   1019                         k++;
   1020                     }
   1021                     if (!f) {
   1022                         j = k;
   1023                         continue;
   1024                     }
   1025                     if (next[i][ord[i][j]] != i) {
   1026                         occ[i].emplace_back((c ^ v) >> b, 1);
   1027                         occ[next[i][ord[i][j]]].emplace_back((c ^ v) >> b, -1);
   1028                     }
   1029                     while (j < k) {
   1030                         if (v >> ord[i][j] & 1) v ^= 1 << ord[i][j];
   1031                         j++;
   1032                     }
   1033                     if (~v >> b & 1) break;
   1034                 }
   1035             }
   1036         }
   1037         c = 0;
   1038         for (int i = n - 1; i >= 0; i--) {
   1039             cnt[c >> b]++;
   1040             c ^= a[i];
   1041             for (auto [x, m] : occ[i]) {
   1042                 ans += 1LL * cnt[x] * m * (1 << b);
   1043             }
   1044         }
   1045         c = 0;
   1046         for (int i = n - 1; i >= 0; i--) {
   1047             cnt[c >> b] = 0;
   1048             c ^= a[i];
   1049         }
   1050         for (int i = 0; i <= n; i++) occ[i].clear();
   1051     }
   1052     std::cout << ans << "\n";
   1053 }
   1054 
   1055 int main() {
   1056     std::ios::sync_with_stdio(0);
   1057     std::cin.tie(0);
   1058     
   1059     int t;
   1060     std::cin >> t;
   1061     while (t--) solve();
   1062 }
   1063 ```
   1064 
   1065 **Rate The Problem!**
   1066 
   1067 * Good Problem
   1068 * Okay Problem
   1069 * Bad Problem
   1070 * Didn't Solve
   1071 
   1072 [2261H - Oh Tree Tree Tree, No Need to Leave](/contest/2261/problem/H)
   1073 
   1074 Author & Editorial: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")   
   1075  Preparation: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv") & [ttamx](/profile/ttamx "Grandmaster ttamx")
   1076 
   1077 **Hint 1**
   1078 
   1079 The solution is extremely simple.
   1080 
   1081 **Hint 2**
   1082 
   1083 Read up on hamming codes if you do not know them.
   1084 
   1085 **Solution**
   1086 
   1087 It is actually possible to restore the correct order of the bits, regardless of how many nodes are flipped. This can be done in the following strategy:
   1088 
   1089 * Isabel will place the string on the tree using a DFS. Starting from node $1$, whenever she places a $0$ she recurses to the left child, and whenever she places a $1$ she recurses to the right child. The exception is of course at a leaf node, in which case she always backtracks.
   1090 * Tara will do the exact same, this time in order to retrieve the string (possibly with a flip at a single bit). Specifically, when she sees a $0$ she goes left and when he sees a $1$ she goes right.
   1091 
   1092 Using this strategy, Tara receives the original string with at most one flip. This is a classic problem that can be solved using hamming codes.
   1093 
   1094 **Code**
   1095 
   1096 ```
   1097 #ifdef LOCAL
   1098     #include <bits/include_all.h>
   1099 #else
   1100     #include <bits/stdc++.h>
   1101     #include <ext/pb_ds/assoc_container.hpp>
   1102     #include <ext/pb_ds/tree_policy.hpp>
   1103 #endif
   1104 
   1105 #pragma GCC target ("avx2")
   1106 #pragma GCC optimize ("Ofast")
   1107 #pragma GCC optimize ("unroll-loops")
   1108 
   1109 #define all(x) (x).begin(), (x).end()
   1110 #define rall(x) (x).rbegin(), (x).rend()
   1111 #define int long long
   1112 
   1113 using namespace std;
   1114 using namespace __gnu_pbds;
   1115 
   1116 template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
   1117 template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
   1118 template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
   1119 
   1120 typedef long long ll;
   1121 typedef long double ld;
   1122 typedef pair<int, int> pii;
   1123 
   1124 const ll mod = 998244353;
   1125 const ll inf = 1e18;
   1126 const int MAX = 2e5 + 42;
   1127 
   1128 random_device rd;
   1129 mt19937 gen(rd());
   1130 uniform_int_distribution<ll> dis(1, inf);
   1131 
   1132 void solve_first() {
   1133     int n, h;
   1134     cin >> n >> h; int m = (1 << h) - 1;
   1135     string s;
   1136     cin >> s;
   1137     s = "0" + s;
   1138 
   1139     string ans(m + 1, '0');
   1140     for(int i = 1; i <= m; i++) {
   1141         if(i & i - 1) {
   1142             int idx = i - __lg(i) - 1;
   1143             if(idx > n) continue;
   1144             ans[i] = s[idx];
   1145             for(int j = 0; j < h; j++) {
   1146                 if(i >> j & 1) ans[1 << j] ^= s[idx] & 1;
   1147             }
   1148         }
   1149     }
   1150 
   1151     string res(m + 1, '0');
   1152     int idx = 1;
   1153     function<void(int)> dfs = [&](int v) {
   1154         char cr = ans[idx++];
   1155         res[v] = cr;
   1156 
   1157         vector<int> c;
   1158         if(2 * v + 1 <= m) {
   1159             c.push_back(2 * v);
   1160             c.push_back(2 * v + 1);
   1161             if(cr & 1) swap(c[0], c[1]);
   1162         }
   1163 
   1164         for(auto to : c) dfs(to);
   1165     };
   1166     dfs(1);
   1167     res.erase(res.begin());
   1168 
   1169     cout << res << '\n';
   1170 }
   1171 
   1172 void solve_second() {
   1173     int n, h;
   1174     cin >> n >> h; int m = (1 << h) - 1;
   1175     string s;
   1176     cin >> s;
   1177     s = "0" + s;
   1178 
   1179     string res = "0";
   1180     int idx = 1;
   1181     function<void(int)> dfs = [&](int v) {
   1182         char cr = s[v];
   1183         res.push_back(cr);
   1184 
   1185         vector<int> c;
   1186         if(2 * v + 1 <= m) {
   1187             c.push_back(2 * v);
   1188             c.push_back(2 * v + 1);
   1189             if(cr & 1) swap(c[0], c[1]);
   1190         }
   1191 
   1192         for(auto to : c) dfs(to);
   1193     };
   1194     dfs(1);
   1195 
   1196     int bad = 0;
   1197     for(int i = 1; i <= m; i++) {
   1198         if(res[i] & 1) bad ^= i;
   1199     }
   1200     res[bad] ^= 1;
   1201 
   1202     string ans(n, '0');
   1203     for(int i = 1; i <= m; i++) {
   1204         if(i & i - 1) {
   1205             int idx = i - __lg(i) - 1;
   1206             if(idx > n) continue;
   1207             ans[idx - 1] = res[i];
   1208         }
   1209     }
   1210 
   1211     cout << ans << '\n';
   1212 }
   1213 
   1214 string who;
   1215 
   1216 void solve() {
   1217     if(who == "first") solve_first();
   1218     else solve_second();
   1219 }
   1220 
   1221 signed main() {
   1222     ios_base::sync_with_stdio(0); cin.tie(0);
   1223     cin >> who;
   1224     int ttt = 1;
   1225     cin >> ttt;
   1226     while(ttt--) {
   1227         solve();
   1228     }
   1229 }
   1230 ```
   1231 
   1232 **Rate The Problem!**
   1233 
   1234 * Good Problem
   1235 * Okay Problem
   1236 * Bad Problem
   1237 * Didn't Solve