2171.md (24376B)
1 Source: https://codeforces.com/blog/entry/148567 2 3 I hope you all enjoyed the contest! Special thanks to 4 5 * [djm03178](/profile/djm03178 "Master djm03178") for suggesting the inclusion of C1, and for helping with test writing on all problems, especially F 6 * [satyam343](/profile/satyam343 "Master satyam343") for helping me solve H 7 * [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069") for providing the idea for one of the solutions to E 8 * [Intellegent](/profile/Intellegent "Grandmaster Intellegent") for providing one of the proofs for the solution to D, and for providing the idea for one of the solutions to F 9 10 **Rate the contest!** 11 12 **Quality** 13 14 * Excellent contest 15 * Good contest 16 * Average contest 17 * Bad contest 18 * Horrible contest 19 20 **Difficulty** 21 22 * Trivial contest 23 * Easy contest 24 * Average contest 25 * Hard contest 26 * Impossible contest 27 28 #### [A — Shizuku Hoshikawa and Farm Legs](https://codeforces.com/contest/2171/problem/A) 29 30 **Solution** 31 32 **Step 1** 33 34 If $n$ is odd, there are clearly zero possible configurations. 35 36 **Step 2** 37 38 Suppose $n$ is even. Then consider the number of legs that belong to cows. This can be any multiple of $4$ that is less than or equal to $n$. The remaining legs will belong to chickens. Thus, the answer is equal to the number of nonnegative multiples of $4$ which are less than or equal to $n$, which is given by $\lfloor \frac{n}{4} \rfloor + 1$. 39 40 **Code (C++)** 41 42 ``` 43 #include <bits/stdc++.h> 44 using namespace std; 45 46 void solve(){ 47 int n; 48 cin >> n; 49 cout << (n & 1 ? 0 : n/4+1) << '\n'; 50 } 51 52 int main(){ 53 ios::sync_with_stdio(false); 54 cin.tie(NULL); 55 int t; 56 cin >> t; 57 while(t--) solve(); 58 } 59 ``` 60 61 **Rate the problem!** 62 63 **Quality** 64 65 * Excellent problem 66 * Good problem 67 * Average problem 68 * Bad problem 69 * Horrible problem 70 71 **Difficulty** 72 73 * Trivial problem 74 * Easy problem 75 * Average problem 76 * Hard problem 77 * Impossible problem 78 79 #### [B — Yuu Koito and Minimum Absolute Sum](https://codeforces.com/contest/2171/problem/B) 80 81 **Solution** 82 83 **Step 1** 84 85 The given expression is equal to $|(a_2 - a_1) + (a_3 - a_2) + \dots + (a_n - a_{n-1})|$. 86 87 **Step 2** 88 89 This simplifies to $|a_n - a_1|$. 90 91 **Step 3** 92 93 We want to minimize the absolute difference between the first and last elements. To do so, if one of them is set and the other one isn't, we will set them to be equal. Now, the remaining blank elements do not affect the given expression, so we can set them all to be zero. 94 95 **Code (C++)** 96 97 ``` 98 #include <bits/stdc++.h> 99 using namespace std; 100 101 void solve(){ 102 int n; 103 cin >> n; 104 vector<int> a(n); 105 for(int i=0; i<n; i++) 106 cin >> a[i]; 107 if(a[0] == -1) 108 a[0] = a[n-1]; 109 if(a[n-1] == -1) 110 a[n-1] = a[0]; 111 for(int i=0; i<n; i++) 112 if(a[i] == -1) 113 a[i] = 0; 114 cout << abs(a[n-1] - a[0]) << '\n'; 115 for(int i=0; i<n; i++) 116 cout << a[i] << " \n"[i == n-1]; 117 } 118 119 int main(){ 120 ios::sync_with_stdio(false); 121 cin.tie(NULL); 122 int t; 123 cin >> t; 124 while(t--) solve(); 125 } 126 ``` 127 128 **Rate the problem!** 129 130 **Quality** 131 132 * Excellent problem 133 * Good problem 134 * Average problem 135 * Bad problem 136 * Horrible problem 137 138 **Difficulty** 139 140 * Trivial problem 141 * Easy problem 142 * Average problem 143 * Hard problem 144 * Impossible problem 145 146 #### [C1/C2 — Renako Amaori and XOR Game](https://codeforces.com/contest/2171/problem/C2) 147 148 **Solution (Easy Version)** 149 150 **Step 1** 151 152 The $\mathrm{XOR}$ of all $2n$ elements is invariant. Note that this is also equal to the $\mathrm{XOR}$ between Ajisai and Mai's final scores. Therefore, if this value is zero, the game ends in a tie. Otherwise, Ajisai and Mai's final scores will differ, so the game does not end in a tie. 153 154 **Step 2** 155 156 Suppose the $\mathrm{XOR}$ of all $2n$ elements is nonzero. If $a_i = b_i$, then the $i$-th turn is useless. Now, consider the **largest** $i$ such that $a_i \neq b_i$. This person can control whose score is $0$ and whose score is $1$. Since all future turns are useless, they win. Therefore, if the largest $i$ satisfying $a_i \neq b_i$ is odd, Ajisai wins. Otherwise, Mai wins. 157 158 **Code (C++)** 159 160 ``` 161 #include <bits/stdc++.h> 162 using namespace std; 163 164 void solve(){ 165 int n, x = 0, idx; 166 cin >> n; 167 vector<int> a(n), b(n); 168 for(int i=0; i<n; i++){ 169 cin >> a[i]; 170 x ^= a[i]; 171 } 172 for(int i=0; i<n; i++){ 173 cin >> b[i]; 174 x ^= b[i]; 175 } 176 if(!x){ 177 cout << "Tie" << '\n'; 178 return; 179 } 180 for(int i=0; i<n; i++) 181 if(a[i] ^ b[i]) 182 idx = i; 183 cout << (idx & 1 ? "Mai" : "Ajisai") << '\n'; 184 } 185 186 int main(){ 187 ios::sync_with_stdio(false); 188 cin.tie(NULL); 189 int t; 190 cin >> t; 191 while(t--) solve(); 192 } 193 ``` 194 195 **Solution (Hard Version)** 196 197 **Step 1** 198 199 The $\mathrm{XOR}$ of all $2n$ elements is equal to the $\mathrm{XOR}$ between Ajisai and Mai's final scores. Therefore, we know exactly what bits their scores will differ in. 200 201 **Step 2** 202 203 The most significant of these bits dictates who wins the game. Therefore, we can apply the solution from the easy version to the most significant bit of the $\mathrm{XOR}$ of all $2n$ elements. 204 205 **Code (C++)** 206 207 ``` 208 #include <bits/stdc++.h> 209 using namespace std; 210 211 void solve(){ 212 int n, x = 0, bit, idx; 213 cin >> n; 214 vector<int> a(n), b(n); 215 for(int i=0; i<n; i++){ 216 cin >> a[i]; 217 x ^= a[i]; 218 } 219 for(int i=0; i<n; i++){ 220 cin >> b[i]; 221 x ^= b[i]; 222 } 223 if(!x){ 224 cout << "Tie" << '\n'; 225 return; 226 } 227 for(int i=0; i<20; i++) 228 if(x&1<<i) 229 bit = i; 230 for(int i=0; i<n; i++) 231 if((a[i]^b[i])&1<<bit) 232 idx = i; 233 cout << (idx & 1 ? "Mai" : "Ajisai") << '\n'; 234 } 235 236 int main(){ 237 ios::sync_with_stdio(false); 238 cin.tie(NULL); 239 int t; 240 cin >> t; 241 while(t--) solve(); 242 } 243 ``` 244 245 **Bonus** 246 247 Can you find the difference between the players' scores, where the winner tries to maximize this value and the loser tries to minimize this value? I don't have a solution, but I suspect this may be impossible in polynomial time. Leave a comment if you have either a solution or a proof that it's impossible. 248 249 **Rate the problem!** 250 251 **Quality** 252 253 * Excellent problem 254 * Good problem 255 * Average problem 256 * Bad problem 257 * Horrible problem 258 259 **Difficulty** 260 261 * Trivial problem 262 * Easy problem 263 * Average problem 264 * Hard problem 265 * Impossible problem 266 267 #### [D/F — Rae Taylor and Trees](https://codeforces.com/contest/2171/problem/F) 268 269 **Solution (Easy Version)** 270 271 **Step 1** 272 273 Let $\mathrm{pre}_i$ denote the **minimum** of $p_1, \dots, p_i$, and let $\mathrm{suf}_i$ denote the **maximum** of $p_i, \dots, p_n$. Then if there exists some $i$ such that $\mathrm{pre}_{i-1} \gt \mathrm{suf}_i$, then the answer is $\texttt{No}$. This is because there is no edge from any value in $p_1, \dots, p_{i-1}$ to any value in $p_i, \dots, p_n$. 274 275 **Step 2** 276 277 Otherwise, suppose that for every $i$, we have that $\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$. Then for every $i$, we have that there exists a path from $p_{i-1}$ to $p_i$, by going from $p_{i-1}$ to $\mathrm{pre}_{i-1}$ to $\mathrm{suf}_i$ to $p_i$. Since the graph consisting of these paths is connected, it must have some spanning tree, so the answer is $\texttt{Yes}$. 278 279 **Code (C++)** 280 281 ``` 282 #include <bits/stdc++.h> 283 using namespace std; 284 285 void solve(){ 286 int n; 287 cin >> n; 288 vector<int> p(n+1), pre(n+1, n), suf(n+2); 289 for(int i=1; i<=n; i++){ 290 cin >> p[i]; 291 pre[i] = min(pre[i-1], p[i]); 292 } 293 for(int i=n; i>=1; i--) 294 suf[i] = max(suf[i+1], p[i]); 295 for(int i=2; i<=n; i++) 296 if(pre[i-1] > suf[i]){ 297 cout << "No" << '\n'; 298 return; 299 } 300 cout << "Yes" << '\n'; 301 } 302 303 int main(){ 304 ios::sync_with_stdio(false); 305 cin.tie(NULL); 306 int t; 307 cin >> t; 308 while(t--) solve(); 309 } 310 ``` 311 312 **Solution (Hard Version)** 313 314 **Step 1** 315 316 Suppose that $\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$ for all $i$. Let $s_1 \lt \dots \lt s_k = n$ denote the indices satisfying $p_i = \mathrm{suf}_i$, that is, the suffix maxes of $p$. Then let's partition $p$ into blocks ending at each $s_i$. Now, consider a block consisting of $p[l, r]$ for $l=s_{i-1}+1$ and $r=s_i$. We have that $\mathrm{suf}_l = \mathrm{suf}_r = p_r$ by construction, which means that all values in $p[l, r-1]$ are less than $p_r$. So we can connect all of these values to $p_r$. 317 318 **Step 2** 319 320 Now, each block is connected, so it suffices to connect the blocks to each other. We have that $\mathrm{pre}_{l-1} \lt \mathrm{suf}_l = p_r$, so we can connect $p_r$ to $\mathrm{pre}_{l-1}$. By induction, we see that all blocks are now connected, since each block is connected to some previous block. 321 322 **Code (C++)** 323 324 ``` 325 #include <bits/stdc++.h> 326 using namespace std; 327 328 void solve(){ 329 int n; 330 cin >> n; 331 vector<int> p(n+1), pre(n+1, n); 332 vector<pair<int, int>> suf(n+2); 333 for(int i=1; i<=n; i++){ 334 cin >> p[i]; 335 pre[i] = min(pre[i-1], p[i]); 336 } 337 for(int i=n; i>=1; i--) 338 suf[i] = max(suf[i+1], {p[i], i}); 339 for(int i=2; i<=n; i++) 340 if(pre[i-1] > suf[i].first){ 341 cout << "No" << '\n'; 342 return; 343 } 344 cout << "Yes" << '\n'; 345 for(int l=1; l<=n;){ 346 int r = suf[l].second; 347 for(int i=l; i<r; i++) 348 cout << p[i] << ' ' << p[r] << '\n'; 349 if(l > 1) 350 cout << pre[l-1] << ' ' << p[r] << '\n'; 351 l = r+1; 352 } 353 } 354 355 int main(){ 356 ios::sync_with_stdio(false); 357 cin.tie(NULL); 358 int t; 359 cin >> t; 360 while(t--) solve(); 361 } 362 ``` 363 364 **Bonus** 365 366 Can you count the number of satisfactory trees? I don't have a solution to this version; leave a comment if you find one. 367 368 **Rate the problem!** 369 370 **Quality** 371 372 * Excellent problem 373 * Good problem 374 * Average problem 375 * Bad problem 376 * Horrible problem 377 378 **Difficulty** 379 380 * Trivial problem 381 * Easy problem 382 * Average problem 383 * Hard problem 384 * Impossible problem 385 386 #### [E — Anisphia Wynn Palettia and Good Permutations](https://codeforces.com/contest/2171/problem/E) 387 388 **Solution** 389 390 **Step 1** 391 392 Let $x$'s denote elements which all share a common divisor, and let $-$'s denote any elements. Then an array of the form $[-, x, x, -, x, x, \dots]$ will have no bad indices. Let's call an array of this form "perfect". 393 394 **Step 2** 395 396 Suppose the $x$'s are even elements. We have roughly $\frac{n}{2}$ even elements, which means we can form a perfect array of length roughly $\frac{3n}{4}$. Now, we have roughly $\frac{n}{6}$ elements which are odd multiples of $3$, which means we can form a disjoint perfect array of length roughly $\frac{n}{4}$. By concatenating these two arrays, we achieve a roughly full permutation with $O(1)$ bad indices. See the next section for a proof of the bound on bad indices. 397 398 **Bound on bad indices** 399 400 Instead of counting bad indices, we will count good indices. We form a perfect array of length $3\lfloor \frac{n}{4} \rfloor$, where all indices are good except for potentially the last one. We also form a perfect array of length $3\lfloor \frac{n+3}{12} \rfloor$ because we gain a new triple for every pair of $\{3, 9\} \pmod{12}$. Again, all indices are good except for potentially the last one. Therefore, we achieve $3\lfloor \frac{n}{4}\rfloor + 3\lfloor \frac{n+3}{12} \rfloor - 2$ good indices. It can be verified for every residue class $\bmod 12$ that this is lower bounded by $n-6$. Since there are $n-2$ indices in total, we have at most $4$ bad indices. 401 402 **Code (C++)** 403 404 ``` 405 #include <bits/stdc++.h> 406 using namespace std; 407 408 void solve(){ 409 int n; 410 cin >> n; 411 vector<vector<int>> a(3); 412 for(int i=1; i<=n; i++) 413 if(!(i % 2)) 414 a[0].push_back(i); 415 else if(!(i % 3)) 416 a[1].push_back(i); 417 else 418 a[2].push_back(i); 419 while(a[2].size() >= 1 && a[0].size() >= 2){ 420 cout << a[2].back() << ' '; 421 a[2].pop_back(); 422 cout << a[0].back() << ' '; 423 a[0].pop_back(); 424 cout << a[0].back() << ' '; 425 a[0].pop_back(); 426 } 427 while(a[2].size() >= 1 && a[1].size() >= 2){ 428 cout << a[2].back() << ' '; 429 a[2].pop_back(); 430 cout << a[1].back() << ' '; 431 a[1].pop_back(); 432 cout << a[1].back() << ' '; 433 a[1].pop_back(); 434 } 435 for(int i : a[0]) 436 cout << i << ' '; 437 for(int i : a[1]) 438 cout << i << ' '; 439 for(int i : a[2]) 440 cout << i << ' '; 441 cout << '\n'; 442 } 443 444 int main(){ 445 ios::sync_with_stdio(false); 446 cin.tie(NULL); 447 int t; 448 cin >> t; 449 while(t--) solve(); 450 } 451 ``` 452 453 **Bonus** 454 455 Let $f(n)$ denote the minimum number of bad indices across all permutations of length $n$. Can you find the value of $\max f(n)$? I suspect the answer is $2$, but I don't have a formal proof. Furthermore, can you find $f(n)$ for all $n$? 456 457 Update: I've heard from several people that $\max f(n) = 1$. Feel free to post a comment with a proof, if you'd like. 458 459 Update: 460 461 **Solution** 462 463 A construction commented by [d1amondzz](/profile/d1amondzz "Specialist d1amondzz") seems to prove an upper bound of $f(3), f(5) \leq 1$ and $f(n) = 0$ for $n\neq 3, 5$. I think several other comments may have alluded to a similar solution as well. The general idea is that for the largest prefix of primes $p_1, ..., p_k$ satisfying $p_{k-1}\cdot p_k \leq n$, we can construct an array $q$ as follows: for each $p_i$, first append $p_i$ to $q$, then append all elements with smallest prime factor $p_i$, ending with $p_i\cdot p_{i+1}$. Then all adjacent elements are not coprime, so as long as this array is of size at least roughly $\frac{2}{3}n$, we can intersperse it with the remaining elements to achieve no bad indices. All composites are included in $q$, because if a composite number has smallest prime factor at least $p_{k+1}$, then its value is at least $(p_{k+1})^2 \gt p_k\cdot p_{k+1} \gt n$ by construction of $k$. So we have that $q$ is of length asympototically at least $n-\frac{n}{\log n}$, which is asymptotically at least $cn$ for any $c \lt 1$. We can furthermore verify that this construction works for all small $n$ except for $3$ and $5$. 464 465 As for the lower bound, it's easy to see that $f(3) \geq 1$ since all pairs are coprime, and that $f(5) \geq 1$ since the only pair that is not coprime is $\{2, 4\}$, but we cannot have that these elements appear in all triples. Therefore, we have that $f(3) = f(5) = 1$ and $f(n) = 0$ for $n\neq 3, 5$. 466 467 **Rate the problem!** 468 469 **Quality** 470 471 * Excellent problem 472 * Good problem 473 * Average problem 474 * Bad problem 475 * Horrible problem 476 477 **Difficulty** 478 479 * Trivial problem 480 * Easy problem 481 * Average problem 482 * Hard problem 483 * Impossible problem 484 485 #### [G — Sakura Adachi and Optimal Sequences](https://codeforces.com/contest/2171/problem/G) 486 487 **Solution** 488 489 **Step 1** 490 491 Let's fix the number of double operations we use; call this integer $k$. Now, we can treat each value independently. 492 493 **Step 2** 494 495 Consider a specific pair $a_i, b_i$. If we don't apply any addition operations, we have that $a_i$ becomes $a_i \cdot 2^k$. Clearly we need that $a_i \cdot 2^k \leq b_i$. Now, observe that applying an addition operation before applying $j$ of the $k$ double operations is equivalent to adding $2^j$ to our final sum. We need to add $b_i - a_i \cdot 2^k$, so in total, we apply $\lfloor \frac{b_i - a_i \cdot 2^k}{2^k} \rfloor = \lfloor \frac{b_i}{2^k} \rfloor - a_i$ addition operations at the beginning, each adding $2^k$ to our sum. Then, we apply $\texttt{popcount}((b_i - a_i \cdot 2^k)\pmod{2^k}) = \texttt{popcount}(b_i\pmod{2^k})$ addition operations later, where $\texttt{popcount}(x)$ denotes the number of set bits in $x$. This is because, if the $j$-th bit of $b_i - a_i \cdot 2^k$ is set for some $j \lt k$, we would like to apply an operation before applying $j$ of the double operations so we can add $2^j$ to our sum. 496 497 **Step 3** 498 499 We would like to choose the largest number of double operations possible, since a double operation increases all values by at least one. Furthermore, since $n\geq 2$, a double operation is strictly more effective than an addition operation. However, we still need to satisfy $a_i \cdot 2^k \leq b_i$ for all $i$. Therefore, we will choose $k=\min \log_2{\frac{b_i}{a_i}}$. 500 501 **Step 4** 502 503 Between each double operation, the addition operations can be rearranged. Let's consider all of the addition operations applied before applying exactly $j$ double operations; denote these values $c_1, \dots, c_n$, where $c_i$ is the number of addition operations performed on element $a_i$. Then we can multiply our number of sequences by ${\sum c_i \choose c_1, \dots, c_n}$, the multinomial coefficient of $c_i$. This is equal to $\frac{(\sum c_i)!}{\prod (c_i!)}$. To simplify implementation, note that for $j \lt k$, all $c_i$ are either $0$ or $1$, so the denominator is only nontrivial for $j=k$. The final answer is the product of these values across all $0\leq j\leq k$. See the next section for intuition on multinomial coefficients and some of the details on its implementation. 504 505 **Multinomial coefficients** 506 507 The intuition behind the formula for multinomial coefficients is as follows: let's say $n=3$, and we want to find the number of ways to color $\sum c_i$ balls such that $c_1$ are red, $c_2$ are green, and $c_3$ are blue. Let's call our positions "red $1$" $\dots$ "red $c_1$" $\dots$ "blue $c_3$". Now, it's clear that there are $(\sum c_i)!$ ways to assign each ball to a position, because we have $\sum c_i$ choices of balls to assign to "red $1$", then $\sum c_i - 1$ remaining choices of balls to assign to "red $2$", and so forth, until we only have one choice of balls to assign to "blue $c_3$". However, this overcounts, because there is no difference between assigning ball $1$ to "red $1$" and ball $2$ to "red $2$", and vice versa. We are overcounting the red assignments by a factor of $c_1!$, because every valid selection of red balls achieves $c_1!$ assignments of red balls to positions. Similar reasoning holds for the green and blue balls, so in total, we have $\frac{(\sum c_i)!}{\prod (c_i!)}$ different sequences. 508 509 Multinomial coefficients can be computed by precomputing factorials. For the numerator, note that if $\sum c_i \geq 10^6+3$ then $(\sum c_i)! \equiv 0\pmod{10^6+3}$ because we have a factor of $10^6+3$, so we only need to precompute factorials up to $10^6+2$. For the denominator, we can divide by $c_i!$ by multiplying by the modular inverse of $c_i!$ modulo $10^6+3$. Crucially, note that $c_i \lt 10^6+3$ because the number of addition operations you can apply is at most $b_i - a_i \lt 10^6$, so modular inverses are well-defined. 510 511 **Code (C++)** 512 513 ``` 514 #include <bits/stdc++.h> 515 #define int long long 516 using namespace std; 517 518 int mod = 1e6+3; 519 520 vector<int> fact(mod); 521 522 int inv(int a){ 523 return a <= 1 ? a : mod - mod / a * inv(mod % a) % mod; 524 } 525 526 void solve(){ 527 int n, x, ans = 1; 528 cin >> n; 529 vector<int> a(n), b(n); 530 for(int i=0; i<n; i++) 531 cin >> a[i]; 532 for(int i=0; i<n; i++) 533 cin >> b[i]; 534 int k = __lg(b[0] / a[0]); 535 for(int i=1; i<n; i++) 536 k = min(k, __lg(b[i] / a[i])); 537 x = k; 538 vector<int> cnt(k), c(n); 539 for(int i=0; i<n; i++){ 540 for(int j=0; j<k; j++){ 541 cnt[j] += b[i] & 1; 542 b[i] >>= 1; 543 } 544 c[i] = b[i] - a[i]; 545 } 546 for(int j=0; j<k; j++){ 547 x += cnt[j]; 548 ans = ans * fact[cnt[j]] % mod; 549 } 550 int last = accumulate(c.begin(), c.end(), 0LL); 551 ans = (last < mod ? ans * fact[last] % mod : 0); 552 for(int i : c){ 553 x += i; 554 ans = ans * inv(fact[i]) % mod; 555 } 556 cout << x << ' ' << ans << '\n'; 557 } 558 559 signed main(){ 560 ios::sync_with_stdio(false); 561 cin.tie(NULL); 562 fact[0] = 1; 563 for(int i=1; i<mod; i++) fact[i] = fact[i-1] * i % mod; 564 int t; 565 cin >> t; 566 while(t--) solve(); 567 } 568 ``` 569 570 **Rate the problem!** 571 572 **Quality** 573 574 * Excellent problem 575 * Good problem 576 * Average problem 577 * Bad problem 578 * Horrible problem 579 580 **Difficulty** 581 582 * Trivial problem 583 * Easy problem 584 * Average problem 585 * Hard problem 586 * Impossible problem 587 588 #### [H — Shiori Miyagi and Maximum Array Score](https://codeforces.com/contest/2171/problem/H) 589 590 **Solution** 591 592 **Step 1** 593 594 Let's first try to solve this problem with inefficient time and memory, then we will later optimize it. For $1\leq i\leq n$ and $0\leq j\leq m-n$, let $\mathrm{dp}[i][j]$ denote the largest score achievable from the first $i$ indices, while also satisfying $a_i = i+j$. Now, since $a$ must be strictly increasing, we equivalently have that $a_i - i$ is monotonically increasing. Therefore, we can transition as follows: $\mathrm{dp}[i][j] = \max_{k\leq j} \mathrm{dp}[i-1][k] + v(i, i+j)$, because we may choose $a_{i-1}$ to be any value satisfying $a_{i-1} - (i-1) \leq j$, then we choose $a_i = i+j$, adding a score of $v(i, i+j)$. 595 596 **Step 2** 597 598 Now, we will try to remove the first dimension; that is, $\mathrm{dp}[j]$ denotes the largest score achievable while also satisfying $a_i = i+j$, where we will update this array as we iterate through all $i$. We will store this in a data structure that supports quickly querying prefix maximums and increasing point values; in particular, either a Fenwick tree or a segment tree will work. 599 600 Suppose we are at some stage $i$ and would like to update $\mathrm{dp}[j]$. As before, we want to update it to $\max_{k\leq j} \mathrm{dp}[k] + v(i, i+j)$. We should process $j$ in reverse order, as we want to ensure that we are accessing $\mathrm{dp}[i-1][k]$ instead of $\mathrm{dp}[i][k]$. 601 602 However, we only have to update $\mathrm{dp}[j]$ if $v(i, i+j)$ is nonzero. This is because, if $v(i, i+j)$ is zero, then we are updating $\mathrm{dp}[j]$ to $\max_{k\leq j} \mathrm{dp}[k]$. However, since we are only querying prefix maximums, any query involving $j$ will implicitly query all $k\leq j$ anyways, so it is not necessary to explicitly update $\mathrm{dp}[j]$. Our final answer is $\max \mathrm{dp}[j]$. See the next section for runtime analysis. 603 604 **Runtime analysis** 605 606 For simplicity of analysis, assume $m - n \geq c$ for some reasonable $c$, to avoid pathological cases where $\log (m-n)$ is undefined or zero. 607 608 For each $i$, we are updating $O(\frac{m-n}{i})$ values. Therefore, in total, we have $O(\sum \frac{m-n}{i}) = O((m-n)H(n))$ updates. Since harmonic numbers are known to grow logarithmically, this is $O((m-n)\log n)$. Each update takes $O(\log (m-n))$ time, as it involves a query and an update on a Fenwick tree or segment tree of size $m-n+1$. So the updates in total take $O((m-n)\log n\log{(m-n)})$ time. 609 610 However, we also need to compute $v(i, i+j)$ for each update. This will take $O(\sum v(i, i+j))$ time. For a fixed $i$, we have that $O(\frac{m-n}{i})$ values satisfy $v(i, i+j) \geq 1$, $O(\frac{m-n}{i^2})$ values satisfy $v(i, i+j) \geq 2$, and so forth. Therefore, for a fixed $i$, we have that $\sum v(i, i+j) = O(\sum \frac{m-n}{i^k}) = O(\frac{m-n}{i}\sum \frac{1}{i^{k-1}}) = O(\frac{m-n}{i} \cdot \frac{1}{1-\frac{1}{i}}) = O(\frac{m-n}{i} \cdot \frac{i}{i-1}) = O((m-n) \cdot \frac{1}{i-1})$. Across all $i\geq 2$, we have $O((m-n)H(n-1)) = O((m-n)\log n)$. This is dominated by the $O((m-n)\log n\log{(m-n)})$ term from the updates. 611 612 Finally, we have an additional $n$ term, as we have to iterate through all $i\leq n$. Our total runtime is $O((m-n)\log n\log{(m-n)} + n)$. 613 614 **Code (C++)** 615 616 ``` 617 #include <bits/stdc++.h> 618 using namespace std; 619 620 void solve(){ 621 int n, m; 622 cin >> n >> m; 623 vector<int> mx(m-n+1); 624 function<int(int)> query = [&](int i)->int{ 625 int ret = 0; 626 for(; i>=0; i=(i&i+1)-1) 627 ret = max(ret, mx[i]); 628 return ret; 629 }; 630 function<void(int, int)> update = [&](int i, int val){ 631 for(; i<=m-n; i|=i+1) 632 mx[i] = max(mx[i], val); 633 }; 634 function<int(int, int)> v = [](int b, int x)->int{ 635 int ans = 0; 636 while(!(x % b)){ 637 ans++; 638 x /= b; 639 } 640 return ans; 641 }; 642 for(int i=2; i<=n; i++) 643 for(int j=(m-n+i)/i*i; j>=i; j-=i) 644 update(j-i, query(j-i) + v(i, j)); 645 cout << query(m-n) << '\n'; 646 } 647 648 int main(){ 649 ios::sync_with_stdio(false); 650 cin.tie(NULL); 651 int t; 652 cin >> t; 653 while(t--) solve(); 654 } 655 ``` 656 657 **Rate the problem!** 658 659 **Quality** 660 661 * Excellent problem 662 * Good problem 663 * Average problem 664 * Bad problem 665 * Horrible problem 666 667 **Difficulty** 668 669 * Trivial problem 670 * Easy problem 671 * Average problem 672 * Hard problem 673 * Impossible problem