2268.md (46489B)
1 Source: https://codeforces.com/blog/entry/157140 2 3 ### ⭐ **Hope you enjoyed the problems!** ⭐ 4 5 [2269A - SauSaGe Bank](/contest/2269/problem/A "Codeforces Round 1124 (Div. 2)") 6 7 **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") 8 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") 9 10 **Hints** 11 12 **Hint 1** 13 14 If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$. 15 16 **Hint 2** 17 18 For fixed $a+b$, is $2^a+2^b$ larger when $a,b$ are close together, or when one is as large as possible? 19 20 **Solution** 21 22 If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$. 23 24 Therefore the problem becomes: Split $n$ into exactly $k$ positive integers $a_1,\dots,a_k$, and maximize 25 26 $2^{a_1}+2^{a_2}+...+2^{a_k}$ 27 28 For fixed $a+b$, $2^a+2^b$ is larger when one of them is as large as possible. 29 30 **Proof** 31 32 Suppose two segment lengths are $a\le b$, with $a \gt 1$. Move one day from the smaller segment to the larger one: 33 34 $(a,b) \to (a-1,b+1)$ 35 36 Compare the contributions: 37 38 $2^{a-1} + 2^{b+1} - (2^a + 2^b) = 2^b - 2^{a-1} \gt 0$ 39 40 So this change always increases the answer. 41 42 Hence, in an optimal solution, we cannot have two segments with length greater than $1$. We keep transferring days from smaller segments to the largest one until all but one segment have length $1$. 43 44 Thus the optimal lengths are 45 46 $n-k+1,\underbrace{1,1,\ldots,1}_{k-1\text{ times}}$ 47 48 So the maximum amount is $2^{n-k+1}+2(k-1)$ 49 50 **Code** 51 52 ``` 53 #include <bits/stdc++.h> 54 using namespace std; 55 int main() { 56 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 57 int tc; 58 cin >> tc; 59 while(tc--) { 60 int n, k; 61 cin >> n >> k; 62 cout << (1<<(n-k+1)) + 2*(k-1) << '\n'; 63 } 64 return 0; 65 } 66 ``` 67 68 --- 69 70 [2269B - KiaKio and Squared Numbers](/contest/2269/problem/B "Codeforces Round 1124 (Div. 2)") 71 72 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") 73 **Preparation:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") 74 75 **Hints** 76 77 **Hint 1** 78 79 What is the maximum possible value of (f(x)), where (f(x)) is the sum of the squares of the decimal digits of (x)? 80 81 Notice that after just one operation, every value becomes at most (729). 82 83 **Hint 2** 84 85 Since all values eventually become small, what happens if we repeatedly apply the operation? 86 87 Try to detect the cycles of the function (f). Can two numbers that enter the same cycle still behave differently? 88 89 **Solution** 90 91 **Fact** 92 93 The only cycles of the function $f(x)$ are 94 95 $ 1 \to 1 $ 96 97 and 98 99 $ 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4. $ 100 101 Every positive integer eventually reaches exactly one of these two cycles. 102 103 **Solution** 104 105 For each initial value $a_i$, we simulate the process until it reaches one of the two cycles. 106 107 If it reaches $1$, we assign it the signature $8$. 108 109 Otherwise, suppose it takes $s$ operations to reach the element at position $k$ of the 8-cycle, where the positions are numbered from $0$ to $7$. 110 111 Its position after $t$ operations is 112 113 $ (k+t-s) \bmod 8. $ 114 115 Therefore, two numbers entering the 8-cycle will eventually have identical values at every step if and only if: 116 117 $ (k_1-s_1) \equiv (k_2-s_2) \pmod 8. $ 118 119 We use this value as the signature of each number. 120 121 Thus, two initial values are in tune if and only if their signatures are equal. 122 123 Let $cnt[x]$ be the number of elements with signature $x$. The answer is 124 125 $ \boxed{ \sum_{x=0}^{8} \frac{cnt[x](cnt[x]-1)}{2} } $ 126 127 Since every number reaches a cycle after a constant number of operations, we can calculate all signatures and count the pairs in $\mathcal{O}(n)$ time per test case. 128 129 **Code** 130 131 ``` 132 #include <bits/stdc++.h> 133 134 using namespace std; 135 136 typedef long long ll; 137 typedef long double ld; 138 typedef pair<int,int> pii; 139 typedef pair<ll,ll> pll; 140 141 #define F first 142 #define S second 143 #define endl '\n' 144 #define Mp make_pair 145 #define pb push_back 146 #define pf push_front 147 #define size(x) (ll)x.size() 148 #define all(x) x.begin(), x.end() 149 #define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n" 150 151 const int N = 2e5 + 100, lg = 18; 152 const ll Mod = 1e9 + 7; 153 const ll inf = 1e18 + 10; 154 155 // The unique non-trivial cycle of the "sum of squared decimal digits" map. 156 // 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ... 157 const ll CYC[8] = {4, 16, 37, 58, 89, 145, 42, 20}; 158 159 int t, n; 160 ll cnt[9]; 161 162 // Signature of a lighthouse: 163 // 8 -> "calm": the value reaches 1 and stays there forever. 164 // 0..7 -> "restless": the phase of the lighthouse on the 8-cycle. 165 // Two lighthouses are in tune iff their signatures are equal. 166 int sig(ll x) { 167 ll s = 0; 168 while (true) { 169 if (x == 1) return 8; 170 for (int k = 0; k < 8; k++) 171 if (x == CYC[k]) return (int)(((k - s) % 8 + 8) % 8); 172 ll y = 0; 173 while (x > 0) { ll r = x % 10; y += r * r; x /= 10; } 174 x = y; 175 s++; 176 } 177 } 178 179 void work() { 180 cin >> n; 181 182 for (int i = 0; i <= 8; i++) cnt[i] = 0; 183 184 for (int i = 1; i <= n; i++) { 185 ll a; cin >> a; 186 cnt[sig(a)] ++; 187 } 188 189 ll ans = 0; 190 for (int i = 0; i <= 8; i++) ans += cnt[i] * (cnt[i] - 1) / 2; 191 192 cout << ans << endl; 193 } 194 195 void reset_work() { 196 return; 197 } 198 199 int main() { 200 ios_base::sync_with_stdio(false), cin.tie(0); 201 202 cin >> t; 203 while (t --) { 204 work(); 205 reset_work(); 206 } 207 208 return 0; 209 } 210 ``` 211 212 --- 213 214 [2269C - K Is Important](/contest/2269/problem/C "Codeforces Round 1124 (Div. 2)") / [2268A - K Is Important](/contest/2268/problem/A "Codeforces Round 1124 (Div. 1)") 215 216 **Idea:** [eren__](/profile/eren__ "Grandmaster eren__") 217 **Preparation:** [eren__](/profile/eren__ "Grandmaster eren__") 218 219 **Hints** 220 221 **Hint 1** 222 223 Consider the special case where $2k = n$. Which elements are competing against each other to be deleted? 224 225 **Hint 2** 226 227 You can prove that for a specific index $i$, we are forced to delete exactly one element from the symmetric pair $(a_i, a_{n-i+1})$. Therefore, to maximize the sum, we should greedily take $\max(a_i, a_{n-i+1})$. 228 229 **Solution** 230 231 We can analyze the problem by splitting it into two cases based on the relationship between $2k$ and $n$: 232 233 **Case 1: $2k \le n$** The elements in the middle, where $k \le i \le n - k + 1$, are inevitably going to be deleted. No matter what sequence of operations we choose, these elements will eventually land on the $k$-th position from either the left or the right side. Thus, we unconditionally add all of them to our total sum. 234 235 After removing the middle section, we are left with a prefix of length $k-1$ and a suffix of length $k-1$. 236 237 **Proof of the pairing relation:** Notice that when the remaining array shrinks to exactly length $k + i - 1$ (for $1 \le i \le k - 1$), the $k$-th element from the left and the $k$-th element from the right correspond exactly to the original elements $a_{n-i+1}$ and $a_i$ (or what remains of their relative positions). At this specific length, the operation forces us to delete exactly one of them. 238 239 Therefore, for each $1 \le i \le k - 1$, we must choose exactly one element from the pair $(a_i, a_{n-i+1})$. To maximize our score, we greedily add $\max(a_i, a_{n-i+1})$ to our answer. 240 241 **Case 2: $2k \gt n$** This case is very similar, but the roles are inverted. The elements in the middle, where $n - k + 2 \le i \le k - 1$, are completely fixed and safe. The total length of the array will drop below $k$ before these elements can ever reach the $k$-th position from either boundary. Thus, they can *never* be deleted. 242 243 For the remaining valid elements on the two boundaries, the exact same symmetric relationship holds. We form pairs from the two ends: $(a_i, a_{n-i+1})$ for $1 \le i \le n - k + 1$. Just like in the first case, we can delete exactly one element from each pair, so we greedily add $\max(a_i, a_{n-i+1})$ to our sum. 244 245 Using two pointers (`l` and `r`) allows us to implement both cases cleanly in $\mathcal{O}(n)$. 246 247 **Code** 248 249 ``` 250 #include <bits/stdc++.h> 251 #define pb push_back 252 #define F first 253 #define S second 254 #define all(a) a.begin(),a.end() 255 #define sz(a) (int)a.size() 256 #define pii pair<ll,ll> 257 #define ll long long 258 #define ld long double 259 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++) 260 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--) 261 using namespace std ; 262 const int maxn = 5e5 + 10 ; 263 int a[maxn] ; 264 signed main(){ 265 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 266 int t ;cin >> t ; 267 while(t--){ 268 int n , k ; cin >> n >> k; 269 for(int i = 1 ;i <= n ; i++){ 270 cin >> a[i] ; 271 } 272 ll sum = 0 ; 273 vector <int> vec; 274 for(int i = 1 ; i <= n ; i++){ 275 if(i >= k && i <= n-k+1){ 276 sum += a[i] ; 277 continue ; 278 } 279 vec.pb(a[i]) ; 280 } 281 int t2 = max(0 , sz(vec)- (k-1)) ; 282 int l = 0 , r= sz(vec)-1 ; 283 while(t2--){ 284 sum += max(vec[l] , vec[r]) ; 285 l++; 286 r--; 287 } 288 cout << sum << "\n" ; 289 } 290 } 291 ``` 292 293 --- 294 295 [2269D - What a SauSaGe! It's All Meat](/contest/2269/problem/D "Codeforces Round 1124 (Div. 2)") / [2268B - What a SauSaGe! It's All Meat](/contest/2268/problem/B "Codeforces Round 1124 (Div. 1)") 296 297 **Idea:** [_R00T](/profile/_R00T "Master _R00T") 298 **Preparation:** [_R00T](/profile/_R00T "Master _R00T") 299 300 **Hints** 301 302 **Hint 1** 303 304 Write all possible values of $3k$ in binary. What property of each $a_i$ is preserved after every operation? 305 306 **Hint 2** 307 308 Show that instead of two adjacent elements, we can apply the same XOR mask to any pair $a_i,a_j$. 309 310 **Hint 3** 311 312 By combining several operations, we can XOR two chosen elements by any four-bit number with an even number of set bits. 313 314 **Hint 4** 315 316 An element with an odd number of set bits can never become All-Meat. To prove that every other element can become All-Meat, consider these two cases separately: - There is an element with odd popcount. - All elements have even popcount. 317 318 **Solution** 319 320 The possible XOR masks in one operation are: 321 322 $ 3,6,9,12,15. $ 323 324 Their binary representations are: 325 326 $ 0011,\ 0110,\ 1001,\ 1100,\ 1111. $ 327 328 All these masks have an even number of set bits. XORing a number with such a mask flips an even number of its bits, so the parity of its popcount does not change. 329 330 The All-Meat values smaller than $16$ are: 331 332 $ 0,3,6,9,12,15, $ 333 334 or in binary: 335 336 $ 0000,\ 0011,\ 0110,\ 1001,\ 1100,\ 1111. $ 337 338 They all have even popcount. Therefore, an element with odd popcount can never become All-Meat. This gives us the following upper bound: 339 340 $ \text{answer}\leq \#\{i\mid \operatorname{popcount}(a_i)\text{ is even}\}. $ 341 342 Now we prove that this upper bound can always be achieved. 343 344 First, we can apply the same mask to any two elements, not necessarily adjacent ones. Suppose we want to apply a mask to $a_i$ and $a_j$, where $i \lt j$. Apply it to every adjacent pair: 345 346 $ (i,i+1),(i+1,i+2),\ldots,(j-1,j). $ 347 348 Every element strictly between $i$ and $j$ is XORed twice, so it remains unchanged. Only $a_i$ and $a_j$ are XORed once. 349 350 We can also combine multiple operations on the same pair. The set of all four-bit values with even popcount is: 351 352 $ E=\{0,3,5,6,9,10,12,15\}. $ 353 354 All of them are already valid masks except $5$ and $10$, and: 355 356 $ 5=3\oplus6,\qquad 10=3\oplus9. $ 357 358 Thus, we can XOR any two chosen elements by any mask with even popcount. 359 360 Equivalently, if we write the array as an $n\times4$ grid of bits, we may choose any two rows and any two columns and flip the four corner bits. 361 362 We now consider two cases. 363 364 **Case 1: There is an element with odd popcount.** 365 366 Choose one such element as a buffer. 367 368 For every element $a_i$ with even popcount, XOR both $a_i$ and the buffer by $a_i$. This is possible because $a_i$ itself has even popcount. 369 370 After this operation: 371 372 $ a_i\oplus a_i=0, $ 373 374 so $a_i$ becomes All-Meat. The buffer still has odd popcount because we only XOR it with even-popcount masks. 375 376 Therefore, every element with even popcount becomes All-Meat, while the elements with odd popcount cannot contribute to the answer anyway. 377 378 **Case 2: All elements have even popcount.** 379 380 Use $a_1$ as a buffer. For every $2\leq i\leq n$, XOR $a_1$ and $a_i$ by $a_i$. This makes every $a_i$ for $i\geq2$ equal to zero. 381 382 After these operations, the array has the form: 383 384 $ [x,0,0,\ldots,0], $ 385 386 where: 387 388 $ x=a_1\oplus a_2\oplus\cdots\oplus a_n. $ 389 390 Since all original elements have even popcount, $x$ also has even popcount. If $x$ is one of: 391 392 $ 0,3,6,9,12,15, $ 393 394 then every element is already All-Meat. 395 396 The only remaining possibilities are $x=5$ and $x=10$. In both cases, apply XOR with $3$ to the first two elements: 397 398 $ (5,0)\longrightarrow(6,3), $ $ (10,0)\longrightarrow(9,3). $ 399 400 Again, every element becomes All-Meat. 401 402 Therefore, the upper bound is always achievable, and the answer is exactly: 403 404 $ \boxed{\#\{i\mid \operatorname{popcount}(a_i)\text{ is even}\}}. $ 405 406 For each update, we only need to remove the contribution of the old value and add the contribution of the new value. 407 408 The initial array is processed in $\mathcal{O}(n)$, and every update is processed in $\mathcal{O}(1)$. Therefore, the total time complexity is $\mathcal{O}(n+q)$. 409 410 **Code** 411 412 ``` 413 #include <bits/stdc++.h> 414 using namespace std; 415 416 inline bool good(int x) { 417 return __builtin_popcount(x) % 2 == 0; 418 } 419 420 int32_t main() { 421 cin.tie(0); 422 cout.tie(0); 423 ios_base::sync_with_stdio(0); 424 425 int tc; 426 cin >> tc; 427 428 while (tc--) { 429 int n, q; 430 cin >> n >> q; 431 432 vector<int> a(n); 433 int answer = 0; 434 435 for (int &x : a) { 436 cin >> x; 437 answer += good(x); 438 } 439 440 cout << answer; 441 442 while (q--) { 443 int p, x; 444 cin >> p >> x; 445 --p; 446 447 answer -= good(a[p]); 448 a[p] = x; 449 answer += good(a[p]); 450 451 cout << ' ' << answer; 452 } 453 454 cout << '\n'; 455 } 456 457 return 0; 458 } 459 ``` 460 461 --- 462 463 [2269E - KiaKio and Energy Intervals](/contest/2269/problem/E "Codeforces Round 1124 (Div. 2)") / [2268C - KiaKio and Energy Intervals](/contest/2268/problem/C "Codeforces Round 1124 (Div. 1)") 464 465 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") 466 **Preparation:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") 467 468 **Hints** 469 470 **Hint 1** 471 472 Let: 473 474 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $ 475 476 If $m=\max(a_l,a_{l+1},\ldots,a_r)$, show that the value of the interval is: 477 478 $ (p_{l-1}\oplus p_r)\mathbin{\&}m. $ 479 480 **Hint 2** 481 482 Build the maximum Cartesian tree of the original array. 483 484 What is the relation between $\operatorname{LCA}(l,r)$ and the maximum element of $a_l,a_{l+1},\ldots,a_r$? 485 486 **Hint 3** 487 488 Construct the answer greedily from the highest bit to the lowest bit. 489 490 For a candidate mask $M$, we only need to determine whether there exists an interval whose value contains every bit of $M$. 491 492 **Hint 4** 493 494 For a fixed candidate $M$, define: 495 496 $ b_i=a_i\mathbin{\&}M $ 497 498 and let $s_i$ be the prefix XOR of $b$. 499 500 An interval represented by a Cartesian-tree vertex $v$ is valid for $M$ if: 501 502 $ (a_v\mathbin{\&}M)=M $ 503 504 and: 505 506 $ s_{l-1}\oplus s_r=M. $ 507 508 **Hint 5** 509 510 Suppose the subtree of $v$ represents the segment $[L,R]$. 511 512 For an interval whose Cartesian-tree LCA is $v$, its two prefix endpoints satisfy: 513 514 $ l-1\in[L-1,v-1],\qquad r\in[v,R]. $ 515 516 Be careful with the pair $(v-1,v)$: it represents the forbidden one-element interval $[v,v]$. 517 518 **Hint 6** 519 520 Process the smaller child first, remove its prefix XORs from the frequency array, and then process the larger child. 521 522 Keep the larger side in the frequency array, iterate over the smaller side, and search for the required complementary prefix XOR. 523 524 **Solution** 525 526 Define the prefix XORs of the original array as: 527 528 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $ 529 530 Suppose we choose an interval $[l,r]$, and let: 531 532 $ m=\max(a_l,a_{l+1},\ldots,a_r). $ 533 534 Bitwise AND distributes over XOR, so: 535 536 $ \begin{aligned} &(a_l\mathbin{\&}m)\oplus (a_{l+1}\mathbin{\&}m)\oplus\cdots\oplus (a_r\mathbin{\&}m)\\ &= (a_l\oplus a_{l+1}\oplus\cdots\oplus a_r) \mathbin{\&}m\\ &= (p_{l-1}\oplus p_r)\mathbin{\&}m. \end{aligned} $ 537 538 Therefore, the answer depends only on the XOR of two prefix endpoints and the maximum of the interval. 539 540 ### Cartesian tree 541 542 Build the maximum Cartesian tree of the original array $a$. Ties may be handled in any consistent way. 543 544 This tree has two useful properties: 545 546 * The subtree of every vertex $v$ corresponds to a continuous segment $[L_v,R_v]$. 547 * For every interval $[l,r]$: 548 549 $ a_{\operatorname{LCA}(l,r)} = \max(a_l,a_{l+1},\ldots,a_r). $ 550 551 Thus, if $v=\operatorname{LCA}(l,r)$, the value of the interval is: 552 553 $ (p_{l-1}\oplus p_r)\mathbin{\&}a_v. $ 554 555 ### Constructing the answer bit by bit 556 557 Suppose some higher bits of the answer have already been fixed, and we want to test a candidate mask $M$. 558 559 The candidate is feasible if there exists an interval whose value contains every bit of $M$. 560 561 For this check, define: 562 563 $ b_i=a_i\mathbin{\&}M $ 564 565 and its prefix XORs: 566 567 $ s_0=0,\qquad s_i=b_1\oplus b_2\oplus\cdots\oplus b_i. $ 568 569 Equivalently: 570 571 $ s_i=p_i\mathbin{\&}M. $ 572 573 For an interval whose Cartesian-tree LCA is $v$, all bits of $M$ occur in its value if and only if: 574 575 $ (a_v\mathbin{\&}M)=M $ 576 577 and: 578 579 $ s_{l-1}\oplus s_r=M. $ 580 581 The second condition can be rewritten as: 582 583 $ s_r=s_{l-1}\oplus M. $ 584 585 Therefore, after fixing one endpoint, we only need a frequency array to determine whether the required other endpoint exists. 586 587 Notice that the Cartesian tree is always built from the original values. Only the prefix XORs are masked during a feasibility check. 588 589 ### Processing one Cartesian-tree vertex 590 591 Suppose the subtree of $v$ corresponds to $[L,R]$. 592 593 Every interval whose LCA is exactly $v$ can be represented by two prefix endpoints: 594 595 $ x=l-1\in[L-1,v-1], $ $ y=r\in[v,R]. $ 596 597 We need to find a pair satisfying: 598 599 $ s_x\oplus s_y=M. $ 600 601 There is one important exception. The pair: 602 603 $ (x,y)=(v-1,v) $ 604 605 represents the interval $[v,v]$, which is forbidden because the statement requires $l \lt r$. 606 607 Moreover, whenever $a_v & M=M$, this pair automatically satisfies: 608 609 $ s_{v-1}\oplus s_v=a_v\mathbin{\&}M=M. $ 610 611 So failing to exclude this exact pair would produce a false positive at every suitable vertex. 612 613 ### Small-to-large traversal 614 615 For every processed subtree $[L,R]$, we maintain the following invariant: 616 617 > The frequency array contains $s_L,s_{L+1},\ldots,s_R$. 618 619 At a vertex $v$: 620 621 1. Recursively check both child subtrees. 622 2. Keep the prefix XORs of the larger child in the frequency array. 623 3. Iterate over the endpoints belonging to the smaller side. 624 4. For every value $s_x$, check whether $s_x\oplus M$ exists on the other side. 625 5. Merge the smaller side into the frequency array. 626 627 The boundary prefix $s_{L-1}$ is inserted temporarily when needed. 628 629 The pair $(v-1,v)$ is excluded by checking one boundary endpoint before inserting the other one. Since the frequency array stores counts rather than only presence, equal prefix XOR values at different indices are still handled correctly. 630 631 Whenever an index is scanned as part of the smaller side, the size of the subtree containing it at least doubles before it can be scanned again. Hence, every index is scanned at most $\mathcal{O}(\log n)$ times. 632 633 One feasibility check takes: 634 635 $ \mathcal{O}(n\log n). $ 636 637 There are $18$ bits, so the total time complexity is: 638 639 $ \mathcal{O}(18n\log n). $ 640 641 The memory complexity is: 642 643 $ \mathcal{O}(n+2^{18}). $ 644 645 The implementation below uses an explicit stack because a Cartesian tree can have depth $n$ for a sorted array. 646 647 **Code** 648 649 ``` 650 #include <bits/stdc++.h> 651 652 using namespace std; 653 654 typedef long long ll; 655 typedef long double ld; 656 typedef pair<int,int> pii; 657 typedef pair<ll,ll> pll; 658 659 #define F first 660 #define S second 661 #define endl '\n' 662 #define Mp make_pair 663 #define pb push_back 664 #define pf push_front 665 #define size(x) (ll)x.size() 666 #define all(x) x.begin(), x.end() 667 668 const int N = 2e5 + 100, lg = 18; 669 const ll Mod = 1e9 + 7; 670 const ll inf = 1e18 + 10; 671 672 ll MOD(ll a, ll mod=Mod) { 673 a%=mod; (a<0)&&(a+=mod); return a; 674 } 675 ll poww(ll a, ll b, ll mod=Mod) { 676 ll res = 1; 677 while(b > 0) { 678 if(b%2 == 1) res = MOD(res * a, mod); 679 b /= 2; 680 a = MOD(a * a, mod); 681 } 682 return res; 683 } 684 685 int t, n, a[N], par[lg][N], pref[N], cnt[N * 2], answ = 0, maxi = 0; 686 687 int getmx(int l, int r) { 688 int res = l; 689 for(int i=lg-1; i>=0; i--) { 690 if(l + (1<<i) - 1 <= r) { 691 res = (a[par[i][l]] > a[res] ? par[i][l] : res); 692 l += (1<<i); 693 } 694 } 695 return res; 696 } 697 698 void divide(int l, int r) { 699 if(l > r) return; 700 if(l == r) { 701 cnt[pref[l]] ++; 702 return; 703 } 704 if(l == r-1) { 705 cnt[pref[l]] ++; 706 cnt[pref[r]] ++; 707 if((max(a[l], a[r]) & answ) == answ) { 708 maxi = max(maxi, pref[l-1] ^ pref[r]); 709 } 710 return; 711 } 712 713 int mid = getmx(l, r); 714 715 if(r-mid > mid-l) { 716 divide(l, mid-1); 717 for(int i=l; i<mid; i++) cnt[pref[i]] --; 718 divide(mid+1, r); 719 720 for(int i=mid-1; i>=l-1; i--) { 721 if(cnt[(answ ^ pref[i])] > 0 && (a[mid]&answ) == answ) maxi = answ; 722 if (i == mid-1) cnt[pref[mid]] ++; 723 } 724 for(int i=mid-1; i>=l; i--) cnt[pref[i]] ++; 725 } else { 726 divide(mid+1, r); 727 for(int i=mid+1; i<=r; i++) cnt[pref[i]] --; 728 divide(l, mid-1); 729 730 cnt[pref[mid-1]] --; 731 cnt[pref[l-1]] ++; 732 for(int i=mid; i<=r; i++) { 733 if(cnt[(answ ^ pref[i])] > 0 && (a[mid]&answ) == answ) maxi = answ; 734 if(i == mid) cnt[pref[mid-1]] ++; 735 } 736 cnt[pref[l-1]] --; 737 738 for(int i=mid; i<=r; i++) cnt[pref[i]] ++; 739 } 740 } 741 742 bool check() { 743 maxi = 0; 744 for(int j=1; j<=n; j++) { 745 pref[j] = pref[j-1] ^ (a[j] & answ); 746 } 747 748 divide(1, n); 749 750 for(int i=1; i<=n; i++) { 751 cnt[pref[i]] = 0; 752 } 753 754 if(maxi == answ) return 1; 755 return 0; 756 } 757 758 void work() { 759 cin>>n; 760 761 int mxtmp = 0, anstmp = 0; 762 for(int i=1; i<=n; i++) { 763 cin>>a[i]; 764 mxtmp = max(mxtmp, a[i]); 765 par[0][i] = i; 766 } 767 768 for(int i=1; i<=n; i++) anstmp ^= (a[i] & mxtmp); 769 770 for(int i=n; i>=1; i--) { 771 for(int j=1; j<lg; j++) { 772 int x = par[j-1][i], y = par[j-1][min(n, i + (1<<(j-1)))]; 773 if(a[x] > a[y]) par[j][i] = x; 774 else par[j][i] = y; 775 } 776 } 777 778 for(int i=lg-1; i>=0; i--) { 779 answ += (1 << i); 780 781 if(check() == 0) { 782 answ -= (1 << i); 783 } 784 } 785 786 cout<<max(answ, anstmp)<<endl; 787 } 788 789 void reset_work() { 790 answ = 0; 791 for(int i=1; i<=n; i++) a[i] = 0, pref[i] = 0; 792 return; 793 } 794 795 int main() { 796 ios_base::sync_with_stdio(false), cin.tie(0); 797 798 // freopen("inp.txt", "r", stdin); 799 // freopen("out-m.txt", "w", stdout); 800 801 802 cin>>t; 803 // t = 1; 804 while(t --) { 805 work(); 806 reset_work(); 807 } 808 809 return 0; 810 } 811 ``` 812 813 --- 814 815 [2269F - AghaBalaSar and Hamed](/contest/2269/problem/F "Codeforces Round 1124 (Div. 2)") / [2268D - AghaBalaSar and Hamed](/contest/2268/problem/D "Codeforces Round 1124 (Div. 1)") 816 817 **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") 818 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") 819 820 **What is AghaBalaSar?** 821 822 AghaBalaSar (آقابالاسر) is a term commonly used in the Iranian CP community for the nearest greater/smaller element on either side. 823 824 I also used it in a previous contest as well :D [2127F - Hamed and AghaBalaSar](/contest/2127/problem/F) 825 826 **Hints** 827 828 **Hint 1** 829 830 For a fixed $i$, try to describe the shape of a shortest path. In particular, how many times do we really need to move left? 831 832 **Hint 2** 833 834 For a fixed $i$, what can we say about the positions $j$ whose $f(i, j)$ are $1$, $2$, or greater than $2$? 835 836 **Solution** 837 838 The important observation is that a shortest path has the form 839 840 $L,R,R,\ldots,R,L$ 841 842 So after at most one initial left move, all right moves are forced. 843 844 Let $R_i=\text{the first }j \gt i\text{ such that }p_j \gt p_i$ or $n+1$ if it does not exist. 845 846 We split the permutation into blocks ending at positions $r$ with $R_r=n+1$, because we cannot move from one block to any of the blocks to its right. 847 848 Let $dp_i$ be the sum of distances from $i$ to all positions in the current block. 849 850 Let $x$ be the rightmost position reachable from $i$ in at most two moves. 851 852 There are two cases. 853 854 **Case 1: ($x=R[i]$)** 855 856 Then there is no way to reach anything beyond $R_i$ in two moves. 857 858 Therefore, for every $j \gt R_i$, every shortest path starts with $i\to R_i$, hence $f(i,j)=1+f(R_i,j)$. 859 860 Now compare the contributions of $i$ and $R_i$. 861 862 * For $j \lt i$, both distances are $1$. 863 * For $j=i$, we gain $-1$. 864 * For $j \gt i$, the distance from (i) is exactly one larger than the corresponding distance from $R_i$. 865 866 The total difference simplifies to $dp_i-dp_{R_i}=r-i-1$. Thus 867 868 $dp_i=dp_{R_i}+r-i-1$ 869 870 Where $r$ is the end of the current block. 871 872 **Case 2: ($x \gt R_i$)** 873 874 Now $x$ is reachable in two moves, and $x$ is the furthest position with this property. 875 876 For every $j \gt x$, $f(i,j)=2+f(x,j)$. 877 878 Why? We can reach $x$ in two moves and then follow an optimal path from $x$. Also, by definition of $x$, no position farther right can be reached from $i$ in two moves, so we cannot do better. 879 880 Thus, for everything after $x$, we can simply use $dp_x$. 881 882 It remains to handle the positions between $i$ and $x$. 883 884 Since $x$ is reachable in at most two moves, every position $j\in(i,x]$ has distance either $2$ or $3$ from $i$. 885 886 Let $c_2$ be the number of $j \in (i,x]$ such that $f(i,j)=2$. 887 888 There are $x-i-1$ positions strictly between $i$ and $x$. Among them, $c_2-1$ have distance $2$, because $x$ itself is also counted by $c_2$. Therefore the remaining $x-i-c_2$ positions have distance $3$. Comparing their contributions with $dp_x$, we get 889 890 $dp_i=dp_x+2(r-i)-2-c_2$ 891 892 So the only remaining problem is computing $x$ and $c_2$ efficiently. 893 894 **Finding the positions reachable in two moves** 895 896 A position $j \gt i$ can be reached in two moves in exactly these ways: 897 898 * $i \lt j \lt R_i$, by $i\to R_i\to j$; 899 * $j=R_{R_i}$; 900 * There is some $k\le i$ such that $R_k=j$, because we can do $i\to k\to j$. 901 902 Let $L_j$ be the minimum $k$ such that $R_k = j$, then third case is simply $L_j\le i$. 903 904 We process $i$ from right to left and maintain all positions $j$ satisfying $L_j\le i$. The rightmost marked position is exactly $x$. 905 906 **Computing $c_2$** 907 908 Among the distance-$2$ positions we have: 909 910 * $R_i-i-1$ positions between $i$ and $R_i$; 911 * $R_{R_i}$, if it exists; 912 * all currently marked positions except $R_i$. 913 914 There is one possible double count: $R_{R_i}$ may itself already be marked. 915 916 So we can compute $c_2$ by processing $i$ from right to left and maintaining all marked positions. 917 918 Complexity: $\mathcal{O}(n)$ 919 920 **Code** 921 922 ``` 923 #include <bits/stdc++.h> 924 using namespace std; 925 926 using ll = long long; 927 928 const int MXN = 1e6+5; 929 930 int n, p[MXN], R[MXN], L[MXN]; 931 ll dp[MXN]; 932 vector<int> vec[MXN]; 933 bool mark[MXN]; 934 935 void solve(int l, int r) { 936 dp[r] = r-l; 937 int lst=r, cnt=0; 938 if(L[r]!=n+1) { 939 vec[L[r]].push_back(r); 940 mark[r] = 1; 941 cnt++; 942 } 943 for(int i=r-1; i>=l; i--) { 944 while(!mark[lst]) lst--; 945 if(lst==R[i]) { 946 dp[i] = dp[R[i]] + r-l+1 - 2 - (i-l); 947 } 948 else { 949 int c1 = i-l + 1; 950 int c2 = R[i]-i-1 + (R[R[i]]!=n+1) + cnt - 1 - (R[R[i]]!=n+1 && L[R[R[i]]]<=i); 951 dp[i] = dp[lst] + 2*(r-l+1) - 3 - 2*c1 - c2 + 1; 952 } 953 for(int j : vec[i]) 954 mark[j] = 0, 955 cnt--; 956 if(L[i]!=n+1) { 957 vec[L[i]].push_back(i); 958 mark[i] = 1; 959 cnt++; 960 } 961 } 962 963 for(int i=l; i<=r; i++) 964 dp[i] += l-1; 965 } 966 967 void Main() { 968 cin >> n; 969 for(int i=1; i<=n; i++) { 970 cin >> p[i]; 971 vec[i].clear(); 972 mark[i] = 0; 973 } 974 fill(L+1, L+n+1, n+1); 975 for(int i=n; i>=1; i--) { 976 for(R[i]=i+1; R[i]<=n && p[R[i]]<p[i]; R[i]=R[R[i]]); 977 L[R[i]] = i; 978 } 979 int l=1; 980 for(int r=1; r<=n; r++) 981 if(R[r]==n+1) { 982 solve(l, r); 983 l = r+1; 984 } 985 ll ans = 0; 986 for(int i=1; i<=n; i++) 987 ans += dp[i]; 988 cout << ans << '\n'; 989 } 990 991 int32_t main() { 992 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 993 int T; 994 cin >> T; 995 while(T--) Main(); 996 return 0; 997 } 998 ``` 999 1000 --- 1001 1002 [2268E - Kia Kio and Tree of Life](/contest/2268/problem/E "Codeforces Round 1124 (Div. 1)") 1003 1004 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel") 1005 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T") 1006 1007 **Hints** 1008 1009 **Hint 1** 1010 1011 The number of valid trees that can be constructed from a segment of length $m$ is the $m$-th Catalan number. 1012 1013 **Hint 2** 1014 1015 The vertices inside every subtree form a continuous subarray. Fix a subarray of length $l$. In how many trees does it appear as the subtree below some edge? 1016 1017 **Answer** 1018 1019 Exactly $C_lC_{n-l}$, where $C_i$ is the $i$-th Catalan number. 1020 1021 **Hint 3** 1022 1023 Consider every bit independently. If the XOR of the entire array has this bit set, exactly one of the two components created by cutting any edge has this bit set. 1024 1025 **Hint 4** 1026 1027 Suppose the bit is not set in the XOR of the entire array. We need, for every length $l$, the number of subarrays of length $l$ whose XOR has this bit set. 1028 1029 **Hint 5** 1030 1031 Let $p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$. Encode the corresponding bit of each $p_i$ as either $1$ or $-1$. The number of pairs with different signs can be found from their autocorrelation. 1032 1033 **Hint 6** 1034 1035 We only need a weighted sum of the autocorrelation values. Using Parseval's identity, this weighted sum can be calculated without performing an inverse NTT for every bit. 1036 1037 **Solution** 1038 1039 Let $C_m$ be the $m$-th Catalan number: 1040 1041 $ C_m=\frac{1}{m+1}\binom{2m}{m}. $ 1042 1043 The recursive construction in the statement generates exactly the binary trees whose inorder traversal is: 1044 1045 $ 1,2,\ldots,n. $ 1046 1047 Therefore, there are $C_n$ valid trees. 1048 1049 Consider an edge between a parent and one of its children. The component containing the child after removing this edge is exactly the child's subtree. Since the inorder traversal is fixed, the vertices of this subtree form a continuous subarray. 1050 1051 Now fix a proper subarray $[L,R]$ of length $l$. 1052 1053 There are $C_l$ possible trees inside this subarray. After deleting this subtree, the remaining $n-l$ vertices can form any valid tree, giving $C_{n-l}$ possibilities. 1054 1055 The location of $[L,R]$ determines one gap in the inorder traversal of the remaining tree. This gap corresponds to a unique empty child position, so the chosen subtree can be attached there in exactly one way. 1056 1057 Therefore, a fixed subarray of length $l$ appears as the child subtree of an edge in exactly: 1058 1059 $ C_lC_{n-l} $ 1060 1061 valid trees. 1062 1063 Let: 1064 1065 $ S=a_1\oplus a_2\oplus\cdots\oplus a_n. $ 1066 1067 For a subarray $I$, let its XOR be $X_I$. Cutting the edge above this subtree produces two components with XOR values: 1068 1069 $ X_I \qquad\text{and}\qquad S\oplus X_I. $ 1070 1071 Thus, the whole answer can be written as: 1072 1073 $ \sum_{\substack{I\text{ is a subarray}\\|I| \lt n}} C_{|I|}C_{n-|I|} \left(X_I+(S\oplus X_I)\right). $ 1074 1075 We calculate this sum bit by bit. 1076 1077 Fix a bit $b$. 1078 1079 **Case 1: Bit $b$ of $S$ is set.** 1080 1081 At this bit, $X_I$ and $S\oplus X_I$ are different. Therefore, exactly one of the two components has this bit set for every tree and every edge. 1082 1083 There are $C_n$ trees, and every tree has $n-1$ edges. Hence, before multiplying by $2^b$, the contribution is: 1084 1085 $ (n-1)C_n. $ 1086 1087 **Case 2: Bit $b$ of $S$ is not set.** 1088 1089 In this case, the two component XORs have the same value at bit $b$. 1090 1091 * If bit $b$ of $X_I$ is zero, the edge contributes zero. 1092 * If bit $b$ of $X_I$ is one, both components contribute this bit, so the edge contributes twice. 1093 1094 For every length $l$, let $D_l$ be the number of subarrays of length $l$ whose XOR has bit $b$ set. The contribution of this bit is: 1095 1096 $ 2\sum_{l=1}^{n-1}D_lC_lC_{n-l}. $ 1097 1098 It remains to calculate every $D_l$. 1099 1100 Define the prefix XORs: 1101 1102 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $ 1103 1104 The XOR of a subarray of length $l$ starting after position $i$ is: 1105 1106 $ p_i\oplus p_{i+l}. $ 1107 1108 Define: 1109 1110 $ s_i= \begin{cases} 1,&\text{if bit }b\text{ of }p_i\text{ is zero},\\ -1,&\text{if bit }b\text{ of }p_i\text{ is one}. \end{cases} $ 1111 1112 The required subarray has bit $b$ set exactly when $s_i$ and $s_{i+l}$ are different. 1113 1114 Consider: 1115 1116 $ R_l=\sum_{i=0}^{n-l}s_is_{i+l}. $ 1117 1118 Equal pairs contribute $1$, while different pairs contribute $-1$. Since there are $n+1-l$ pairs in total: 1119 1120 $ R_l=(n+1-l)-2D_l. $ 1121 1122 Therefore: 1123 1124 $ D_l=\frac{n+1-l-R_l}{2}. $ 1125 1126 The values $R_l$ form the autocorrelation of the sequence $s$. After padding the sequence with enough zeros, let $F_k$ be its NTT. The NTT representation of the autocorrelation is: 1127 1128 $ P_k=F_kF_{-k}. $ 1129 1130 With a transform of size $N$, the index $-k$ is represented by $(N-k)\bmod N$. 1131 1132 A direct implementation could perform an inverse NTT and obtain every $R_l$. However, we only need their weighted sum. 1133 1134 Let: 1135 1136 $ w_l=C_lC_{n-l} $ 1137 1138 for $1\leq l \lt n$, and let $W_k$ be the NTT of $w$. Using Parseval's identity: 1139 1140 $ \sum_{l=1}^{n-1}w_lR_l = \frac{1}{N} \sum_{k=0}^{N-1}P_kW_{-k}. $ 1141 1142 Also: 1143 1144 $ 2\sum_{l=1}^{n-1}D_lw_l = \sum_{l=1}^{n-1}(n+1-l)w_l - \sum_{l=1}^{n-1}R_lw_l. $ 1145 1146 The first sum is independent of the bit and can be precomputed. The second sum is calculated using one forward NTT and Parseval's identity. 1147 1148 Therefore, we need one NTT for the weights and at most one NTT for each of the $18$ bits. 1149 1150 The total time complexity is: 1151 1152 $ \mathcal{O}(18n\log n), $ 1153 1154 and the memory complexity is $\mathcal{O}(n)$. 1155 1156 **Code** 1157 1158 ``` 1159 #include <bits/stdc++.h> 1160 1161 using namespace std; 1162 1163 using i64 = long long; 1164 1165 const int mod = 998244353; 1166 const int G = 3; 1167 const int B = 18; 1168 const int N = 200000; 1169 1170 int qpow(int a, int b) { 1171 int r = 1; 1172 while (b) { 1173 if (b & 1) r = (i64)r * a % mod; 1174 a = (i64)a * a % mod; 1175 b >>= 1; 1176 } 1177 return r; 1178 } 1179 1180 struct NTT { 1181 int n; 1182 vector<int> rev, roots; 1183 1184 NTT(int n) : n(n), rev(n), roots(n) { 1185 for (int i = 1; i < n; i++) { 1186 rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0); 1187 } 1188 1189 for (int len = 1; len < n; len <<= 1) { 1190 int z = qpow(G, (mod - 1) / (len << 1)); 1191 roots[len] = 1; 1192 for (int i = 1; i < len; i++) { 1193 roots[len + i] = (i64)roots[len + i - 1] * z % mod; 1194 } 1195 } 1196 } 1197 1198 void transform(vector<int>& a) const { 1199 for (int i = 0; i < n; i++) { 1200 if (i < rev[i]) swap(a[i], a[rev[i]]); 1201 } 1202 1203 for (int len = 1; len < n; len <<= 1) { 1204 for (int i = 0; i < n; i += len << 1) { 1205 for (int j = 0; j < len; j++) { 1206 int x = a[i + j]; 1207 int y = (i64)a[i + j + len] * roots[len + j] % mod; 1208 1209 a[i + j] = x + y; 1210 if (a[i + j] >= mod) a[i + j] -= mod; 1211 1212 a[i + j + len] = x - y; 1213 if (a[i + j + len] < 0) a[i + j + len] += mod; 1214 } 1215 } 1216 } 1217 } 1218 }; 1219 1220 vector<int> fac(2 * N + 1); 1221 vector<int> ifac(2 * N + 1); 1222 vector<int> catalan(N + 1); 1223 1224 void init() { 1225 fac[0] = 1; 1226 for (int i = 1; i <= 2 * N; i++) { 1227 fac[i] = (i64)fac[i - 1] * i % mod; 1228 } 1229 1230 ifac[2 * N] = qpow(fac[2 * N], mod - 2); 1231 for (int i = 2 * N; i >= 1; i--) { 1232 ifac[i - 1] = (i64)ifac[i] * i % mod; 1233 } 1234 1235 for (int i = 0; i <= N; i++) { 1236 catalan[i] = (i64)fac[2 * i] * ifac[i] % mod 1237 * ifac[i + 1] % mod; 1238 } 1239 } 1240 1241 void solve() { 1242 int n; 1243 cin >> n; 1244 1245 vector<int> a(n), pref(n + 1); 1246 for (int& x : a) cin >> x; 1247 1248 if (n == 1) { 1249 cout << 0 << '\n'; 1250 return; 1251 } 1252 1253 for (int i = 1; i <= n; i++) { 1254 pref[i] = pref[i - 1] ^ a[i - 1]; 1255 } 1256 1257 vector<int> weight(n); 1258 int W = 0; 1259 1260 for (int d = 1; d < n; d++) { 1261 weight[d] = (i64)catalan[d] * catalan[n - d] % mod; 1262 W = (W + (i64)(n - d + 1) * weight[d]) % mod; 1263 } 1264 1265 int len = 1; 1266 while (len < 2 * (n + 1)) len <<= 1; 1267 1268 NTT ntt(len); 1269 1270 vector<int> kernel(len); 1271 for (int d = 1; d < n; d++) { 1272 kernel[d] = weight[d]; 1273 kernel[len - d] = weight[d]; 1274 } 1275 1276 ntt.transform(kernel); 1277 1278 int answer = (i64)((1 << B) - 1) * W % mod; 1279 int inv_len = qpow(len, mod - 2); 1280 int inv_two = (mod + 1) / 2; 1281 int total_xor = pref[n]; 1282 1283 vector<int> seq(len); 1284 1285 for (int b = 0; b < B; b++) { 1286 if ((total_xor >> b) & 1) continue; 1287 1288 fill(seq.begin(), seq.end(), 0); 1289 1290 for (int i = 0; i <= n; i++) { 1291 seq[i] = ((pref[i] >> b) & 1) ? mod - 1 : 1; 1292 } 1293 1294 ntt.transform(seq); 1295 1296 int spectral_sum = 0; 1297 1298 for (int k = 0; k < len; k++) { 1299 int opposite = (len - k) & (len - 1); 1300 1301 int term = (i64)kernel[k] * seq[k] % mod 1302 * seq[opposite] % mod; 1303 1304 spectral_sum += term; 1305 if (spectral_sum >= mod) spectral_sum -= mod; 1306 } 1307 1308 int Q = (i64)spectral_sum * inv_len % mod * inv_two % mod; 1309 1310 answer -= (i64)(1 << b) * Q % mod; 1311 if (answer < 0) answer += mod; 1312 } 1313 1314 cout << answer << '\n'; 1315 } 1316 1317 int main() { 1318 cin.tie(0)->sync_with_stdio(0); 1319 1320 init(); 1321 1322 int T; 1323 cin >> T; 1324 1325 while (T--) solve(); 1326 } 1327 ``` 1328 1329 --- 1330 1331 [2268F - Deglado](/contest/2268/problem/F "Codeforces Round 1124 (Div. 1)") 1332 1333 **Idea:** [eren__](/profile/eren__ "Grandmaster eren__") 1334 **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T") 1335 1336 **Hints** 1337 1338 **Hint 1** 1339 1340 Think of each operation as swapping two elements in each of two columns. Therefore, the parity of the total number of inversions over all columns never changes. So if it is odd, the answer is $-1$. 1341 1342 **Hint 2** 1343 1344 Consider the total number of inversions over all columns. One operation can decrease this number by at most $2$. Since there are $2n\binom{2n}{2}$ inversions in the worst case, we need at least $n\binom{2n}{2}$ operations in general. Therefore, our construction can only afford about $9n$ additional operations. 1345 1346 **Hint 3** 1347 1348 Process the values in increasing order. For each value $x$, try to place all occurrences of $x$ into row $x$, so that values $1,2,\ldots,2n-1$ are placed in their correct rows one by one. 1349 1350 **Hint 4** 1351 1352 Pair the columns: $(1,2),(3,4),\ldots$. For a fixed $x$, each pair can contain $0,1,$ or $2$ copies of $x$ in its top row. 1353 1354 **Hint 5** 1355 1356 Distinguish the two possible one-$x$ cases: the $x$ is on top the of left column (we call them $L$-pairs) or on top of the right column (we call them $R$-pairs). 1357 1358 **Hint 6** 1359 1360 Process $L$-pairs from left to right and $R$-pairs from right to left. If an $L$ and $R$ meet, they can be fixed together. 1361 1362 **Solution** 1363 1364 First, consider the parity of the total number of inversions in all columns. 1365 1366 One operation swaps the two top elements with the two bottom elements. In each affected column, this is equivalent to swapping two elements, so the parity of the inversion count of that column changes. Since two columns are affected, the parity of the total inversion count does not change. 1367 1368 In the final grid every column is sorted, so the total number of inversions is $0$, which is even. 1369 1370 Therefore, if the initial total number of inversions is odd, the answer is immediately $-1$. 1371 1372 Now assume it is even. 1373 1374 We process 1375 1376 $ x=1,2,\ldots,2n-1. $ 1377 1378 Our goal at step $x$ is to put every occurrence of $x$ into row $x$. 1379 1380 Pair the columns: 1381 1382 $ (1,2),(3,4),\ldots,(2n-1,2n). $ 1383 1384 For each pair, look at its two cells in row $x$. 1385 1386 There are four possibilities: 1387 1388 * Type $0$: neither cell contains $x$; 1389 * Type $L$: only the left cell contains $x$; 1390 * Type $R$: only the right cell contains $x$; 1391 * Type $1$: both cells contain $x$. 1392 1393 Our goal is to make every pair Type $1$. Once this happens, all $2n$ copies of $x$ are in row $x$. 1394 1395 For each $x=1,2,\ldots,2n-2$, we proceed through the following steps: 1396 1397 **1.** Consider only the pairs $2,3,\ldots,n-1$. The first and last pairs will be handled separately. 1398 1399 **2.** We get rid of all Type $1$ pairs. For every Type $1$ pair, perform an operation on that pair. The two $x$'s are currently on top, so after the operation, they move down and the pair becomes Type $0$. 1400 1401 **3.** While there is a Type $L$ pair, take the leftmost one, say pair $i$: 1402 **3.1.** If pair $i+1$ is Type $0$ or Type $L$, move the right $x$ of pair $i$ to row $x+1$ by performing operations on pair $i$, then perform an operation on pairs $i$ and $i+1$. Pair $i$ becomes Type $1$. 1403 **3.2.** If pair $i+1$ is Type $R$, leave this Type $L$ pair for later. 1404 1405 **4.** While there is a Type $R$ pair, take the rightmost one, say pair $i$: 1406 **4.1.** If pair $i-1$ is Type $0$ or Type $R$, do the symmetric operation: move the appropriate $x$ to row $x+1$, then perform an operation so that pair $i$ becomes Type 1. 1407 **4.2.** If pair $i-1$ is Type $L$, the two pairs form an $L$-$R$ configuration. Move the right $x$ of pair $i-1$ and the left $x$ of pair $i$ to the same row, then perform an operation to move both $x$'s to the top. Both pairs become Type $1$. 1408 1409 **5.** At this point, every middle pair is Type $0$ or Type $1$. For each Type $0$ pair, move its two $x$'s to the same row and perform an operation to move both to the top. Thus every middle pair becomes Type $1$. 1410 1411 **6.** Finally, fix the first and last pairs. They can always be made Type $1$ using at most $2n−x+2$ operations (it means we need at most $2$ additional operations). 1412 1413 For $x=2n-1$, for each $i=1,2,\ldots,2n-1$, if $a_{2n-1,i}\neq 2n-1$, perform an operation on the subgrid whose top-left cell is $(2n-1,i)$. This requires at most $2n-1$ operations. 1414 1415 **Number of operations** 1416 1417 For a fixed $x$, each pair needs at most $2n-x$ operations during the main process. There are $n$ pairs, giving at most $n(2n-x)$. 1418 1419 The first and last pairs require at most $2$ additional operations for each $x$, contributing $2\cdot2(2n-2)$. 1420 1421 Finally, the $x=2n-1$ case costs at most $n-1$ additional operations. 1422 1423 Hence the total is at most 1424 1425 $ \sum_{x=1}^{2n-2} n(2n-x) +4(2n-2)+(n-1). $ 1426 1427 The main sum is 1428 1429 $ n\sum_{x=1}^{2n-2}(2n-x) = n\binom{2n}{2}. $ 1430 1431 Therefore, 1432 1433 $ \begin{aligned} \text{operations} &\le n\binom{2n}{2} +4(2n-2)+(n-1)\\ &= n\binom{2n}{2}+9n-9\\ &\le n\binom{2n}{2}+9n. \end{aligned} $ 1434 1435 So the required bound is satisfied. 1436 1437 The construction also gives the actual sequence of operations if we implement the described moves. 1438 1439 **Code** 1440 1441 ``` 1442 #include <bits/stdc++.h> 1443 using namespace std; 1444 1445 using pii = pair<int, int>; 1446 1447 const int MXN = 202; 1448 1449 int n, n2, a[MXN][MXN]; 1450 vector<pii> ans; 1451 1452 inline void opr(int i, int j) { 1453 swap(a[i][j], a[i+1][j]); 1454 swap(a[i][j+1], a[i+1][j+1]); 1455 ans.push_back({i, j}); 1456 } 1457 1458 inline int wh(int x, int j) { 1459 for(int i=x; i<=n2; i++) 1460 if(a[i][j]==x) 1461 return i; 1462 assert(0); 1463 return -1; 1464 } 1465 1466 inline void R(int x, int j) { 1467 for(int i=wh(x, j+1)-1; i>=x; i--) opr(i, j+1); 1468 } 1469 1470 inline void RL(int x, int j) { 1471 int pos1 = wh(x, j+1), pos2 = wh(x, j+2); 1472 while(pos1>pos2) opr(--pos1, j); 1473 while(pos1<pos2) opr(--pos2, j+2); 1474 while(pos1>x) opr(--pos1, j+1); 1475 } 1476 1477 inline void L(int x, int j) { 1478 for(int i=wh(x, j)-1; i>=x; i--) opr(i, j-1); 1479 } 1480 1481 inline void L1(int x, int j) { 1482 if(a[x+1][j]==x) opr(x+1, j); // extra, we can ignore it for x<=2n-3 1483 opr(x, j-1); // extra, we can ignore it 1484 for(int i=wh(x, j)-1; i>=x+1; i--) opr(i, j); 1485 opr(x, j-1); 1486 } 1487 1488 inline void solve0(int x, int j) { 1489 int pos1=wh(x, j), pos2=wh(x, j+1); 1490 while(pos1>pos2) opr(--pos1, j-1); 1491 while(pos1<pos2) opr(--pos2, j+1); 1492 while(pos1>x) opr(--pos1, j); 1493 } 1494 1495 inline void lft(int x) { // 2 extra 1496 if(a[x][2]==x) { 1497 if(a[x][1]==x) return; 1498 if(a[x+1][1]==x) opr(x+1, 1); 1499 opr(x, 1); 1500 } 1501 else if(a[x][1]==x) { 1502 if(a[x+1][2]==x) opr(x+1, 1); 1503 opr(x, 1); 1504 } 1505 1506 int pos1=wh(x, 1), pos2=wh(x, 2); 1507 if(pos1>pos2) { 1508 while(pos1>pos2) opr(--pos1, 1); 1509 pos2++; 1510 } 1511 while(pos1<pos2) opr(--pos2, 2); 1512 while(pos1>x) opr(--pos1, 1); 1513 } 1514 1515 inline void rgt(int x) { // 2 extra 1516 if(a[x][n2-1]==x) { 1517 if(a[x][n2]==x) return; 1518 if(a[x+1][n2]==x) opr(x+1, n2-1); 1519 opr(x, n2-1); 1520 } 1521 else if(a[x][n2]==x) { 1522 if(a[x+1][n2-1]==x) opr(x+1, n2-1); 1523 opr(x, n2-1); 1524 } 1525 1526 int pos1=wh(x, n2-1), pos2=wh(x, n2); 1527 if(pos1<pos2) { 1528 while(pos1<pos2) opr(--pos2, n2-1); 1529 pos1++; 1530 } 1531 while(pos1>pos2) opr(--pos1, n2-2); 1532 while(pos1>x) opr(--pos1, n2-1); 1533 } 1534 1535 1536 inline void lst() { // 2n-1 extra 1537 for(int j=1; j<=n2-1; j++) 1538 if(a[n2][j]!=n2) opr(n2-1, j); 1539 } 1540 1541 inline void print() { 1542 cout << ans.size() << '\n'; 1543 for(auto [x, y] : ans) cout << x << ' ' << y << '\n'; 1544 ans.clear(); 1545 } 1546 1547 void Main() { 1548 cin >> n; 1549 n2 = n<<1; 1550 for(int i=1; i<=n2; i++) 1551 for(int j=1; j<=n2; j++) 1552 cin >> a[i][j]; 1553 int inv = 0; 1554 for(int j=1; j<=n2; j++) 1555 for(int i1=1; i1<=n2; i1++) 1556 for(int i2=i1+1; i2<=n2; i2++) 1557 inv ^= a[i1][j]>a[i2][j]; 1558 if(inv) { 1559 cout << "-1\n"; 1560 return; 1561 } 1562 if(n==1) { 1563 if(a[1][1]==2) cout << "1\n1 1\n"; 1564 else cout << "0\n"; 1565 return; 1566 } 1567 for(int x=1; x<=n2-2; x++) { 1568 for(int j=3; j<=n2-3; j+=2) 1569 if(a[x][j]==x && a[x][j+1]==x) opr(x, j); 1570 for(int j=3; j<=n2-3; j+=2) 1571 if(a[x][j]==x && a[x][j+1]!=x) { 1572 if(j==n2-3 || a[x][j+3]!=x) R(x, j); 1573 else RL(x, j); 1574 } 1575 for(int j=n2-3; j>=3; j-=2) 1576 if(a[x][j]!=x && a[x][j+1]==x) { 1577 if(a[x][j-2]==x && a[x][j-1]==x) L1(x, j); 1578 else L(x, j); 1579 } 1580 for(int j=3; j<=n2-3; j+=2) 1581 if(a[x][j]!=x) 1582 solve0(x, j); 1583 lft(x); 1584 rgt(x); 1585 } 1586 lst(); 1587 print(); 1588 } 1589 1590 int32_t main() { 1591 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 1592 int tc; 1593 cin >> tc; 1594 while(tc--) Main(); 1595 return 0; 1596 } 1597 ``` 1598 1599 **Challenge** 1600 1601 Can you improve the construction and reduce the number of operations below $n\binom{2n}{2} + 9n$ ?