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