2271.md (28969B)
1 Source: https://codeforces.com/blog/entry/157590 2 3 thanks to [nifeshe](/profile/nifeshe "Grandmaster nifeshe") for making my life easier with templates 4 5 [2271A - Robot Odd Moves](/contest/2271/problem/A) 6 7 **Hints** 8 9 **Hint 1** 10 11 After performing $z$ operations, the robot's $x$-coordinate is exactly $z$. 12 13 **Hint 2** 14 15 After completing any operation, the $x$-coordinate and $y$-coordinate always have the same parity. 16 17 **Hint 3** 18 19 Try to find a construction to reach any point $(x,y)$ where $y\le x$ and $x$ and $y$ have the same parity. 20 21 **Solution** 22 23 Notice that after performing $z$ operations, the robot's $x$-coordinate will be exactly $z$, while its $y$-coordinate cannot exceed $z$. 24 25 We will first consider the case $b\le a$, then handle the special case $b=a+1$. 26 27 Notice that the robot can reach any point $(x,y)$ where $0\le y\le x$ and $x$ and $y$ have the same parity in exactly $x$ operations. To do so, we can first move up until reaching $y$, then alternate between moving up and down. 28 29 But what if $x$ and $y$ have different parities? 30 31 In this case, we can reach $(x,y-1)$ in exactly $x$ operations, since $x$ and $y-1$ have the same parity. 32 33 Now, recall that in each operation, the robot moves vertically **before** moving horizontally. Therefore, we can perform one additional operation: 34 35 $(x,y-1)\rightarrow(x,y)\rightarrow(x+1,y).$ 36 37 The robot visits $(x,y)$ during this operation, so the answer is $x+1$. 38 39 Now, let's consider the remaining cases: 40 41 * If $b=a+1$, we can use the same construction, since $a$ and $b$ have different parities. We reach $(a,b-1)=(a,a)$ in $a$ operations, then visit $(a,b)$ during the next operation. Thus, the answer is $a+1$. 42 * If $b \gt a+1$, reaching $(a,b)$ is impossible, since the robot can make at most $a+1$ vertical moves before leaving column $a$. 43 44 Therefore, the answer is: 45 46 * $-1$ if $b \gt a+1$. 47 * $a$ if $a$ and $b$ have the same parity. 48 * $a+1$ otherwise. 49 50 The time complexity is $O(1)$ per test case. 51 52 **Code** 53 54 ``` 55 #include <bits/stdc++.h> 56 using namespace std; 57 58 void solve() { 59 int a, b; 60 cin >> a >> b; 61 if (b > a + 1) cout << -1 << '\n'; 62 else if (a % 2 == b % 2) cout << a << '\n'; 63 else cout << a + 1 << '\n'; 64 } 65 66 int main() { 67 ios::sync_with_stdio(false); 68 cin.tie(nullptr); 69 70 int t; 71 cin >> t; 72 while (t--) { 73 solve(); 74 } 75 } 76 ``` 77 78 **Rate The Problem!** 79 80 * Good Problem 81 * Okay Problem 82 * Bad Problem 83 * Didn't Solve 84 85 [2271B - MEX Game](/contest/2271/problem/B) 86 87 **Hints** 88 89 **Hint 1** 90 91 Let $cnt[x]$ be the number of cards containing $x$. Consider the smallest $x$ such that $cnt[x] \lt 2k$. 92 93 **Hint 2** 94 95 What happens if $cnt[x]=2k-1$? Can Alice and Bob have the same $\operatorname{mex}_k$? 96 97 **Hint 3** 98 99 If $cnt[x]\le 2k-2$, try finding a winning strategy for Bob by pairing cards with the same value. 100 101 **Solution** 102 103 Let $cnt[x]$ be the number of cards containing $x$. 104 105 We will consider the integers $x=0,1,2,\ldots$ in increasing order, and find the first $x$ such that $cnt[x] \lt 2k$. 106 107 We claim that **Alice wins if and only if $cnt[x]=2k-1$**. 108 109 Let's prove this by considering two cases. 110 111 **Case 1: $cnt[x]=2k-1$.** 112 113 We will show that it is impossible for Alice and Bob to have the same $\operatorname{mex}_k$, regardless of how they play. 114 115 Suppose both players have the same $\operatorname{mex}_k=y$. We consider three cases: 116 117 * If $y \lt x$, both players must have fewer than $k$ cards containing $y$. This is impossible because $cnt[y]\ge 2k$. 118 * If $y=x$, both players must again have fewer than $k$ cards containing $x$. This is impossible because $cnt[x]=2k-1$. 119 * If $y \gt x$, both players must have at least $k$ cards containing $x$. This is also impossible because $cnt[x]=2k-1 \lt 2k$. 120 121 Therefore, there is no possible value of $y$ for which both players have the same $\operatorname{mex}_k$. 122 123 Thus, **Alice always wins**, regardless of how either player plays. 124 125 **Case 2: $cnt[x]\le 2k-2$.** 126 127 We will show that Bob can always make both MEX values equal. 128 129 Bob can use the following strategy: pair as many cards with the same value as possible, then pair the remaining cards arbitrarily. Whenever Alice takes a card, Bob takes the other card from its pair. 130 131 This guarantees that each player receives either $\lfloor cnt[y]/2\rfloor$ or $\lceil cnt[y]/2\rceil$ cards containing any integer $y$. 132 133 Now notice that: 134 135 * For every $y \lt x$, we have $cnt[y]\ge 2k$, so both players receive at least $k$ cards containing $y$. 136 * For $y=x$, we have $cnt[x]\le 2k-2$, so both players receive fewer than $k$ cards containing $x$. 137 138 Therefore, both players have $\operatorname{mex}_k=x$, and Bob wins. 139 140 Thus, we only need to find the first $x$ with $cnt[x] \lt 2k$. The answer is "YES" if $cnt[x]=2k-1$, and "NO" otherwise. 141 142 The time complexity is $O(n)$ per test case. 143 144 **Code** 145 146 ``` 147 #include <bits/stdc++.h> 148 using namespace std; 149 150 int main() { 151 ios::sync_with_stdio(false); 152 cin.tie(nullptr); 153 154 int t; 155 cin >> t; 156 157 while (t--) { 158 int n, k; 159 cin >> n >> k; 160 161 vector<int> cnt(n + 1, 0); 162 for (int i = 0; i < n; ++i) { 163 int a; 164 cin >> a; 165 ++cnt[a]; 166 } 167 168 for (int x = 0; x <= n; ++x) { 169 if (cnt[x] < 2 * k) { 170 cout << (cnt[x] == 2 * k - 1 ? "YES\n" : "NO\n"); 171 break; 172 } 173 } 174 } 175 176 return 0; 177 } 178 ``` 179 180 **Rate The Problem!** 181 182 * Good Problem 183 * Okay Problem 184 * Bad Problem 185 * Didn't Solve 186 187 [2271C - XOR Problem](/contest/2271/problem/C) 188 189 **Hints** 190 191 **Hint 1** 192 193 Consider the prefix XOR array $p$. A subarray $[l,r]$ has XOR $0$ if and only if $p_{l-1}=p_r$. 194 195 **Hint 2** 196 197 How does the beauty change when a prefix XOR appears for the first, second, or third time? 198 199 **Hint 3** 200 201 Try constructing a prefix XOR array where every possible value appears exactly twice, while ensuring that $p_{i-1}\oplus p_i\le n$. 202 203 **Solution** 204 205 Let $x$ be the greatest power of $2$ not exceeding $n$. 206 207 Define the prefix XOR array $p$ as follows: 208 209 * $p_0=0$. 210 * $p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$. 211 212 Notice that a subarray $[l,r]$ has XOR equal to $0$ if and only if $p_{l-1}=p_r$. 213 214 Also, since $a_i\le n \lt 2x$, none of the elements has a set bit greater than or equal to $2x$. Therefore, every prefix XOR belongs to the range $[0,2x-1]$. 215 216 Now, let's see what happens when we add a new prefix XOR $p_i$: 217 218 * If $p_i$ has never appeared before, no new subarray with XOR $0$ is created, so the beauty increases by $1$. 219 * If $p_i$ has appeared exactly once, exactly one new subarray with XOR $0$ is created, so the beauty stays the same. 220 * If $p_i$ has appeared at least twice, the beauty decreases. 221 222 Since there are only $2x$ possible prefix XOR values, and $p_0=0$ already exists, the **maximum possible beauty is at most $2x-1$**. 223 224 To achieve this beauty with the maximum possible length, we want every prefix XOR from $0$ to $2x-1$ to appear exactly twice. 225 226 This gives us $4x$ prefix XORs, corresponding to an array of length $4x-1$. 227 228 Now, let's show how to construct such an array. 229 230 Instead of constructing $a$ directly, we will construct the prefix XOR array $p$, then recover $a$ using $a_i=p_{i-1}\oplus p_i$. 231 232 First, visit all integers from $0$ to $x-1$ in increasing order, then visit them again in decreasing order: 233 234 $0,1,\ldots,x-1,x-1,\ldots,1,0.$ 235 236 After that, do the same for all integers from $x$ to $2x-1$: 237 238 $x,x+1,\ldots,2x-1,2x-1,\ldots,x+1,x.$ 239 240 Clearly, every integer from $0$ to $2x-1$ appears exactly twice. 241 242 We only need to verify that every $a_i=p_{i-1}\oplus p_i$ is at most $n$. 243 244 Notice that: 245 246 * The XOR of any two integers from $[0,x-1]$ is smaller than $x$. 247 * The XOR of any two integers from $[x,2x-1]$ is also smaller than $x$, since their highest set bits cancel. 248 * The only jump between these two ranges is from $0$ to $x$, whose XOR is exactly $x$. 249 250 Therefore, every element of $a$ is at most $x\le n$, so our construction is valid. 251 252 Since every prefix XOR appears exactly twice, we have exactly $2x$ subarrays with XOR $0$. Thus, the beauty is 253 254 $(4x-1)-2x=2x-1,$ 255 256 which achieves the maximum possible beauty with the maximum possible length. 257 258 The time complexity is $O(n)$ per test case. 259 260 **Code** 261 262 ``` 263 #include <bits/stdc++.h> 264 using namespace std; 265 266 void solve() { 267 int n; 268 cin >> n; 269 270 int x = 1; 271 while (2 * x <= n) x *= 2; 272 273 vector<int> p; 274 for (int i = 0; i < x; i++) p.push_back(i); 275 for (int i = x - 1; i >= 0; i--) p.push_back(i); 276 for (int i = x; i < 2 * x; i++) p.push_back(i); 277 for (int i = 2 * x - 1; i >= x; i--) p.push_back(i); 278 279 cout << (int)p.size() - 1 << '\n'; 280 for (int i = 1; i < (int)p.size(); i++) 281 cout << (p[i] ^ p[i - 1]) << " \n"[i == (int)p.size() - 1]; 282 } 283 284 int main() { 285 ios::sync_with_stdio(false); 286 cin.tie(nullptr); 287 288 int t; 289 cin >> t; 290 while (t--) solve(); 291 } 292 ``` 293 294 **Rate The Problem!** 295 296 * Good Problem 297 * Okay Problem 298 * Bad Problem 299 * Didn't Solve 300 301 [2271D - Target Infection](/contest/2271/problem/D) 302 303 **Hints** 304 305 **Hint 1** 306 307 Notice that $|f(s+1)-f(s)|\le 1$. How can we use this property? 308 309 **Hint 2** 310 311 Prove that the maximum value of $f(s)$ is achieved at some $s=l_i$. 312 313 **Hint 3** 314 315 After finding a position $pos$ with maximum $f(pos)$, try using binary search to find a position $s$ where $f(s)=k$, even though $f(s)$ is not monotonic. 316 317 **Solution** 318 319 Let $f(s)$ be the number of infected positions in the segment $[s,s+m-1]$. 320 321 First, notice that when we increase $s$ by $1$, we remove the position $s$ and add the position $s+m$. 322 323 Therefore, **$f(s)$ can change by at most $1$** when we increase $s$ by $1$. 324 325 This observation will be useful later. 326 327 Now, let's find the maximum possible value of $f(s)$. 328 329 We claim that **the maximum is achieved at some $s=l_i$**. 330 331 To see why, consider any starting position $s$: 332 333 * If $s$ is infected but is not the beginning of an infection interval, we can move $s$ to the left by $1$. Since the newly added position is infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of that interval. 334 * If $s$ is not infected, we can move $s$ to the right by $1$. Since the removed position is not infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of the next infection interval. 335 336 Therefore, it is sufficient to check $f(l_i)$ for every interval. 337 338 Let $mx$ be the maximum value we find, and let $pos$ be a position where $f(pos)=mx$. 339 340 Now, we have three cases: 341 342 * If $k \gt mx$, the answer is $-1$, since we cannot infect that many people. 343 * If $k=mx$, we can simply output $pos$. 344 * Otherwise, $k \lt mx$, and we will find a valid position using binary search. 345 346 Now, suppose $k \lt mx$. We know that $f(pos)=mx \gt k$, and we also know that $f(10^{15}+1)=0\le k$, since there are no infected positions after $10^{15}$. 347 348 Therefore, we have two positions: one where $f(s) \gt k$, and another where $f(s)\le k$. 349 350 Recall that **moving $s$ by $1$ changes $f(s)$ by at most $1$**. This means that somewhere between these two positions, there must be a position where $f(s)=k$. 351 352 We can find such a position using binary search! 353 354 Maintain two positions $l$ and $r$ such that $f(l) \gt k$ and $f(r)\le k$. Initially, set $l=pos$ and $r=10^{15}+1$. 355 356 Let $mid=\lfloor(l+r)/2\rfloor$. 357 358 * If $f(mid) \gt k$, set $l=mid$. 359 * Otherwise, set $r=mid$. 360 361 Notice that we always keep one position with $f(s) \gt k$ and another with $f(s)\le k$, so we never lose the guarantee that a valid answer exists between them. 362 363 Continue until $r=l+1$. 364 365 Now, since $f(l) \gt k$ and $f(r)\le k$, and these positions are adjacent, we must have $f(r)=k$. Therefore, we can output $r$. 366 367 **Note that $f(s)$ does not need to be monotonic for this binary search to work!** We only need the fact that $f(s)$ changes by at most $1$ between consecutive positions. 368 369 **Code** 370 371 ``` 372 #include <bits/stdc++.h> 373 using namespace std; 374 375 void solve() { 376 int n; 377 long long m, k; 378 cin >> n >> m >> k; 379 380 vector<long long> l(n), r(n), pref(n + 1); 381 for (int i = 0; i < n; i++) { 382 cin >> l[i] >> r[i]; 383 pref[i + 1] = pref[i] + r[i] - l[i] + 1; 384 } 385 386 auto f = [&](long long s) -> long long { 387 long long e = s + m - 1; 388 389 int i = lower_bound(r.begin(), r.end(), s) - r.begin(); 390 int j = upper_bound(l.begin(), l.end(), e) - l.begin() - 1; 391 392 if (i > j) return 0; 393 394 long long ans = pref[j + 1] - pref[i]; 395 ans -= max(0LL, s - l[i]); 396 ans -= max(0LL, r[j] - e); 397 return ans; 398 }; 399 400 long long mx = -1, pos = 0; 401 for (int i = 0; i < n; i++) { 402 long long cur = f(l[i]); 403 if (cur > mx) { 404 mx = cur; 405 pos = l[i]; 406 } 407 } 408 409 if (k > mx) { 410 cout << -1 << '\n'; 411 return; 412 } 413 414 if (k == mx) { 415 cout << pos << '\n'; 416 return; 417 } 418 419 long long low = pos, high = 1000000000000001LL; 420 421 while (high - low > 1) { 422 long long mid = (low + high) / 2; 423 if (f(mid) > k) low = mid; 424 else high = mid; 425 } 426 427 cout << high << '\n'; 428 } 429 430 int main() { 431 ios::sync_with_stdio(false); 432 cin.tie(nullptr); 433 434 int t; 435 cin >> t; 436 while (t--) solve(); 437 } 438 ``` 439 440 **Rate The Problem!** 441 442 * Good Problem 443 * Okay Problem 444 * Bad Problem 445 * Didn't Solve 446 447 [2271E - Array Emptying](/contest/2271/problem/E) 448 449 **Hints** 450 451 **Hint 1** 452 453 Try solving a relaxed version where we can split any element, even if it is smaller than or equal to $k$. 454 455 **Hint 2** 456 457 Show that we can perform all splits before any erasures, then process the erasures in reverse order. 458 459 **Hint 3** 460 461 Binary search on the number of splits. When processing backward, consider the largest remaining element: should we erase it or split it? 462 463 **Solution** 464 465 First, let's solve a **relaxed version** of the problem, where we are allowed to split any element, even if it is already small enough to be erased. 466 467 Let's find a greedy solution for this relaxed version. 468 469 Suppose we perform exactly $c$ splits. Each split increases the number of elements by $1$, so we will need $n+c$ erasures. 470 471 Therefore, the total number of operations is 472 473 $n+2c.$ 474 475 Now, notice that **we can always perform all splits before any erasures**. 476 477 We can prove this using an exchange argument. If a split happens after an erasure, we can swap these two operations. The split remains valid because splitting is always allowed in our relaxed version, and the erasure remains valid because $k$ only increases. 478 479 By repeatedly applying this argument, we can rearrange the operations into the following order: 480 481 $\underbrace{\text{split},\ldots,\text{split}}_{c},\underbrace{\text{erase},\ldots,\text{erase}}_{n+c}.$ 482 483 Now, let's binary search on the number of splits $c$. 484 485 To check whether $c$ splits are sufficient, we will **process the erasures in reverse order**, starting from the last erasure and moving toward the first. 486 487 The value of $k$ at the last operation is 488 489 $S=k+n+2c-1.$ 490 491 Let $H$ be the largest remaining element. 492 493 We have two cases: 494 495 * **If $H \gt S$**, we must split $H$, since we cannot erase it now, and we certainly cannot erase it at any earlier operation, where $k$ is even smaller. 496 * **If $H\le S$**, we claim that it is optimal to erase $H$ now. 497 498 Let's prove the second case. 499 500 Consider an optimal solution that does not erase $H$ at this moment. There are two possibilities: 501 502 1. **It erases $H$ at an earlier operation.** In this case, we can simply swap that erasure with the current one. This is valid because $H\le S$, and the other element, being no larger than $H$, can also be erased earlier. 503 2. **It splits $H$ instead.** Suppose it erases some smaller element $y$ at this moment. We can instead erase $H$ and split $y$. Since $y\le H$, the two elements produced by splitting $y$ are no larger than those produced by splitting $H$. Therefore, we can perform the same subsequent operations without making anything harder. If the element erased at this moment was itself produced by splitting $H$, we can simply erase $H$ instead and avoid those splits. 504 505 Thus, in both cases, there exists an optimal solution that erases $H$ now. 506 507 This proves our greedy strategy. 508 509 Whenever we erase an element, we decrease $S$ by $1$, since we move to the previous erasure. Whenever we split an element, we replace it with two elements equal to $\lceil H/2\rceil$, without changing $S$. 510 511 If we need more than $c$ splits, the check fails. Otherwise, it succeeds. 512 513 We can implement this efficiently using a frequency array to maintain the remaining elements. 514 515 Now, let $X$ be the minimum number of operations for the relaxed problem. 516 517 Clearly, the answer to the original problem is **at least $X$**, since the relaxed problem allows everything the original problem allows. 518 519 However, notice something important about our greedy construction: **we only split an element when $H \gt S$**. 520 521 Since $S$ is at least the value of $k$ when that split would actually happen, we also have $H \gt k$ at that moment. 522 523 Therefore, every split performed by our greedy solution is valid in the original problem as well! 524 525 This means our solution to the relaxed problem is also a valid solution to the original problem, so the minimum number of operations is the same for both. 526 527 Finally, if $c$ is the minimum number of splits found by binary search, the answer is 528 529 $\boxed{n+2c}.$ 530 531 The time complexity is $O(n\log n)$ per test case, and the space complexity is $O(n)$. 532 533 **Code** 534 535 ``` 536 #include <bits/stdc++.h> 537 using namespace std; 538 539 void solve() { 540 int n, k; 541 cin >> n >> k; 542 543 vector<int> a(n); 544 int mx = 0; 545 for (int &x : a) { 546 cin >> x; 547 mx = max(mx, x); 548 } 549 550 vector<int> freq(mx + 1); 551 for (int x : a) freq[x]++; 552 553 auto ok = [&](int c) { 554 vector<int> cnt = freq; 555 int alive = n, used = 0, H = mx; 556 long long S = 1LL * k + n + 2LL * c - 1; 557 558 while (alive > 0) { 559 while (cnt[H] == 0) H--; 560 561 if (H <= S) { 562 cnt[H]--; 563 alive--; 564 S--; 565 } else { 566 if (used == c) return false; 567 cnt[H]--; 568 cnt[(H + 1) / 2] += 2; 569 alive++; 570 used++; 571 } 572 } 573 return true; 574 }; 575 576 int l = 0, r = max(0, mx - k); 577 while (l < r) { 578 int mid = (l + r) / 2; 579 if (ok(mid)) r = mid; 580 else l = mid + 1; 581 } 582 583 cout << n + 2 * l << '\n'; 584 } 585 586 int main() { 587 ios::sync_with_stdio(false); 588 cin.tie(nullptr); 589 590 int t; 591 cin >> t; 592 while (t--) solve(); 593 } 594 ``` 595 596 **Rate The Problem!** 597 598 * Good Problem 599 * Okay Problem 600 * Bad Problem 601 * Didn't Solve 602 603 [2271F - Beautiful Pillers](/contest/2271/problem/F) 604 605 **Hints** 606 607 **Hint 1** 608 609 Notice that we can always make the array beautiful using at most $2$ operations. 610 611 **Hint 2** 612 613 Let $mx$ be the maximum element. Try setting $a_1=mx$ or $a_n=mx$. 614 615 **Hint 3** 616 617 If neither works, can we make the array beautiful by changing one occurrence of $mx$ to something? 618 619 **Solution** 620 621 First, notice that we can always make the array beautiful using at most **$2$ operations**, by setting $a_1=a_n=10^9$. 622 623 Now, let's check whether the array is already beautiful. If it is, the answer is $0$. 624 625 Otherwise, the answer must be either $1$ or $2$. 626 627 We claim that **if the answer is $1$, at least one of the following three operations makes the array beautiful**. 628 629 Let $mx$ be the maximum element of the array, and let $pos$ be any position such that $a_{pos}=mx$. 630 631 The three operations are: 632 633 1. Set $a_1=mx$. 634 2. Set $a_n=mx$. 635 3. Set $a_{pos}=1$. 636 637 We can simply try each operation and check whether the resulting array is beautiful. If any of them works, the answer is $1$. Otherwise, the answer is $2$. 638 639 Now, let's prove why these three cases are sufficient. 640 641 Imagine the array looks like this: 642 643 $\underbrace{\text{xxxxx}}_{\text{left}}\quad mx\quad\underbrace{\text{xxxxx}}_{\text{right}}.$ 644 645 Notice that setting $a_1=mx$ makes the entire left side covered by good pairs, while setting $a_n=mx$ does the same for the right side. 646 647 If neither operation makes the array beautiful, this means there are still uncovered positions on both sides. 648 649 Therefore, if we want to fix everything using only one operation, we must somehow fix both sides at once. 650 651 The only remaining possibility is to **decrease a maximum element**, allowing good pairs to connect across it. 652 653 Suppose changing this maximum element to some value $X$ makes the array beautiful. 654 655 We claim that changing it to $1$ would also work. 656 657 Why? Any new good pair that spans this position remains good if we decrease its value even further. 658 659 The other possibility is that the new value $X$ creates two good pairs, one on each side, looking like this: 660 661 $X\quad\ldots\quad X\quad\ldots\quad X.$ 662 663 Here, the middle $X$ is the element we changed, and both pairs are good. 664 665 If we decrease the middle element to $1$, the two pairs can be replaced by one larger good pair: 666 667 $X\quad\ldots\quad 1\quad\ldots\quad X.$ 668 669 Thus, decreasing the maximum element to $1$ is sufficient. 670 671 lets also note if that max element occurs more than once this is useless. 672 673 This proves that checking our three operations is enough to find an optimal solution. 674 675 Finally, checking whether an array is beautiful can be implemented in $O(n\log n)$ using several approaches, or in $O(n)$ using a monotonic stack. 676 677 Since we perform only a constant number of checks, the overall time complexity is **$O(n)$** per test case. 678 679 **Code** 680 681 ``` 682 #include <bits/stdc++.h> 683 using namespace std; 684 685 bool beautiful(vector<int>& a) { 686 int n = a.size(); 687 vector<int> st, diff(n + 1); 688 689 for (int i = 0; i < n; i++) { 690 while (!st.empty() && a[st.back()] < a[i]) 691 st.pop_back(); 692 693 if (!st.empty() && a[st.back()] == a[i]) { 694 diff[st.back()]++; 695 diff[i + 1]--; 696 } 697 st.push_back(i); 698 } 699 700 int cur = 0; 701 for (int i = 0; i < n; i++) { 702 cur += diff[i]; 703 if (cur == 0) return false; 704 } 705 return true; 706 } 707 708 void solve() { 709 int n; 710 cin >> n; 711 vector<int> a(n); 712 for (int &x : a) cin >> x; 713 714 if (beautiful(a)) { 715 cout << 0 << '\n'; 716 return; 717 } 718 719 int pos = max_element(a.begin(), a.end()) - a.begin(); 720 int mx = a[pos]; 721 722 auto check = [&](int i, int x) { 723 int old = a[i]; 724 a[i] = x; 725 bool ok = beautiful(a); 726 a[i] = old; 727 if (ok) { 728 cout << 1 << '\n'; 729 cout << i + 1 << ' ' << x << '\n'; 730 } 731 return ok; 732 }; 733 734 if (check(0, mx)) return; 735 if (check(n - 1, mx)) return; 736 if (check(pos, 1)) return; 737 738 cout << 2 << '\n'; 739 cout << 1 << ' ' << mx << '\n'; 740 cout << n << ' ' << mx << '\n'; 741 } 742 743 int main() { 744 ios::sync_with_stdio(false); 745 cin.tie(nullptr); 746 747 int t; 748 cin >> t; 749 while (t--) solve(); 750 } 751 ``` 752 753 **Rate The Problem!** 754 755 * Good Problem 756 * Okay Problem 757 * Bad Problem 758 * Didn't Solve 759 760 [2271G - Grid Filling](/contest/2271/problem/G) 761 762 **Solution Part1** 763 764 ### Case 1: There are no $1\times 1$ pieces 765 766 First, let's consider the case where the grid contains no $1\times 1$ pieces. 767 768 Notice that either every piece has width at least $2$, or every piece has height at least $2$. Otherwise, a row segment of height $1$ and a column segment of width $1$ would intersect to form a $1\times 1$ piece. 769 770 Since we can transpose the grid, we may assume that **every piece has width at least $2$**. 771 772 We will show that a valid filling always exists. 773 774 **Step 1: Fill the first row of every piece.** 775 776 Consider a piece of width $w$, whose first row is row $i$ of the grid (using 0-based indexing). 777 778 * If $i$ is even, fill it with $[1,2,\ldots,w]$. 779 * Otherwise, fill it with $[w,w-1,\ldots,1]$. 780 781 When $w$ is odd, we additionally swap the middle element with the element before it in the decreasing order. 782 783 For example, when $w=5$, the two arrangements are: 784 785 $[1,2,3,4,5]$ and $[5,3,4,2,1]$. 786 787 Notice that these arrangements differ at every position. This ensures that vertically adjacent first rows have different values, while horizontally adjacent pieces also have different values at their boundaries. 788 789 **Step 2: Fill the remaining rows.** 790 791 Now, fill the remaining cells row by row, from top to bottom. 792 793 For the $k$-th row of a piece of width $w$ (0-based), we need to place the numbers 794 795 $kw+1,kw+2,\ldots,(k+1)w.$ 796 797 Normally, we place them in increasing order. However, if the first number equals the cell immediately to its left, we instead move the last number to the beginning. 798 799 Since $w\ge 2$, this always avoids horizontal conflicts. 800 801 Also, different rows of the same piece use completely different ranges of numbers, so vertical adjacency inside each piece is automatically satisfied. Across horizontal cuts, the first-row construction handles pieces of height $1$, while taller pieces have different ranges at the boundary. 802 803 Thus, every piece contains exactly the required numbers, and all adjacent cells are different. Therefore, **a valid filling always exists when there are no $1\times 1$ pieces**. 804 805 **Solution Part2** 806 807 ### Case 2: There are $1\times 1$ pieces 808 809 First, let's determine when it is **impossible** to fill the grid. 810 811 Suppose there are two $1\times 1$ pieces in the same row, with only $1\times 2$ pieces between them. 812 813 For example: 814 815 $x\ |\ x\ x\ |\ x\ x\ |\ x\ x\ |\ x$ 816 817 Since every $1\times 1$ piece must contain $1$, the first cell is forced to be $1$. This forces the next $1\times 2$ piece to be $[2,1]$, and the same applies to every following piece. 818 819 We end up with: 820 821 $1\ |\ 2\ 1\ |\ 2\ 1\ |\ 2\ 1\ |\ 1$ 822 823 Clearly, this is invalid because the last two adjacent cells both contain $1$. 824 825 The same argument applies vertically to two $1\times 1$ pieces with only $2\times 1$ pieces between them. 826 827 We claim that **these are the only cases where a valid filling is impossible**. 828 829 Let's prove this by constructing a valid filling whenever neither case occurs. 830 831 **Step 1: Fill all thin pieces.** 832 833 First, put $1$ in every $1\times 1$ piece. 834 835 Now, let's fill all $1\times y$ and $y\times 1$ pieces. 836 837 We will only explain the construction for horizontal pieces, since vertical pieces can be handled in exactly the same way. 838 839 Consider any two $1\times 1$ pieces in the same row. 840 841 Since our impossible condition does not occur, there must be at least one $1\times y$ piece between them with $y\ge 3$. 842 843 Choose the first such piece from the left and call it the **turning point**. 844 845 We fill the pieces between the two $1\times 1$ pieces as follows: 846 847 * For every piece before the turning point, write its numbers in decreasing order. 848 * For every piece after the turning point, write its numbers in increasing order. 849 * For the turning point itself, use the order $[y,1,2,3,\ldots,y-1]$. 850 851 Notice that this guarantees that adjacent cells contain different numbers, including across the boundaries of the pieces. 852 853 For portions of the row before the first $1\times 1$ piece, after the last one, or rows containing no $1\times 1$ pieces, we can simply choose a suitable increasing or decreasing order. 854 855 We apply the same construction vertically to fill all remaining $y\times 1$ pieces.  856 857 **Step 2: Fill the rows containing $1$.** 858 859 Notice that by choosing our coloring patterns consistently in the previous step, the already-colored cells in each partially filled row contain the same value. 860 861 Now, consider every partially filled row whose already-colored cells contain $1$. 862 863 We can fill the gaps between these $1$ s using exactly the same turning-point construction from Step 1. 864 865 This fills all such rows while ensuring that horizontally adjacent cells contain different numbers.  866 867 **Step 3: Fill the remaining cells.** 868 869 Now, let's consider the remaining unfilled rows. 870 871 The important observation is that **these rows can be handled independently**, since the vertical constraints have already been taken care of by our construction. 872 873 Furthermore, every gap we need to fill has the same value, say $x$, on both its left and right boundaries. 874 875 Therefore, we only need to arrange the remaining numbers inside each piece so that adjacent values are different and neither boundary creates a conflict. 876 877 We can use the same idea as before: arrange the values in increasing or decreasing order, and use a turning point whenever necessary. 878 879 Since the required values are available and the vertical constraints are already satisfied, we can fill all remaining gaps. 880 881 Thus, we have constructed a valid filling whenever neither of the two impossible configurations occurs, completing the proof. 882 883 **Rate The Problem!** 884 885 * Good Problem 886 * Okay Problem 887 * Bad Problem 888 * Didn't Solve 889 890 [2271H2 - Personal Issues (Hard Version)](/contest/2271/problem/H2) 891 892 **Solution** 893 894 Editorial will be Added when Axial isn't tired :( 895 896 if you have any non slop solutions please comment them below 897 898 **Code** 899 900 ~~~~ 901 902 ~~~~ 903 904 **Rate The Problem!** 905 906 * Good Problem 907 * Okay Problem 908 * Bad Problem 909 * Didn't Solve