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