codeforces-scrape

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

2123.md (25307B)


      1 Source: https://codeforces.com/blog/entry/144363
      2 
      3 I hope you all enjoyed the contest!
      4 
      5 **Rating Predictions**
      6 
      7 | Predictor | A | B | C | D | E | F | G |
      8 | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 900 | 1000 | 1500 | 1500 | 1800 | 1700 |
     10 | [__baozii__](/profile/__baozii__ "International Master __baozii__") | 800 | 800 | 1200 | 1500 | 1500 | 1600 | 1900 |
     11 | [DivinePunishment](/profile/DivinePunishment "Expert DivinePunishment") | 800 | 900 | 1100 | 1400 | 1500 | 1600 | 1900 |
     12 | [Edeeva](/profile/Edeeva "Master Edeeva") | 800 | 800 | 1000 | 1200 | 1600 | 1800 | 2200 |
     13 | [efishel](/profile/efishel "Master efishel") | 800 | 800 | 1000 | 1200 | 1400 | 1500 | 1900 |
     14 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 900 | 1400 | 1500 | 1700 | 2000 |
     15 | [beaten_by_ai](/profile/beaten_by_ai "Expert beaten_by_ai") | 800 | 900 | 1100 | 1600 | 1500 | 1800 | 2000 |
     16 | [Hori](/profile/Hori "Candidate Master Hori") | 800 | 800 | 1200 | 1600 | 1400 | 1500 | 2000 |
     17 | [kevlu8](/profile/kevlu8 "Expert kevlu8") | 800 | 900 | 1000 | 1300 | 1600 | 1700 | — |
     18 | [Lilypad](/profile/Lilypad "Master Lilypad") | 800 | 900 | 1100 | 1400 | 1400 | 1500 | — |
     19 | [Friedrich](/profile/Friedrich "Candidate Master Friedrich") | 800 | 800 | 1000 | 1300 | 1600 | 1700 | 2100 |
     20 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 900 | 800 | 900 | 1500 | 1600 | 1600 |
     21 | [Non-origination](/profile/Non-origination "Expert Non-origination") | 800 | 800 | 1200 | 1500 | 1500 | 1800 | 2100 |
     22 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1000 | 1100 | 1400 | 1600 | 1800 | 2100 |
     23 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 800 | 1100 | 1400 | 1600 | 1700 | 2000 |
     24 | [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv") | 800 | 800 | 1200 | 1800 | 1500 | 1700 | — |
     25 | [yse](/profile/yse "Expert yse") | 800 | 900 | 1000 | 1200 | 1500 | 1700 | — |
     26 | Average | 800.0 | 852.9 | 1058.8 | 1388.2 | 1511.8 | 1676.5 | 1961.5 |
     27 | Actual | 800 | 800 | 1000 | 1200 | 1400 | 1700 | 2100 |
     28 
     29 **Rate the contest!**
     30 
     31 **Quality**
     32 
     33 * Excellent contest
     34 * Good contest
     35 * Average contest
     36 * Bad contest
     37 * Horrible contest
     38 
     39 **Difficulty**
     40 
     41 * Trivial contest
     42 * Easy contest
     43 * Average contest
     44 * Hard contest
     45 * Impossible contest
     46 
     47 #### [A — Blackboard Game](https://codeforces.com/contest/2123/problem/A)
     48 
     49 **Solution**
     50 
     51 **Step 1**
     52 
     53 Alice can't lose unless there are no numbers remaining on her turn (in particular, this can only occur if $n$ is even). So Bob's job is to pair all numbers into disjoint pairs $(a, b)$ with $a+b\equiv 3\pmod 4$. If he can do so, he wins by choosing the paired number to each of Alice's choices. Otherwise, Alice wins.
     54 
     55 **Step 2**
     56 
     57 It doesn't really matter if Bob chooses, say, $0$ or $4$, because it won't affect the value of $a+b\pmod 4$. That is, two values are essentially identical in this game if they are equivalent $\bmod 4$. So now, the numbers on the blackboard are essentially $0, 1, 2, 3, 0, 1, 2, 3, \dots (n-1)\pmod 4$.
     58 
     59 **Step 3**
     60 
     61 Now, all of the numbers on the blackboard are either $0$, $1$, $2$, or $3$. It is clear that Bob must pair $0$ with $3$, and $1$ with $2$. So Bob wins if the number of $0$'s is the same as the number of $3$'s, and the number of $1$'s is the same as the number of $2$'s.
     62 
     63 **Code (C++)**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 using namespace std;
     68  
     69 void solve(){
     70     int n;
     71     cin >> n;
     72     vector<int> cnt(4);
     73     for(int i=0; i<n; i++)
     74         cnt[i % 4]++;
     75     cout << (cnt[0] == cnt[3] && cnt[1] == cnt[2] ? "Bob" : "Alice") << '\n';
     76 }
     77  
     78 int main(){
     79     int t;
     80     cin >> t;
     81     while(t--) solve();
     82 }
     83 ```
     84 
     85 **Step 4 (optional)**
     86 
     87 For an $O(1)$ solution, observe that as $n$ increases, a $0$, $1$, $2$, and $3$ are introduced, in that order. So the number of $0$'s can only match the number of $3$'s, and the number of $1$'s can only match the number of $2$'s, if $n$ is a multiple of $4$.
     88 
     89 **Code (C++)**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 using namespace std;
     94  
     95 void solve(){
     96     int n;
     97     cin >> n;
     98     cout << (n % 4 ? "Alice" : "Bob") << '\n';
     99 }
    100  
    101 int main(){
    102     int t;
    103     cin >> t;
    104     while(t--) solve();
    105 }
    106 ```
    107 
    108 **Rate the problem!**
    109 
    110 **Quality**
    111 
    112 * Excellent problem
    113 * Good problem
    114 * Average problem
    115 * Bad problem
    116 * Horrible problem
    117 
    118 **Difficulty**
    119 
    120 * Trivial problem
    121 * Easy problem
    122 * Average problem
    123 * Hard problem
    124 * Impossible problem
    125 
    126 #### [B — Tournament](https://codeforces.com/contest/2123/problem/B)
    127 
    128 **Solution**
    129 
    130 **Step 1**
    131 
    132 If $k \gt 1$, then the answer is always $\texttt{YES}$. This is because player $j$ might never get picked.
    133 
    134 **Step 2**
    135 
    136 If $k=1$, then we claim that the answer is only $\texttt{YES}$ if player $j$ has the maximum strength across all players. Indeed, consider the set of players with maximum strength. It is impossible for all of them to get eliminated, because the last one of them can't possibly lose a match. So at least one of these players will be remaining at the end of the game. If player $j$ is not one of these players, they cannot be the last player remaining.
    137 
    138 **Code (C++)**
    139 
    140 ```
    141 #include <bits/stdc++.h>
    142 using namespace std;
    143  
    144 void solve(){
    145     int n, j, k, mx = 0;
    146     cin >> n >> j >> k;
    147     vector<int> a(n+1);
    148     for(int i=1; i<=n; i++){
    149         cin >> a[i];
    150         mx = max(mx, a[i]);
    151     }
    152     cout << (k > 1 || a[j] == mx ? "YES" : "NO") << '\n';
    153 }
    154  
    155 int main(){
    156     int t;
    157     cin >> t;
    158     while(t--) solve();
    159 }
    160 ```
    161 
    162 **Rate the problem!**
    163 
    164 **Quality**
    165 
    166 * Excellent problem
    167 * Good problem
    168 * Average problem
    169 * Bad problem
    170 * Horrible problem
    171 
    172 **Difficulty**
    173 
    174 * Trivial problem
    175 * Easy problem
    176 * Average problem
    177 * Hard problem
    178 * Impossible problem
    179 
    180 #### [C — Prefix Min and Suffix Max](https://codeforces.com/contest/2123/problem/C)
    181 
    182 **Solution**
    183 
    184 **Step 1**
    185 
    186 If $a$ has size $2$, we can make either of its elements the last one. We can transform $a$ into $\min(a_1, a_2)$ by choosing the prefix of size $2$, and we can transform $a$ into $\max(a_1, a_2)$ by choosing the suffix of size $2$.
    187 
    188 **Step 2**
    189 
    190 If $a_i$ is a prefix min, now we can transform $a$ into $[a_i]$. We do so by first choosing the prefix of length $i$. Now, $a_i$ is the first element of $a$. If $a$ is of size $1$, we are done. Otherwise, we can choose the suffix consisting of all of the elements after it. Now, our array is of size $2$, so we can transform $a$ into $[a_i]$ as desired. By identical reasoning, if $a_i$ is a suffix max, we can transform $a$ into $[a_i]$.
    191 
    192 **Step 3**
    193 
    194 Now, suppose that $a_i$ is not a prefix min or a suffix max. Then let $a_p$ be the min of the prefix $[a_1, \dots, a_i]$, and let $a_s$ be the max of the suffix $[a_i, \dots, a_n]$. Note that $p \lt i \lt s$ and $a_p \lt a_i \lt a_s$.
    195 
    196 We claim that it is impossible to remove $a_p$ or $a_s$ without removing $a_i$. Consider the first operation which removes (at least) one of $a_p$, $a_i$, or $a_s$.
    197 
    198 * Suppose you remove $a_p$ by choosing a prefix which includes an element smaller than $a_p$. Since $a_p$ is the smallest element in $[a_1, \dots, a_i]$, this means that you must have chosen at least one element after $a_i$. But then this prefix also includes $a_i$. Since $a_i$ is not the min of this prefix, it will also be removed. By identical reasoning, if you remove $a_s$ by choosing a suffix which includes an element larger than $a_s$, then $a_i$ will also be removed.
    199 * Conversely, suppose you remove $a_p$ by choosing a suffix which includes $a_p$. But then this suffix will include $a_i$ and $a_s$. Since $a_i$ is not the max of this suffix, it will also be removed. By identical reasoning, if you remove $a_s$ by choosing a prefix which includes $a_s$, then $a_i$ will also be removed.
    200 
    201 So the first operation that removes one of $a_p$, $a_i$, or $a_s$ will necessarily remove $a_i$, so it is impossible to transform $a$ into $[a_i]$.
    202 
    203 **Code (C++)**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 using namespace std;
    208  
    209 void solve(){
    210     int n;
    211     cin >> n;
    212     vector<int> a(n+1), pre(n+1, INT_MAX), suf(n+2);
    213     for(int i=1; i<=n; i++){
    214         cin >> a[i];
    215         pre[i] = min(pre[i-1], a[i]);
    216     }
    217     for(int i=n; i>=1; i--)
    218         suf[i] = max(suf[i+1], a[i]);
    219     for(int i=1; i<=n; i++)
    220         cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);
    221     cout << '\n';
    222 }
    223  
    224 int main(){
    225     int t;
    226     cin >> t;
    227     while(t--) solve();
    228 }
    229 ```
    230 
    231 **Rate the problem!**
    232 
    233 **Quality**
    234 
    235 * Excellent problem
    236 * Good problem
    237 * Average problem
    238 * Bad problem
    239 * Horrible problem
    240 
    241 **Difficulty**
    242 
    243 * Trivial problem
    244 * Easy problem
    245 * Average problem
    246 * Hard problem
    247 * Impossible problem
    248 
    249 #### [D — Binary String Battle](https://codeforces.com/contest/2123/problem/D)
    250 
    251 **Solution**
    252 
    253 **Step 1**
    254 
    255 Let $\mathrm{cnt}$ be the number of ones in $s$. Then clearly if $\mathrm{cnt} \leq k$, Alice can win immediately.
    256 
    257 **Step 2**
    258 
    259 Now, let's reframe Bob's win condition. Bob can win if and only if he can ensure that, before each of Alice's turns, there are at least $k+1$ ones in $s$. In other words, he has to ensure that after each of his turns, $\mathrm{cnt} \gt k$. Clearly, after each of Bob's turns, $\mathrm{cnt} \geq k$, since the entire substring he chose is all ones. So he only has to ensure that there is at least one other extra one in $s$.
    260 
    261 **Step 3**
    262 
    263 If $\mathrm{cnt} \gt k$ and $n\geq 2\cdot k$, then Bob can always win. Indeed, on each of Bob's turns, he can pick any existing one in $s$ to be the extra one. Now, he simply has to choose a substring which doesn't contain this extra one. Then there will be at least $k+1$ ones; the $k$ from the substring he chose, and the extra one. If $n\geq 2\cdot k$, then there must be at least $k$ elements to either the left or the right of this one, so Bob can choose such a substring.
    264 
    265 For example, consider $n=8$ and $k=4$. Suppose, before Bob's turn, $s=00100010$. Then Bob chooses any arbitrary existing one in $s$, say, the one in the third position. Now, he would like to choose a substring of length $k$ which does not include the third position. In this case, he can choose the substring $s[5, 8]$. Now, after his turn, $s=00101111$. As desired, there are at least five ones, in particular, the four in $s[5, 8]$ and the extra one in the third position.
    266 
    267 **Step 4**
    268 
    269 This motivates Alice's strategy as well. Suppose that $n \lt 2\cdot k$. Alice would like to make sure that Bob is losing value from his moves. Notice that every substring of length $k$ includes the element $s_k$. So, after Bob's first turn, we have that $s_k=1$. Now, a winning strategy for Alice is to leave $s_k=1$ until her last turn, and otherwise choose any $k$ arbitrary ones to flip. This guarantees that after every round, $\mathrm{cnt}$ decreases, because Alice flips $k$ ones, whereas Bob flips at most $k-1$ zeros, since $a_k$ is already one. Since $\mathrm{cnt}$ is nonnegative, finite, and decreasing, it must eventually reach zero.
    270 
    271 For example, consider $n=8$ and $k=5$. Suppose that before Alice's turn, $s=01111101$. Then we have that $\mathrm{cnt}=6$. Alice wants to choose any $5$ ones to flip, except for $s_5$. So she chooses to flip $s_2$, $s_3$, $s_4$, $s_6$, and $s_8$. Now, before Bob's turn, $s=00001000$. But any substring of length $5$ includes $s_5$, so Bob can only flip at most $4$ zeros. Suppose he chooses $s[2, 6]$. Then after his turn, we have that $s=01111100$. During this round, the value of $\mathrm{cnt}$ decreased from $6$ to $5$, as desired.
    272 
    273 **Code (C++)**
    274 
    275 ```
    276 #include <bits/stdc++.h>
    277 using namespace std;
    278  
    279 void solve(){
    280     int n, k, cnt = 0;
    281     string s;
    282     cin >> n >> k >> s;
    283     for(char c : s)
    284         if(c == '1')
    285             cnt++;
    286     cout << (cnt <= k || n < 2*k ? "Alice" : "Bob") << '\n';
    287 }
    288  
    289 int main(){
    290     ios::sync_with_stdio(false);
    291     cin.tie(NULL);
    292     int t;
    293     cin >> t;
    294     while(t--) solve();
    295 }
    296 ```
    297 
    298 **Rate the problem!**
    299 
    300 **Quality**
    301 
    302 * Excellent problem
    303 * Good problem
    304 * Average problem
    305 * Bad problem
    306 * Horrible problem
    307 
    308 **Difficulty**
    309 
    310 * Trivial problem
    311 * Easy problem
    312 * Average problem
    313 * Hard problem
    314 * Impossible problem
    315 
    316 #### [E — MEX Count](https://codeforces.com/contest/2123/problem/E)
    317 
    318 **Solution**
    319 
    320 **Step 1**
    321 
    322 Let $\mathrm{mex}$ be the original $\mathrm{MEX}$ of $a$. Clearly we cannot increase $\mathrm{MEX}(a)$ by removing elements. So, for every $0\leq i\leq \mathrm{mex}$, let's try to determine, for which $k$ can we make $\mathrm{MEX}(a) = i$?
    323 
    324 **Step 2**
    325 
    326 We must have $i\leq n-k$, since the $\mathrm{MEX}$ of an array cannot be greater than its size. Furthermore, we must have $\mathrm{freq}(i) \leq k$, since we have to remove all instances of $i$ in order to make it the $\mathrm{MEX}$ of $a$.
    327 
    328 **Step 3**
    329 
    330 Now, we claim that these are the only constraints. Indeed, suppose that $0\leq i\leq \mathrm{mex}$, $i\leq n-k$, and $\mathrm{freq}(i) \leq k$. We want to choose $n-k$ elements to keep. Since $i\leq \mathrm{mex}$, every element smaller than $i$ is in $a$, and since $i\leq n-k$, we can first choose one instance of every element less than $i$. Now, the $\mathrm{MEX}$ of our chosen elements is $i$, so we just need to choose the rest of the elements without affecting the $\mathrm{MEX}$. We can just choose elements arbitrarily, as long as we don't choose $i$. Since $\mathrm{freq}(i) \leq k$, we have enough spare elements to reach our $n-k$ quota without needing to choose $i$.
    331 
    332 **Step 4**
    333 
    334 Let's maintain a set of elements which can be $\mathrm{MEX}(a)$ after removing $k$ elements. As $k$ increases, how does this set change? If we compare the set from $k-1$ to $k$, we now have that the value $n-(k-1)$ is no longer legal, since $n-(k-1) \gt n-k$, so let's erase this element from our set. Furthermore, any elements with frequency $k$ might now be legal, so let's add them to our set as long as they are $\leq \min(\mathrm{mex}, n-k)$. Then we output the size of our set.
    335 
    336 **Code (C++)**
    337 
    338 ```
    339 #include <bits/stdc++.h>
    340 using namespace std;
    341  
    342 void solve(){
    343     int n;
    344     cin >> n;
    345     vector<int> a(n);
    346     map<int, int> freq;
    347     set<int> excl;
    348     for(int i=0; i<=n; i++)
    349         excl.insert(i);
    350     for(int i=0; i<n; i++){
    351         cin >> a[i];
    352         freq[a[i]]++;
    353         excl.erase(a[i]);
    354     }
    355     map<int, vector<int>> invfreq;
    356     for(pair<int, int> p : freq)
    357         invfreq[p.second].push_back(p.first);
    358     int mex = *excl.begin();
    359     set<int> vals;
    360     vals.insert(mex);
    361     for(int k=0; k<=n; k++){
    362         vals.erase(n-k+1);
    363         for(int i : invfreq[k])
    364             if(i <= min(mex, n-k))
    365                 vals.insert(i);
    366         cout << vals.size() << (k != n ? ' ' : '\n');
    367     }
    368 }
    369  
    370 int main(){
    371     int t;
    372     cin >> t;
    373     while(t--) solve();
    374 }
    375 ```
    376 
    377 **Step 4 (alternative)**
    378 
    379 Let $\mathrm{ans}_k$ be the number of possible values of $\mathrm{MEX}(a)$ after removing $k$ elements from $a$. Now, let $\mathrm{diff}$ be the difference array of $\mathrm{ans}$; that is, $\mathrm{diff}_k = \mathrm{ans}_k - \mathrm{ans}_{k-1}$. Then for all $0\leq i\leq \mathrm{mex}$, we have that $\mathrm{MEX}(a)$ can be $i$ if and only if $\mathrm{freq}(i) \leq k \leq n-i$. So we increment $\mathrm{diff}_{\mathrm{freq}(i)}$ and decrement $\mathrm{diff}_{n-i+1}$. Finally, we can reconstruct $\mathrm{ans}$ by taking the prefix sums of $\mathrm{diff}$.
    380 
    381 **Code (C++)**
    382 
    383 ```
    384 #include <bits/stdc++.h>
    385 using namespace std;
    386  
    387 void solve(){
    388     int n;
    389     cin >> n;
    390     vector<int> a(n), ans(n+1), diff(n+2);
    391     map<int, int> freq;
    392     for(int i=0; i<n; i++){
    393         cin >> a[i];
    394         freq[a[i]]++;
    395     }
    396     for(int i=0; i<=n; i++){
    397         diff[freq[i]]++;
    398         diff[n-i+1]--;
    399         if(!freq[i])
    400             break;
    401     }
    402     for(int k=0; k<=n; k++){
    403         ans[k] = (k ? ans[k-1] : 0) + diff[k];
    404         cout << ans[k] << (k != n ? ' ' : '\n');
    405     }
    406 }
    407  
    408 int main(){
    409     ios::sync_with_stdio(false);
    410     cin.tie(NULL);
    411     int t;
    412     cin >> t;
    413     while(t--) solve();
    414 }
    415 ```
    416 
    417 **Rate the problem!**
    418 
    419 **Quality**
    420 
    421 * Excellent problem
    422 * Good problem
    423 * Average problem
    424 * Bad problem
    425 * Horrible problem
    426 
    427 **Difficulty**
    428 
    429 * Trivial problem
    430 * Easy problem
    431 * Average problem
    432 * Hard problem
    433 * Impossible problem
    434 
    435 #### [F — Minimize Fixed Points](https://codeforces.com/contest/2123/problem/F)
    436 
    437 **Solution**
    438 
    439 **Step 1**
    440 
    441 Let's first find out which values must be fixed points. Clearly if $i$ is relatively prime to every $1\leq j\leq n$ with $j\neq i$, then $i$ must be a fixed point. This occurs when $i=1$, or when $i$ is prime and $2\cdot i \gt n$, because the smallest number that is not relatively prime to prime $i$ is $2\cdot i$.
    442 
    443 **Step 2**
    444 
    445 Now, let's try to construct $p$ such that these are the only fixed points. Consider the cycle decomposition of $p$. If we can ensure that all elements in a cycle, excluding the cycle $(1)$, share a common divisor greater than $1$, then $p$ is good.
    446 
    447 **Step 3**
    448 
    449 Notice that a fixed point corresponds to a cycle of length $1$. So we want as few cycles of length $1$ as possible. The prime $i$ are the most restrictive. Let's pair all prime $i$ with $2\cdot i$, if possible. Now, none of the primes $\leq \frac{n}{2}$ are fixed points. For the remaining composites, we have a lot more freedom. We can insert them into the cycle with any one of their prime factors; now, the composites are also not fixed points. Then all cycles share a common divisor, namely, the prime in that cycle, so $p$ is good.
    450 
    451 **Step 4**
    452 
    453 One systematic way to do this is to partition the elements from $1$ to $n$ based on their largest prime divisor. Then, indeed, all of the elements in the cycle containing prime $i$ are divisible by $i$, and $2\cdot i$ has largest prime factor $i$, so if $2\cdot i \leq n$, it will be in the cycle containing $i$.
    454 
    455 **Code (C++)**
    456 
    457 ```
    458 #include <bits/stdc++.h>
    459 using namespace std;
    460  
    461 vector<bool> comp(1e5+1);
    462 vector<int> primes;
    463  
    464 void sieve(){
    465     for(int i=2; i*i<=1e5; i++)
    466         if(!comp[i])
    467             for(int j=i*i; j<=1e5; j+=i)
    468                 comp[j] = true;
    469     for(int i=2; i<=1e5; i++)
    470         if(!comp[i])
    471             primes.push_back(i);
    472 }
    473  
    474 void solve(){
    475     int n;
    476     cin >> n;
    477     vector<int> p(n+1);
    478     for(auto it = primes.rbegin(); it != primes.rend(); ++it){
    479         vector<int> cycle;
    480         for(int i=*it; i<=n; i+=*it)
    481             if(!p[i])
    482                 cycle.push_back(i);
    483         for(int i=0; i<cycle.size(); i++)
    484             p[cycle[i]] = cycle[(i+1) % cycle.size()];
    485     }
    486     for(int i=1; i<=n; i++)
    487         if(!p[i])
    488             p[i] = i;
    489     for(int i=1; i<=n; i++)
    490         cout << p[i] << (i != n ? ' ' : '\n');
    491 }
    492  
    493 int main(){
    494     sieve();
    495     int t;
    496     cin >> t;
    497     while(t--) solve();
    498 }
    499 ```
    500 
    501 **Rate the problem!**
    502 
    503 **Quality**
    504 
    505 * Excellent problem
    506 * Good problem
    507 * Average problem
    508 * Bad problem
    509 * Horrible problem
    510 
    511 **Difficulty**
    512 
    513 * Trivial problem
    514 * Easy problem
    515 * Average problem
    516 * Hard problem
    517 * Impossible problem
    518 
    519 #### [G — Modular Sorting](https://codeforces.com/contest/2123/problem/G)
    520 
    521 **Solution**
    522 
    523 **Step 1**
    524 
    525 Let's first try to answer a query of type 2 in $O(n)$. We want to set $a_1$ as small as possible. Then we want to set $a_2$ to the smallest value which is $\geq a_1$. We continue to choose elements greedily, selecting the smallest legal value $a_i$ which is $\geq a_{i-1}$. If at any point there are no legal values, the answer is $\texttt{NO}$. Otherwise, the answer is $\texttt{YES}$.
    526 
    527 **Step 2**
    528 
    529 Now, let's try to characterize what values we can change $a_i$ into. Clearly $a_i\pmod{\gcd(k, m)}$ is invariant across operations.
    530 
    531 Next, we claim that all values less than $m$ which are congruent to $a_i\pmod{\gcd(k, m)}$ are reachable.
    532 
    533 First, let's consider the case where $\gcd(k, m) = 1$. Then we can set $a_i := a_i + 1\pmod m$ by applying the operation onto $a_i$, $x$ times, where $x$ is the [modular multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of $k\pmod m$. By repeatedly adding $1$, we can set $a_i$ to any value.
    534 
    535 Next, let's consider the case where $\gcd(k, m) \gt 1$. Then, if we imagine dividing $k$ and $m$ by $\gcd(k, m)$, we fall into the previous case; that is, we can set $a_i := a_i + \gcd(k, m)\pmod m$ by applying the operation onto $a_i$, $x$ times, where $x$ is the modular multiplicative inverse of $\frac{k}{\gcd(k, m)}\pmod{\frac{m}{\gcd(k, m)}}$. By repeatedly adding $\gcd(k, m)$, we can set $a_i$ to any value which falls into the same congruence class $\bmod{\gcd(k, m)}$.
    536 
    537 **Step 3**
    538 
    539 Let's try simulating the greedy process, where we repeatedly choose the smallest value which lies in the same congruence class $\bmod \gcd(k, m)$. Then if we have $a_n \lt m$, we can sort the array.
    540 
    541 However, we want to represent the array in a way such that we can update $a_i$ quickly, and check the end-result of $a_n$ after our greedy process quickly. Let $\mathrm{diff}$ be the difference array of $a$; that is, $\mathrm{diff}_i = a_i - a_{i-1}$ (for convenience, we will define $a_0 = 0$). Then, by telescoping sum, we have that $a_n$ is the sum of the elements of the difference array; that is, $a_n = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \dots + (a_2 - a_1) + (a_1 - a_0)$.
    542 
    543 Now, notice that $\mathrm{diff}_i$ is invariant $\bmod{\gcd(k, m)}$, and we also must have that $\mathrm{diff}_i$ is nonnegative for $a$ to be nondecreasing. So let's maintain the sum of the elements of the difference array, where each element is taken $\bmod{\gcd(k, m)}$, for each $k$. Then this is the final value of $a_n$ after simulating the greedy process. This is quick to update, since only two elements of the difference array are changed with each update.
    544 
    545 Finally, we observe that $\gcd(k, m)$ is always a divisor of $m$, so we only have to maintain and update $d(m)$ different values. This allows us to answer queries in $O(d(m))$ time.
    546 
    547 **Code (C++)**
    548 
    549 ```
    550 #include <bits/stdc++.h>
    551 using namespace std;
    552  
    553 int mod(int a, int m){
    554     return (a % m + m) % m;
    555 }
    556  
    557 void solve(){
    558     int n, m, q, op, i, x, k;
    559     cin >> n >> m >> q;
    560     vector<int> a(n+1);
    561     for(int i=1; i<=n; i++)
    562         cin >> a[i];
    563     map<int, long long> ans;
    564     for(int i=1; i*i<=m; i++)
    565         if(!(m % i)){
    566             ans[i] = 0;
    567             ans[m/i] = 0;
    568         }
    569     for(pair<int, int> p : ans)
    570         for(int i=1; i<=n; i++)
    571             ans[p.first] += mod(a[i] - a[i-1], p.first);
    572     while(q--){
    573         cin >> op;
    574         if(op == 1){
    575             cin >> i >> x;
    576             for(pair<int, int> p : ans){
    577                 ans[p.first] += mod(x - a[i-1], p.first) - mod(a[i] - a[i-1], p.first);
    578                 if(i != n)
    579                     ans[p.first] += mod(a[i+1] - x, p.first) - mod(a[i+1] - a[i], p.first);
    580             }
    581             a[i] = x;
    582         }
    583         else{
    584             cin >> k;
    585             cout << (ans[__gcd(k, m)] < m ? "YES" : "NO") << '\n';
    586         }
    587     }
    588 }
    589  
    590 int main(){
    591     ios::sync_with_stdio(false);
    592     cin.tie(NULL);
    593     int t;
    594     cin >> t;
    595     while(t--) solve();
    596 }
    597 ```
    598 
    599 **Step 3 (alternative)**
    600 
    601 Imagine putting all of the numbers from $0$ to $m-1$ in a grid, where each row is of size $\gcd(k, m)$. For example, if $k=8$ and $m=12$, our grid would look as follows:
    602 
    603 |  |  |  |  |
    604 | --- | --- | --- | --- |
    605 | 8 | 9 | 10 | 11 |
    606 | 4 | 5 | 6 | 7 |
    607 | 0 | 1 | 2 | 3 |
    608 
    609 Then observe that by applying operations, we can reach any element in the same column. Consider simulating the greedy process. Then we want to choose the lowest row possible; that is, we want to move up in the grid as infrequently as possible.
    610 
    611 Notice that we only have to move up in the grid if $a_i \pmod{\gcd(k, m)} \lt a_{i-1} \pmod{\gcd(k, m)}$, because then we cannot stay in the same row. We want to move up in the grid $ \lt \frac{m}{\gcd(k, m)}$ times. So let's maintain the number of times we are forced to move up in the grid, for each $k$. This is quick to update, since when we update $a_i$, we only have to compare it to the two adjacent values.
    612 
    613 Finally, we observe that $\gcd(k, m)$ is always a divisor of $m$, so we only have to maintain and update $d(m)$ different values. This allows us to answer queries in $O(d(m))$ time.
    614 
    615 **Code (C++)**
    616 
    617 ```
    618 #include <bits/stdc++.h>
    619 using namespace std;
    620  
    621 void solve(){
    622     int n, m, q, op, i, x, k;
    623     cin >> n >> m >> q;
    624     vector<int> a(n+1);
    625     for(int i=1; i<=n; i++)
    626         cin >> a[i];
    627     map<int, int> ans;
    628     for(int i=1; i*i<=m; i++)
    629         if(!(m % i)){
    630             ans[i] = 0;
    631             ans[m/i] = 0;
    632         }
    633     for(pair<int, int> p : ans)
    634         for(int i=1; i<=n; i++)
    635             ans[p.first] += (a[i] % p.first < a[i-1] % p.first);
    636     while(q--){
    637         cin >> op;
    638         if(op == 1){
    639             cin >> i >> x;
    640             for(pair<int, int> p : ans){
    641                 ans[p.first] += (x % p.first < a[i-1] % p.first) - (a[i] % p.first < a[i-1] % p.first);
    642                 if(i != n)
    643                     ans[p.first] += (a[i+1] % p.first < x % p.first) - (a[i+1] % p.first < a[i] % p.first);
    644             }
    645             a[i] = x;
    646         }
    647         else{
    648             cin >> k;
    649             cout << (ans[__gcd(k, m)] < m / __gcd(k, m) ? "YES" : "NO") << '\n';
    650         }
    651     }
    652 }
    653  
    654 int main(){
    655     ios::sync_with_stdio(false);
    656     cin.tie(NULL);
    657     int t;
    658     cin >> t;
    659     while(t--) solve();
    660 }
    661 ```
    662 
    663 **Rate the problem!**
    664 
    665 **Quality**
    666 
    667 * Excellent problem
    668 * Good problem
    669 * Average problem
    670 * Bad problem
    671 * Horrible problem
    672 
    673 **Difficulty**
    674 
    675 * Trivial problem
    676 * Easy problem
    677 * Average problem
    678 * Hard problem
    679 * Impossible problem