2060.md (27608B)
1 Source: https://codeforces.com/blog/entry/138342 2 3 **Rating Predictions** 4 5 | Predictor | A | B | C | D | E | F | G | 6 | --- | --- | --- | --- | --- | --- | --- | --- | 7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1000 | 1100 | 1300 | 1600 | 1900 | 2400 | 8 | [cry](/profile/cry "International Master cry") | 800 | 1000 | 1000 | 1200 | 1700 | 2000 | 2400 | 9 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 1000 | 1000 | 1400 | 1700 | 2000 | 2400 | 10 | [DivinePunishment](/profile/DivinePunishment "Expert DivinePunishment") | 800 | 1200 | 1100 | 1200 | 1700 | 2000 | 2300 | 11 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 1000 | 1000 | 1400 | 1800 | 2000 | 2400 | 12 | [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") | 800 | 1100 | 1200 | 1600 | 1800 | 2100 | 2400 | 13 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 1000 | 1500 | 1400 | 1300 | 2000 | 1900 | 14 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 900 | 1200 | 1400 | 1700 | 2100 | 2400 | 15 | [yoru_sacri](/profile/yoru_sacri "Candidate Master yoru_sacri") | 800 | 900 | 1300 | 1100 | 1700 | 2000 | | 16 | [efishel](/profile/efishel "Master efishel") | 800 | 800 | 800 | 1300 | 1600 | 1900 | 2100 | 17 | [Friedrich](/profile/Friedrich "Master Friedrich") | 800 | 800 | 1100 | 1300 | 1500 | 2100 | 2300 | 18 | [larush](/profile/larush "Expert larush") | 800 | 1000 | 1100 | 1200 | 1600 | 2000 | 2400 | 19 | [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") | 800 | 800 | 900 | 1200 | 1500 | 1900 | 2100 | 20 21 | | A | B | C | D | E | F | G | 22 | --- | --- | --- | --- | --- | --- | --- | --- | 23 | **Average** | 800 | 961.5 | 1100 | 1307.7 | 1630.8 | 2000 | 2291.7 | 24 | **Actual** | 800 | 1000 | 900 | 1100 | 1500 | 2200 | 2400 | 25 26 #### [2060A - Fibonacciness](/contest/2060/problem/A "Codeforces Round 998 (Div. 3)") 27 28 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 29 Analysis: [larush](/profile/larush "Expert larush") 30 31 **Solution 1** 32 33 We can notice that the possible values of $a_3$ ranges from $-99$ to $200$. Thus, we can iterate over all values of $a_3$ from $-99$ to $200$, and for each value, compute the Fibonacciness of the sequence. The maximal of all these values gives the solution to the problem. 34 35 Time Complexity : $O(3*a_{max})$ 36 37 **Solution 2** 38 39 $a_3$ can be represented as either of the following: 40 41 $a_3 = a_1 + a_2$, or 42 43 $a_3 = a_4 - a_2$, or 44 45 $a_3 = a_5 - a_4$. 46 47 These are at most 3 possible values. Notice that any value of $a_3$ which increases the Fibonacciness must belong to one of the above values (Think why!). So, in order to increase the Fibonacciness of the sequence, we should choose the most frequent of the above values. Then, in the end, we can calculate the Fibonacciness of the sequence after choosing the best value for $a_3$. 48 49 Time Complexity : $O(1)$ 50 51 **Code (C++)** 52 53 ``` 54 #include <bits/stdc++.h> 55 using namespace std; 56 using ll = long long; 57 using vll = vector <ll>; 58 using ii = pair <ll, ll>; 59 using vii = vector <ii>; 60 61 void tc () { 62 vll ve(4); 63 for (ll &i : ve) cin >> i; 64 set <ll> st; 65 st.insert(ve[3]-ve[2]); 66 st.insert(ve[2]-ve[1]); 67 st.insert(ve[0]+ve[1]); 68 cout << 4-st.size() << '\n'; 69 } 70 71 int main () { 72 cin.tie(nullptr) -> sync_with_stdio(false); 73 ll T; cin >> T; while (T--) { tc(); } 74 return 0; 75 } 76 ``` 77 78 **Rate The Problem!** 79 80 * Heat 81 * Mid 82 * Horrendous 83 * Didn't Solve 84 85 #### [2060B - Farmer John's Card Game](/contest/2060/problem/B "Codeforces Round 998 (Div. 3)") 86 87 Problem Credits: [Lilypad](/profile/Lilypad "Candidate Master Lilypad") 88 Analysis: [larush](/profile/larush "Expert larush") 89 90 **Solution** 91 92 Assume the cows are initially ordered correctly. A solution exists if the first cow can place $0$, the second cow can place $1$, and so on, continuing with the first cow placing $n$, the second cow placing $n+1$, and so forth. Observing the pattern, the first cow must be able to place ${0, n, 2n, \dots}$, the second ${1, n+1, 2n+1, \dots}$, and in general, the $i$-th cow (where $i \in [0, n-1]$) must be able to place ${i, n+i, 2n+i, \dots}$. 93 94 For each cow, sorting their cards reveals whether they satisfy this condition: the difference between adjacent cards in the sorted sequence must be $n$. If any cow's cards do not meet this criterion, the solution does not exist, and we output $-1$. 95 96 If the cows are not ordered correctly, we need to rearrange them. To construct the solution, find the index of the cow holding card $i$ for each $i \in [0, n-1]$. Since the cards of each cow are sorted, denote $\texttt{min_card}$ as the smallest card a cow holds. Using an array $p$, iterate over each cow $c$ from $0$ to $n-1$ and set $p_\texttt{min_card} = c$. Finally, iterate $i$ from $0$ to $n-1$ and output $p_i$. 97 98 Time Complexity : $O(nmlog(m))$. Note that sorting is not necessary, and a solution with complexity up to $O((nm)^2)$ will still pass. 99 100 **Code (C++)** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 using ll = long long; 106 using vll = vector <ll>; 107 using ii = pair <ll, ll>; 108 using vii = vector <ii>; 109 110 void tc () { 111 ll n, m; 112 cin >> n >> m; 113 vector <vll> ve(n, vll(m)); 114 vll p(n, -16); 115 bool val = true; 116 ll c = 0; 117 for (vll &we : ve) { 118 for (ll &i : we) cin >> i; 119 ll minN = *min_element(we.begin(), we.end()); 120 if (minN < n) p[minN] = c++; 121 val &= minN < n; 122 sort(we.begin(), we.end()); 123 ll last = we[0]-n; 124 for (ll i : we) { 125 val &= last+n == i; 126 last = i; 127 } 128 } 129 if (!val) { 130 cout << "-1\n"; 131 return; 132 } 133 for (ll i : p) cout << i+1 << ' '; 134 cout << '\n'; 135 } 136 137 int main () { 138 cin.tie(nullptr) -> sync_with_stdio(false); 139 ll T; cin >> T; while (T--) { tc(); } 140 return 0; 141 } 142 ``` 143 144 **Rate The Problem!** 145 146 * Heat 147 * Mid 148 * Horrendous 149 * Didn't Solve 150 151 #### [2060C - Game of Mathletes](/contest/2060/problem/C "Codeforces Round 998 (Div. 3)") 152 153 Problem Credits: [Friedrich](/profile/Friedrich "Master Friedrich") 154 Analysis: [macaquedev](/profile/macaquedev "Expert macaquedev") 155 156 **Solution** 157 158 Note that Bob has all the power in this game, because the order in which Alice picks numbers is irrelevant, since Bob can always pick the optimal number to give himself a point. Therefore, we can just ignore Alice and play the game from Bob's perspective. 159 160 From this point on, a "paired" number is any number $a$ on the blackboard such that there exists a $b$ on the blackboard such that $a+b=k$. 161 162 Bob's strategy is as follows: 163 164 * if Alice picks a paired number, Bob should pick the other number in the pair. 165 * if Alice picks an unpaired number, Bob can pick any other unpaired number, it doesn't matter which. 166 167 This always works because the number of "unpaired numbers" is always even, since $n$ is even and the number of "paired numbers" will always be even. Therefore, for every unpaired number Alice picks, Bob will always have an unpaired number to respond with. 168 169 Therefore, the final score is just the number of pairs in the input. To count them, use a map of counts $c$ such that $c_x$ is the number of occurrences of $x$ on the whiteboard. Then, for each number from $1$ to $\lfloor \frac{k}{2} \rfloor$, take the minimum of $c_x$ and $c_{k-x}$, and add that to the total. Remember the edge case where $k$ is even and $x = \frac{k}{2}$. The number of pairs here is just $\lfloor \frac{c_x}{2} \rfloor$. 170 171 **Code (C++)** 172 173 ``` 174 #include <bits/stdc++.h> 175 using namespace std; 176 using ll = long long; 177 using vll = vector <ll>; 178 using ii = pair <ll, ll>; 179 using vii = vector <ii>; 180 181 void tc () { 182 ll n, k; 183 cin >> n >> k; 184 vll ve(n); 185 for (ll &i : ve) cin >> i; 186 vll th(k+1, 0); 187 for (ll i : ve) { 188 if (i >= k) continue; 189 th[i]++; 190 } 191 ll ans = 0; 192 for (ll i = 1; i < k; i++) { 193 if (i == k-i) { 194 ans += th[i]/2; 195 continue; 196 } 197 ll minN = min(th[i], th[k-i]); 198 th[i] -= minN; 199 th[k-i] -= minN; 200 ans += minN; 201 } 202 cout << ans << '\n'; 203 } 204 205 int main () { 206 cin.tie(nullptr) -> sync_with_stdio(false); 207 ll T; cin >> T; while (T--) { tc(); } 208 return 0; 209 } 210 ``` 211 212 **Rate The Problem!** 213 214 * Heat 215 * Mid 216 * Horrendous 217 * Didn't Solve 218 219 #### [2060D - Subtract Min Sort](/contest/2060/problem/D "Codeforces Round 998 (Div. 3)") 220 221 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 222 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 223 224 **Solution** 225 226 For clarity, let's denote $op_i$ as an operation performed on $a_i$ and $a_{i+1}$. 227 228 Claim: if it is possible, then the sequence of operations $op_1,op_2,\ldots,op_{n-1}$ will sort the array. 229 230 Proof: Let $b$ be any sequence of operations that will sort the array. Let's transform the sequence $b$ such that it becomes $[op_1,op_2,\ldots,op_{n-1}]$. 231 232 First, let's note that an $op_i$ does nothing if $a_i=0$ or $a_{i+1}=0$. Additionally, after $op_i$, at least one of ${a_i,a_{i+1}}$ will become zero. Thus, we can remove all duplicates in $b$ without altering the result. 233 234 Now, let $x$ be the largest number such that $op_x$ is in $b$. Since at least one of $a_x,a_{x+1}$ will be zero, operations must be performed such that each of $a_1,a_2,\ldots,a_{x-1}$ are zero. Let $S$ be the set of indices with $i \lt x$ such that $op_i$ is not in $b$. Note that we can simply append each operation in $S$ at the end of $b$ without altering the result, since all elements before $a_x$ are already zero. 235 236 Our sequence of operations now contain a permutation of $op_1,op_2,\ldots,op_x$, and we have ensured that all of $a_1,a_2,\ldots,a_x=0$. Since the sequence is now sorted, we can in fact continue performing $op_{x+1},op_{x+2},\ldots,op_{n-1}$ in this order. Notice that this sequence of operations will keep our array sorted, as $op_y$ will make $a_y=0$ (since $a_y \lt a{y+1}$). 237 238 Let's show that we can rearrange our operations such that $1$ comes first. There are two cases: either $op_1$ comes before $op_2$, or $op_2$ comes before $op_1$. In the first case, notice that no operation done before $op_1$ will impact either the value of $a_1$ or $a_2$, so rearranging such that $op_1$ comes first does not impact the final results. In the second case, notice that after $op_2$ is done, we must have $a_1=a_2$, as otherwise $op_1$ will not simultaneously make $a_1=a_2=0$. This implies that right before $op_2$ is performed, we must have $a_1+a_3=a_2$. Then, rearranging the operations such that $op_1$ comes first will not impact the final result. 239 240 Using the same line of reasoning, we can make $op_2$ the second operation, then $op_3$, and so on. To solve the problem, we can simply simulate the operations in this order, and then check if the array is sorted at the end. 241 242 Time Complexity : $O(n)$ 243 244 **Code (C++)** 245 246 ``` 247 #include <bits/stdc++.h> 248 using namespace std; 249 using ll = long long; 250 using vll = vector <ll>; 251 using ii = pair <ll, ll>; 252 using vii = vector <ii>; 253 254 void tc () { 255 ll n; 256 cin >> n; 257 vll ve(n); 258 for (ll &i : ve) cin >> i; 259 ll j = 0; 260 for (ll i = 1; i < n; i++) { 261 if (ve[i-1] > ve[i]) j = i; 262 } 263 if (j == 0) { // all done 264 cout << "YES\n"; 265 return; 266 } 267 auto fop = [&](ll i) { 268 ll minN = min(ve[i], ve[i+1]); 269 ve[i] -= minN; 270 ve[i+1] -= minN; 271 }; 272 for (ll i = 0; i < j; i++) { 273 fop(i); 274 } 275 cout << (is_sorted(ve.begin(), ve.end()) ? "YES" : "NO") << '\n'; 276 } 277 278 int main () { 279 cin.tie(nullptr) -> sync_with_stdio(false); 280 ll T; cin >> T; while (T--) { tc(); } 281 return 0; 282 } 283 ``` 284 285 **Rate The Problem!** 286 287 * Heat 288 * Mid 289 * Horrendous 290 * Didn't Solve 291 292 #### [2060E - Graph Composition](/contest/2060/problem/E "Codeforces Round 998 (Div. 3)") 293 294 Problem Credits: [Friedrich](/profile/Friedrich "Master Friedrich") 295 Analysis: [DivinePunishment](/profile/DivinePunishment "Expert DivinePunishment") 296 297 **Solution** 298 299 Let's solve the problem for each operation. 300 301 First, consider the operation that removes an edge from $ F $. Divide $ G $ into its connected components and assign each vertex a component index. Then, for each edge in $ F $, if it connects vertices with different component indices, remove it and increment the operation count. 302 303 This guarantees no path between $ x $ and $ y $ in $ F $ if there is none in $ G $. Next, to ensure a path exists between $ x $ and $ y $ in $ F $ if there is one in $ G $, we divide $ F $ into connected components. After removing excess edges, each component of $ F $ only contains vertices of the same component index. The number of operations needed now is the difference between the number of connected components in $ F $ and $ G $. 304 305 All operations can be efficiently performed using DFS or DSU. 306 307 **Code (C++)** 308 309 ``` 310 #include <bits/stdc++.h> 311 312 #define int long long 313 #define pb emplace_back 314 #define mp make_pair 315 #define x first 316 #define y second 317 #define all(a) a.begin(), a.end() 318 #define rall(a) a.rbegin(), a.rend() 319 320 typedef long double ld; 321 typedef long long ll; 322 323 using namespace std; 324 325 mt19937 rnd(time(nullptr)); 326 327 const int inf = 1e9; 328 const int M = 1e9 + 7; 329 const ld pi = atan2(0, -1); 330 const ld eps = 1e-6; 331 332 void Gdfs(int v, vector<vector<int>> &sl, vector<int> &col, int c){ 333 col[v] = c; 334 for(int u: sl[v]){ 335 if(col[u] == 0){ 336 Gdfs(u, sl, col, c); 337 } 338 } 339 } 340 341 int Fdfs(int v, vector<vector<int>> &sl, vector<int> &col, vector<int> &old_col, int c){ 342 col[v] = c; 343 int res = 0; 344 for(int u: sl[v]){ 345 if(col[u] == 0){ 346 if(old_col[u] != c) res++; 347 else res += Fdfs(u, sl, col, old_col, c); 348 } 349 } 350 return res; 351 } 352 353 void read_con_list(vector<vector<int>> &sl, int m){ 354 for(int i = 0; i < m; ++i){ 355 int u, v; 356 cin >> u >> v; 357 sl[--u].emplace_back(--v); 358 sl[v].emplace_back(u); 359 } 360 } 361 362 void solve(int tc){ 363 int n, mf, mg; 364 cin >> n >> mf >> mg; 365 vector<vector<int>> fsl(n), gsl(n); 366 read_con_list(fsl, mf); 367 read_con_list(gsl, mg); 368 369 vector<int> fcol(n), gcol(n); 370 int ans = 0; 371 for(int i = 0; i < n; ++i){ 372 if(gcol[i] == 0){ 373 Gdfs(i, gsl, gcol, i + 1); 374 } 375 if(fcol[i] == 0){ 376 ans += Fdfs(i, fsl, fcol, gcol, gcol[i]); 377 if(gcol[i] < i + 1) ans++; 378 } 379 } 380 cout << ans; 381 } 382 383 bool multi = true; 384 385 signed main() { 386 ios_base::sync_with_stdio(false); 387 cin.tie(nullptr); 388 cout.tie(nullptr); 389 390 int t = 1; 391 if (multi)cin >> t; 392 for (int i = 1; i <= t; ++i) { 393 solve(i); 394 cout << "\n"; 395 } 396 return 0; 397 } 398 ``` 399 400 **Rate The Problem!** 401 402 * Heat 403 * Mid 404 * Horrendous 405 * Didn't Solve 406 407 #### [2060F - Multiplicative Arrays](/contest/2060/problem/F "Codeforces Round 998 (Div. 3)") 408 409 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED"), [cry](/profile/cry "International Master cry") 410 Analysis: [-firefly-](/profile/-firefly- "Master -firefly-") 411 412 **Hint 1** 413 414 When $n$ is large, many of the array's elements will be $1$. 415 416 **Hint 2** 417 418 The number of non-$1$ elements can't be so large. 419 420 **Hint 3** 421 422 Try to precompute all arrays without $1$ and then use combinatorics. 423 424 **Solution 1** 425 426 The naive solution is to define $f_k(n)$ as the number of arrays containing $n$ elements with a product of $k$. We could then try to compute this by considering the last element of the array among the divisors of $k$, giving us: 427 428 $ f_k(n)=\sum_{j|k}f_j(n-1), $ 429 430 with $f_k(1)=1$. 431 432 The answers would then be $\sum_{i=1}^{n}f_1(i),\sum_{i=1}^{n}f_2(i),\dots,\sum_{i=1}^{n}f_k(i)$. However, this leads to an $O(nk\log k)$ solution, which exceeds our time constraints. We need to optimize this approach. 433 434 We can prove that there are at most $16$ non-$1$ elements in our arrays. This is because: 435 436 * The prime factorization of $k=p_1p_2\cdots p_t$ divides $k$ into the most non-$1$ elements. 437 * With $17$ non-$1$ elements, the smallest possible value would be $k=2^{17}=131072 \gt 10^5$. 438 439 Based on this observation, we can define our dynamic programming state as: 440 441 * Let $dp[i][j]$ represent the number of arrays with product $i$ containing only $j$ **non-$1$** elements. 442 * The recurrence relation becomes: $dp[i][j]=\sum_{p|i,p \gt 1}dp[\frac{i}{p}][j-1]$. 443 * Base case: $dp[i][1]=1$ for $i \gt 1$. 444 445 This computation has a time complexity of $O(k\log^2k)$, as we perform $\sum_{j=1}^{k}d(j)=O(k\log{k})$ additions for each $i$. 446 447 To calculate $f_k(n)$, we: 448 449 1. Enumerate the number of non-$1$ elements from $1$ to $16$. 450 2. For $j$ non-$1$ elements in the array: 451 452 * We have $n-j$ elements that are $1$. 453 * We need to choose $j$ positions for non-$1$ elements. 454 * Fill these positions with $dp[k][j]$ possible sequences. 455 456 This gives us: 457 458 $ f_k(n)=\sum_{j=1}^{16}\binom{n}{j}dp[k][j]. $ 459 460 Therefore: 461 462 $ \begin{align*} &\sum_{i=1}^{n}f_k(n)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{16}\binom{i}{j}dp[k][j]\\ =&\sum_{j=1}^{16}\left(dp[k][j]\sum_{i=1}^{n}\binom{i}{j}\right)\\ =&\sum_{j=1}^{16}\binom{n+1}{j+1}dp[k][j]. \end{align*} $ 463 464 Note that $\sum_{i=1}^{n}\binom{i}{j} = \binom{n+1}{j+1}$ is given by the [Hockey Stick Identity](https://en.wikipedia.org/wiki/Hockey-stick_identity). 465 466 Each answer can be calculated in $O(\log^2k)$ time, giving an overall time complexity of $O(k\log^2k)$. 467 468 **Solution 2** 469 470 Let's revisit the naive approach and define $S_k(n)=\sum_{i=1}^{n}f_{k}(n)$ as our answers. We can observe: 471 472 $ \begin{align} f_{k}(n)&=\sum_{j|k}f_j(n-1)\nonumber\\ \Leftrightarrow f_{k}(n)-f_{k}(n-1)&=\sum_{j|k,j \lt k}f_j(n-1). \end{align} $ 473 474 Accumulating Formula $(1)$ yields: 475 476 $ \begin{align} &&\sum_{i=2}^{n}\left(f_{k}(i)-f_{k}(i-1)\right)&=\sum_{i=2}^{n}\sum_{j|k,j \lt k}f_j(i-1)\nonumber\\ &\Leftrightarrow& f_{k}(n)-f_{k}(1)&=\sum_{j|k,j \lt k}\sum_{i=1}^{n-1}f_{j}(i)\nonumber\\ &\Leftrightarrow& f_{k}(n)&=\sum_{j|k,j \lt k}S_j(n-1)+1. \end{align} $ 477 478 By induction, we can prove that both $f_{k}(n)$ and $S_k(n)$ are polynomials. Let's denote: 479 480 * Degree of $f_k(n)$ as $p(k)$. 481 * Degree of $S_k(n)$ as $q(k)$. 482 483 From the definition of $S_k(n)$, we have $q(k)=p(k)+1$. Formula $(2)$ gives us: 484 485 $ p(k)=\max_{j|k,j \lt k}q(k)=\max_{j|k,j \lt k}p(j)+1, $ 486 487 with $p(1)=0$. By induction, we can show that $p(k)$ equals the number of primes in $k$'s prime factorization. Therefore, $p(k)\le16$ and $q(k)\le17$. 488 489 Since $q(k)$ doesn't exceed $17$, we can: 490 491 1. Precompute $S_k(1),S_k(2),S_k(3),\dots,S_k(18)$. 492 2. Use [Lagrange Interpolation](https://codeforces.com/blog/entry/82953) to compute any $S_k(n)$. 493 494 This also yields an $O(k\log^2k)$ time complexity. 495 496 **Code (C#)** 497 498 ``` 499 using System; 500 using System.Collections.Generic; 501 using System.ComponentModel; 502 using System.Linq; 503 using System.Runtime.Serialization.Json; 504 using System.Text; 505 using System.Threading.Tasks; 506 using TemplateF; 507 508 #if !PROBLEM 509 SolutionF a = new(); 510 a.Solve(); 511 #endif 512 513 namespace TemplateF 514 { 515 internal class SolutionF 516 { 517 private readonly StreamReader sr = new(Console.OpenStandardInput()); 518 private T Read<T>() 519 where T : struct, IConvertible 520 { 521 char c; 522 dynamic res = default(T); 523 dynamic sign = 1; 524 while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read(); 525 if (!sr.EndOfStream && (char)sr.Peek() == '-') 526 { 527 sr.Read(); 528 sign = -1; 529 } 530 while (!sr.EndOfStream && char.IsDigit((char)sr.Peek())) 531 { 532 c = (char)sr.Read(); 533 res = res * 10 + c - '0'; 534 } 535 return res * sign; 536 } 537 538 private T[] ReadArray<T>(int n) 539 where T : struct, IConvertible 540 { 541 T[] arr = new T[n]; 542 for (int i = 0; i < n; ++i) arr[i] = Read<T>(); 543 return arr; 544 } 545 546 public void Solve() 547 { 548 StringBuilder output = new(); 549 const int maxk = 100000, mod = 998244353, bw = 20; 550 List<int>[] d = new List<int>[maxk + 1]; 551 for (int i = 1; i <= maxk; ++i) d[i] = new() { 1 }; 552 for (int i = 2; i <= maxk; ++i) { 553 for (int j = i; j <= maxk; j += i) d[j].Add(i); 554 } 555 int[,] dp = new int[bw + 1, maxk + 1], S = new int[bw + 1, maxk + 1]; 556 for (int k = 1; k <= maxk; ++k) dp[1, k] = S[1, k] = 1; 557 for (int i = 2; i <= bw; ++i) { 558 for (int j = 1; j <= maxk; ++j) { 559 foreach (var k in d[j]) { 560 dp[i, j] += dp[i - 1, k]; 561 dp[i, j] %= mod; 562 } 563 S[i, j] = (S[i - 1, j] + dp[i, j]) % mod; 564 } 565 } 566 int T = Read<int>(); 567 while (T-- > 0) 568 { 569 int k = Read<int>(), n = Read<int>(); 570 if (n <= bw) { 571 for (int j = 1; j <= k; ++j) output.Append(S[n, j]).Append(' '); 572 } else { 573 int _k = k; 574 for (k = 1; k <= _k; ++k) { 575 long ans = 0; 576 for (int i = 1; i <= bw; ++i) { 577 long t = S[i, k]; 578 for (int j = 1; j <= bw; ++j) { 579 if (j == i) continue; 580 t *= n - j; 581 t %= mod; 582 t *= Inv((mod + i - j) % mod, mod); 583 t %= mod; 584 } 585 ans = (ans + t) % mod; 586 } 587 output.Append(ans).Append(' '); 588 } 589 } 590 output.AppendLine(); 591 } 592 Console.Write(output.ToString()); 593 } 594 public static long Inv(long a, long Mod) { 595 long u = 0, v = 1, m = Mod; 596 while (a > 0) { 597 long t = m / a; 598 m -= t * a; (a, m) = (m, a); 599 u -= t * v; (u, v) = (v, u); 600 } 601 return (u % Mod + Mod) % Mod; 602 } 603 } 604 } 605 ``` 606 607 **Rate The Problem!** 608 609 * Heat 610 * Mid 611 * Horrendous 612 * Didn't Solve 613 614 #### [2060G - Bugged Sort](/contest/2060/problem/G "Codeforces Round 998 (Div. 3)") 615 616 Problem Credits: [chromate00](/profile/chromate00 "Expert chromate00") 617 Analysis: [macaquedev](/profile/macaquedev "Expert macaquedev") 618 619 **Hint 1** 620 621 Consider $(a_i, b_i)$ as the $i$-th pair. Can two elements ever become unpaired? 622 623 **Answer** 624 625 No. Every operation keeps the pairs intact. The best way to think about the operation is like this: 626 627 1. Swap the pairs at index $i$ and index $j$. 628 2. Flip each pair (swap $a_i$ with $b_i$, and $a_j$ with $b_j$). 629 630 **Hint 2** 631 632 The operations allow us to swap two pairs, but it also results in both of them getting flipped. Is there any way to swap two pairs *without* flipping anything? 633 634 **Answer** 635 636 It turns out there is, and there always is, because $n \geq 3$. To swap pairs $i$ and $j$, follow this procedure: 637 638 1. Pick any index $k$, where $k \ne i$ and $k \ne j$. 639 2. Do the operation on $i$ and $k$. 640 3. Do the operation on $j$ and $k$. 641 4. Finally, do the operation on $i$ and $k$ again. This results in the pair at index $k$ being unchanged, and the pairs at $i$ and $j$ simply being swapped. 642 643  644 645 **Hint 3** 646 647 Can you flip two pairs without swapping them? 648 649 **Answer** 650 651 Yes. Just perform the operation on pairs $i$ and $j$, and then follow the procedure from Hint 2, and you are effectively swapping, then "swapping and flipping", therefore the final result is simply a flip of two pairs. 652 653  654 655 **Hint 4** 656 657 Can you flip one pair on its own? 658 659 **Answer** 660 661 No, this is not possible due to the parity invariant. The operation involves performing two flips at the same time, which means that it is impossible to end up in a situation where the number of flips is odd. 662 663 **Solution** 664 665 Read the hints first. 666 667 **Key observation:** 668 669 In the final solution, the pairs must be sorted in increasing order of $\min(a_i, b_i)$. We prove this by contradiction. Suppose there exists a pair $(a_i, b_i)$, where $a_i \lt b_i$ and $a_i$ is smaller than the minimum element in the previous pair. In this case, it becomes impossible to place this pair after the previous one, as $a_i$ would always be smaller than the preceding element, regardless of orientation. 670 671 Since all $a_i$ and $b_i$ are distinct, there is exactly one valid final ordering of the pairs. Moreover, this ordering is always reachable because we previously proved that any two pairs can be swapped without flipping their elements. Since swapping any two items in an array an arbitrary number of times allows for sorting by definition, we can sort the pairs in this order. Thus, the solution is to initially sort the pairs based on $\min(a_i, b_i)$. 672 673 **Solution:** 674 675 The problem simplifies to determining whether flipping pairs allows sorting. We can solve this using dynamic programming (DP), defined as follows: 676 677 $dp[1][i] = 1$ if it's possible to sort up and including pair $i$ using an even number of flips, where pair $i$ is not flipped. 678 $dp[2][i] = 1$ if it's possible to sort up and including pair $i$ using an even number of flips, where pair $i$ is flipped. 679 $dp[3][i] = 1$ if it's possible to sort up and including pair $i$ using an odd number of flips, where pair $i$ is not flipped. 680 $dp[4][i] = 1$ if it's possible to sort up and including pair $i$ using an odd number of flips, where pair $i$ is flipped. 681 682 The base cases are as follows: 683 684 $dp[1][1] = 1$, because this represents the state where the first pair is not flipped, resulting in zero flips (which is even) 685 $dp[4][1] = 1$, because this represents the state where the first pair is flipped, resulting in one flip (which is odd). 686 687 There are eight possible transitions, as you can reach each of the four states from two previous states: you either choose to flip the current element or you don't. 688 689 The final answer is $dp[1][n]$ $\texttt{OR}$ $dp[2][n]$, because by Hints 3 and 4, we can only reach states where an even number of pairs are flipped from the starting position. 690 691 **Code (C++)** 692 693 ``` 694 #include <bits/stdc++.h> 695 using namespace std; 696 #define F0R(i, n) for (int i = 0; i < n; i++) 697 #define FOR(i, m, n) for (int i = m; i < n; i++) 698 #define print pair<int, int> 699 #define vp vector<print> 700 #define ALL(x) (x).begin(), (x).end() 701 702 void solve() 703 { 704 int n; 705 cin >> n; 706 vp pairs(n); 707 F0R(i, n) 708 { 709 cin >> pairs[i].first; 710 } 711 F0R(i, n) 712 { 713 cin >> pairs[i].second; 714 } 715 716 sort(ALL(pairs), [](print a, print b) 717 { return min(a.first, a.second) < min(b.first, b.second); }); 718 719 vector<vector<int>> dp(4, vector<int>(n, 0)); 720 dp[0][0] = 1; 721 dp[3][0] = 1; 722 FOR(i, 1, n) 723 { 724 if (pairs[i - 1].first < pairs[i].first and pairs[i - 1].second < pairs[i].second) 725 { 726 dp[0][i] |= dp[0][i - 1]; 727 dp[1][i] |= dp[1][i - 1]; 728 dp[2][i] |= dp[3][i - 1]; 729 dp[3][i] |= dp[2][i - 1]; 730 } 731 if (pairs[i - 1].first < pairs[i].second and pairs[i - 1].second < pairs[i].first) 732 { 733 dp[0][i] |= dp[2][i - 1]; 734 dp[1][i] |= dp[3][i - 1]; 735 dp[2][i] |= dp[1][i - 1]; 736 dp[3][i] |= dp[0][i - 1]; 737 } 738 } 739 cout << ((dp[0][n - 1] | dp[2][n - 1]) ? "YES" : "NO") << endl; 740 } 741 742 signed main() 743 { 744 int tests; 745 cin >> tests; 746 F0R(test, tests) 747 { 748 solve(); 749 } 750 751 return 0; 752 } 753 ``` 754 755 **Rate The Problem!** 756 757 * Heat 758 * Mid 759 * Horrendous 760 * Didn't Solve