codeforces-scrape

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

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. ![Image description](/predownloaded/cd/5d/cd5dc39ba1535f23e43483118a90d83faa5fa0a9.png)
    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. ![Image description](/predownloaded/5b/5b/5b5bc19594581abf47ec549203f5a3127491c68c.png)
    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