2109.md (32495B)
1 Source: https://codeforces.com/blog/entry/142960 2 3 Thank you for your participation! We hope you enjoyed the problems! We would love to hear your feedback! Please share your thoughts in the comments. 4 5 **How did you find the contest?** 6 7 * Great: 8 * Good: 9 * Average: 10 * Bad: 11 * Trash: 12 13 **Which problem was your favorite?** 14 15 * A: 16 * B: 17 * C1: 18 * C2: 19 * C3: 20 * D: 21 * E: 22 * F: 23 24 **Which problem did you find the least enjoyable?** 25 26 * A: 27 * B: 28 * C1: 29 * C2: 30 * C3: 31 * D: 32 * E: 33 * F: 34 35 [2109A - Время дуэли](/contest/2109/problem/A "Codeforces Round 1025 (Div. 2)") 36 37 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"). 38 39 **Hints** 40 41 **Hint 1** 42 43 What can you say when every player has reported a win? 44 45 **Solution** 46 47 A report array can be genuine only if it meets both of these conditions: 48 49 * There must be at least one player who reported $0$ — there are $n - 1$ duels and $n$ players. 50 * There cannot be two adjacent players who both reported $0$ — one of them must have won the duel between them. 51 52 If either condition fails, the answer is `YES` (there is definitely a liar); otherwise, the answer is `NO`. 53 54 **Code** 55 56 ``` 57 #include<bits/stdc++.h> 58 59 using namespace std; 60 61 void solve() { 62 int n; 63 cin >> n; 64 vector<int> a(n); 65 for (int i = 0; i < n; i++) { 66 cin >> a[i]; 67 } 68 69 if (accumulate(a.begin(), a.end(), 0) == n) { 70 cout << "YES" << "\n"; 71 return; 72 } 73 74 for (int i = 0; i < n - 1; i++) if (!a[i] && !a[i + 1]) { 75 cout << "YES" << "\n"; 76 return; 77 } 78 79 cout << "NO" << "\n"; 80 } 81 82 int main() { 83 ios::sync_with_stdio(0), cin.tie(0); 84 int t = 1; 85 cin >> t; 86 while (t--) { 87 solve(); 88 } 89 } 90 ``` 91 92 **Rate the Problem** 93 94 * Amazing problem: 95 * Good problem: 96 * Average problem: 97 * Bad problem: 98 * Didn't solve: 99 100 [2109B - Режь, чтобы выжить](/contest/2109/problem/B "Codeforces Round 1025 (Div. 2)") 101 102 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") and [FetFot](/profile/FetFot "Мастер FetFot"). 103 104 **Hints** 105 106 **Hint 1** 107 108 What changes if the turn order is reversed — starting with Fouad's move before Mouf's cut? 109 110 **Hint 2** 111 112 Can the row and column dimensions be treated independently, or do they interact? How might that influence your approach? 113 114 **Solution** 115 116 We restructure the game by grouping each move (Fouad's move) with the following cut (Mouf's cut). After Mouf performs his initial cut, each combined turn consists of Fouad first moving to any remaining cell, followed by Mouf cutting the grid. 117 118 Now, let's temporarily set aside the initial cut and focus on the state of the grid just before Fouad's first move in this new structure. Suppose the remaining Grid has dimensions $n' \times m'$. Since each cut affects only one dimension, we can handle the row and column reductions independently. Thus, the number of required turns is: 119 120 $ f(n') + f(m') $ 121 122 where $f(l)$ denotes the number of turns required to reduce a $1 \times l$ grid to a single cell. The function $f(l)$ can be defined recursively as: 123 124 $ f(l) = \begin{cases} 0 & l = 1, \\ 1 + \max\limits_{1 \le i \le l} \min(f(i), f(l - i + 1)) & l \gt 1. \end{cases} $ 125 126 Given that $f$ is non-decreasing, the minimum between $f(i)$ and $f(l − i + 1)$ is maximized when $i = \left\lfloor \frac{l}{2} \right\rfloor$. Thus, we simplify the recurrence as: 127 128 $ f(l) = 1 + f\left(\left\lceil \frac{l}{2} \right\rceil \right) $ 129 130 Now returning to the initial cut, note that it is in Mouf's best interest to minimize $n'$ and $m'$ since $f$ is non-decreasing. To do so, he should ensure Fouad ends up on the boundary of the remaining grid after the first cut. This yields four possible configurations: 131 132 $ (n', m') \in S = \{ (a, m),\ (n - a + 1, m),\ (n, b),\ (n, m - b + 1) \} $ 133 134 The total number of turns, including the initial cut, is: 135 136 $ \text{ans} = 1 + \min\limits_{(n', m') \in S} \left[ f(n') + f(m') \right] $ 137 138 The overall time complexity is: $O(\log(n) + \log(m))$. 139 140 **Code** 141 142 ``` 143 #include<bits/stdc++.h> 144 145 using namespace std; 146 147 void solve() { 148 int n, m, a, b; 149 cin >> n >> m >> a >> b; 150 151 vector<pair<int, int>> rec({ 152 make_pair(a, m), make_pair(n - a + 1, m), 153 make_pair(n, b), make_pair(n, m - b + 1)}); 154 155 int ans = n + m; 156 for (auto [n1, m1] : rec) { 157 int res = 0; 158 while (n1 > 1) { 159 ++res; 160 n1 = (n1 + 1) / 2; 161 } 162 while (m1 > 1) { 163 ++res; 164 m1 = (m1 + 1) / 2; 165 } 166 ans = min(ans, res); 167 } 168 169 cout << 1 + ans << "\n"; 170 } 171 172 int main() { 173 ios::sync_with_stdio(0), cin.tie(0); 174 int t = 1; 175 cin >> t; 176 while (t--) { 177 solve(); 178 } 179 } 180 ``` 181 182 **Rate the Problem** 183 184 * Amazing problem: 185 * Good problem: 186 * Average problem: 187 * Bad problem: 188 * Didn't solve: 189 190 [2109C1 - Взлом чисел (простая версия)](/contest/2109/problem/C1 "Codeforces Round 1025 (Div. 2)") 191 192 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") and [FetFot](/profile/FetFot "Мастер FetFot"). 193 194 **Hints** 195 196 **Hint 1** 197 198 Figure out a way to make $x$ equal $1$, then the final command will be $\texttt{"add n-1"}$. 199 200 **Hint 2** 201 202 What range of values can $x$ take after the first application of the $\texttt{"digit"}$ command? 203 204 **Hint 3** 205 206 What about the second application of the $\texttt{"digit"}$ command? 207 208 **Hint 4** 209 210 Avoid overusing the $\texttt{"digit"}$ command — after the second application, $x$ is limited to the range $[1, 16]$. Consider using the binary representation of $x$ instead. 211 212 **Solution** 213 214 * Apply $\texttt{"digit"}$ $\rightarrow$ $x \in [1, 81]$. 215 * Apply $\texttt{"digit"}$ $\rightarrow$ $x \in [1, 16]$. 216 * Apply $\texttt{"add -8"}$ $\rightarrow$ $x \in [1, 8]$. 217 * Apply $\texttt{"add -4"}$ $\rightarrow$ $x \in [1, 4]$. 218 * Apply $\texttt{"add -2"}$ $\rightarrow$ $x \in [1, 2]$. 219 * Apply $\texttt{"add -1"}$ $\rightarrow$ $x$ becomes exactly $1$. 220 * Finally, apply $\texttt{"add n-1"}$. 221 222 **Code** 223 224 ``` 225 #include<bits/stdc++.h> 226 227 using namespace std; 228 229 void solve() { 230 int n; 231 cin >> n; 232 233 cout << "digit" << endl; 234 int x; 235 cin >> x; 236 237 cout << "digit" << endl; 238 cin >> x; 239 240 for (int i = 8; i >= 1; i /= 2) { 241 cout << "add " << -i << endl; 242 cin >> x; 243 } 244 245 cout << "add " << n - 1 << endl; 246 cin >> x; 247 248 cout << "!" << endl; 249 cin >> x; 250 assert(x == 1); 251 } 252 253 int main() { 254 ios::sync_with_stdio(0), cin.tie(0); 255 int t = 1; 256 cin >> t; 257 while (t--) { 258 solve(); 259 } 260 } 261 ``` 262 263 **Rate the Problem** 264 265 * Amazing problem: 266 * Good problem: 267 * Average problem: 268 * Bad problem: 269 * Didn't solve: 270 271 [2109C2 - Взлом чисел (средняя версия)](/contest/2109/problem/C2 "Codeforces Round 1025 (Div. 2)") 272 273 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") and [FetFot](/profile/FetFot "Мастер FetFot"). 274 275 **Hints** 276 277 **Hint 1** 278 279 The first command is not $\texttt{"digit"}$. 280 281 **Hint 2** 282 283 The first command is $\texttt{"mul"}$. 284 285 **Hint 3** 286 287 Combining the $\texttt{"mul"}$ and $\texttt{"digit"}$ commands is powerful! Consider a number that links these two commands. 288 289 **Hint 4** 290 291 Recall that well-known fact from high school: a number is divisible by $9$ if and only if the sum of its digits is divisible by $9$. 292 293 **Solution** 294 295 * Apply $\texttt{"mul 9"}$. 296 * Apply $\texttt{"digit"}$ $\rightarrow$ $x \in [9, 18, 27, 36, 45, 54, 63, 72, 81]$. 297 * Apply $\texttt{"digit"}$ $\rightarrow$ $x$ becomes exactly $9$. 298 * Finally, apply $\texttt{"add n-9"}$. 299 300 **Code** 301 302 ``` 303 #include<bits/stdc++.h> 304 305 using namespace std; 306 307 void solve() { 308 int n; 309 cin >> n; 310 311 cout << "mul " << 9 << endl; 312 int x; 313 cin >> x; 314 315 cout << "digit" << endl; 316 cin >> x; 317 318 cout << "digit" << endl; 319 cin >> x; 320 321 cout << "add " << n - 9 << endl; 322 cin >> x; 323 324 cout << "!" << endl; 325 cin >> x; 326 assert(x == 1); 327 } 328 329 int main() { 330 ios::sync_with_stdio(0), cin.tie(0); 331 int t = 1; 332 cin >> t; 333 while (t--) { 334 solve(); 335 } 336 } 337 ``` 338 339 **Rate the Problem** 340 341 * Amazing problem: 342 * Good problem: 343 * Average problem: 344 * Bad problem: 345 * Didn't solve: 346 347 [2109C3 - Взлом чисел (сложная версия)](/contest/2109/problem/C3 "Codeforces Round 1025 (Div. 2)") 348 349 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") and [FetFot](/profile/FetFot "Мастер FetFot"). 350 351 **Hints** 352 353 **Hint 1** 354 355 While $9$ connects the $\texttt{"mul"}$ and $\texttt{"digit"}$ commands, there may be other numbers that do so as well. 356 357 **Hint 2** 358 359 Another valid solution for the medium version is as follows: 360 361 * $\texttt{"digit"}$. 362 * $\texttt{"mul 99"}$. 363 * $\texttt{"digit"}$. 364 * $\texttt{"add n-18"}$. 365 366 But what's the reasoning behind this sequence? 367 368 **Hint 3** 369 370 $S[(10^d - 1)x] = 9d \quad \forall x \in [1,10^d]$. 371 372 **Solution** 373 374 Let's prove that 375 376 $S[(10^d - 1)x] = 9d \quad \forall x \in [1, 10^d].$ 377 378 Observe that 379 380 $x \cdot (10^d-1) = x \cdot 10^d - x = (x - 1) \cdot 10^d + 10^d - x = (x - 1) \cdot 10^d + [(10^d - 1) - (x - 1)].$ 381 382 The first term represents $(x - 1)$ shifted $d$ places to the left (i.e. multiplies by $10^d$). The second term is the $d$-digit string of nines minus $(x - 1)$, namely 383 384 $\underbrace{999 \ldots 999}_{d \text{ times}} - (x - 1).$ 385 386 Therefore, for every $i$ ($1 \le i \le d$), the $i$-th digit of the second term and the $(i + d)$-th digit of the first term complement each other to sum to $9$. 387 388 Drumroll, please! The number we're about to use is $999\,999\,999$. With just three commands, we can turn any $x$ into $n$: 389 390 * Apply $\texttt{"mul } 999\,999\,999 \texttt{"}$. 391 * Apply $\texttt{"digit"}$ $\rightarrow$ $x$ becomes exactly $81$. 392 * Finally, apply $\texttt{"add n-81"}$. 393 394 There's one special case: if $n = 81$, you only need the first two commands — meaning $f(81) = 2$. 395 396 Now let’s see why no other $n$ can get away with just two commands. First, note that the digit‑sum function $S(i)$ always changes when you add $1$, so $S(i) \neq S(i + 1)$. 397 398 Consider your choice of first command: 399 400 * $\texttt{"add y"}$: When $y$ is positive, it shifts the entire range of possible $x$-values. Otherwise, it shrinks the range but never cuts it down below half its size. In either case, it can’t force $x$ into a single value. 401 * $\texttt{"div y"}$: It fails even on small $x$-values (e.g. $1 \le x \le 4$) — it doesn’t force a single outcome. 402 * $\texttt{"digit"}$: After the first application, it only restricts $x$ to $[1, 81]$, and a second application only narrows it to $[1, 16]$. You still don’t get a single fixed value. 403 404 That leaves only one candidate to start with, which is $\texttt{"mul y"}$. Suppose some other multiplier $y \neq 999\,999\,999$ made $S(x \cdot y)$ constant. Test it against $x = 1$ and $x = 999\,999\,999$: 405 406 $ S(1 \cdot y) \le 80 \lt 81 = S(999\,999\,999\cdot y) $ 407 408 They can’t both be the same, so no such $y \neq 999\,999\,999$ exists. 409 410 Similar to the above reasoning, keeping in mind that $S(i) \neq S(i + 1)$, the only possible second command is $\texttt{"digit"}$ (as this is the only way to shrink the range, since no other command can do so). Hence, only $n = 81$ can reach a fixed result in two commands; every other $n$ requires three. 411 412 **Code** 413 414 ``` 415 #include<bits/stdc++.h> 416 417 using namespace std; 418 419 void solve() { 420 int n; 421 cin >> n; 422 423 cout << "mul 999999999" << endl; 424 int x; 425 cin >> x; 426 427 cout << "digit" << endl; 428 cin >> x; 429 430 if (n != 81) { 431 cout << "add " << n - 81 << endl; 432 cin >> x; 433 } 434 435 cout << "!" << endl; 436 cin >> x; 437 assert(x == 1); 438 } 439 440 int main() { 441 ios::sync_with_stdio(0), cin.tie(0); 442 int t = 1; 443 cin >> t; 444 while (t--) { 445 solve(); 446 } 447 } 448 ``` 449 450 **Rate the Problem** 451 452 * Amazing problem: 453 * Good problem: 454 * Average problem: 455 * Bad problem: 456 * Didn't solve: 457 458 **Fun facts** 459 460 We hid the command limits in C3 so people wouldn’t just guess wildly. We used C1 to bridge the gap between B and C2. This problem was originally a D, but testers found what was then D1 (now C1) way easier than C (which got moved to D). The neat trick for C3 happened by chance — [Kaitokid](/profile/Kaitokid "Гроссмейстер Kaitokid") used $\texttt{"mul 99"}$ instead of the intended $\texttt{"mul 9"}$ in C2, and that's where [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS")'s guessing skills kicked in and saw it could be extended to $999\,999\,999$! After we worked through a formal proof, we decided it was too good not to include in the final problem set. 461 462 [2109D - D/D/D](/contest/2109/problem/D "Codeforces Round 1025 (Div. 2)") 463 464 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") and [FetFot](/profile/FetFot "Мастер FetFot"). 465 466 **Hints** 467 468 **Hint 1** 469 470 Suppose you've reached vertex $i$, what is the shortest possible sequence of moves that brings you back to $i$? 471 472 **Hint 2** 473 474 At any vertex $j$ adjacent to $i$, you may take back-and-forth move $[i \to j \to i].$ 475 476 **Solution** 477 478 Let us temporarily set aside the multiset $A$. Starting from vertex $1$, define 479 480 $ {} $ $\mathrm{dist}[i][p] = \min \{ \, \text{length of a walk from } 1 \text{ to } i \mid \text{length} \bmod 2 = p \, \}, \text{ for parity } p \in \{0, 1\}.$ 481 482 Since any walk of length $d$ can be extended to $d + 2$ by inserting a back-and-forth move $[i \to j \to i]$ at any vertex $j$ adjacent to $i$, only the minimal even and odd distances matter. By performing a breadth-first search from vertex $1$, we derive $\mathrm{dist}$. 483 484 Now reintroduce the multiset $A$ with total sum $S = \sum A$. We would like to select a sub-multiset whose sum $S'$ satisfies both 485 486 * $S' \ge \mathrm{dist}[i][p];$ 487 * $S' \bmod 2 = p.$ 488 489 Taking all elements gives $S' = S$. Let $p = S \bmod 2$, then any vertex with $\mathrm{dist}[i][p] \le S$ is reachable by a walk of parity $p$. Otherwise, we must find a suitable $S' \bmod 2 = 1 - p$ satisfying $\mathrm{dist}[i][1 - p] \le S'$, and the minimal way to flip parity is to remove the smallest odd element $\min_{\mathrm{odd}}$ from the multiset $A$. Parity change is impossible if no such odd element exists, since removing any even element leaves the parity unchanged. Setting $S' = S - a_{\mathrm{odd}}$, any vertex with $\mathrm{dist}[i][1 - p] \le S'$ is reachable by a walk of parity $1 - p$. 490 491 In conclusion, vertex $i$ is attainable by a walk using the original multiset $A$ if and only if either 492 493 * $\mathrm{dist}[i][p] \le S \text{ when } p = S \bmod 2 \text{, or}$ 494 * $\mathrm{dist}[i][p] \le S - \min_{\mathrm{odd}} \text{ when } p \neq S \bmod 2 \text{ and the smallest odd element } \min_{\mathrm{odd}} \in A \text{ exists.} $ 495 496 The overall time complexity is: $O(n + m + \ell)$. 497 498 **Code** 499 500 ``` 501 #include<bits/stdc++.h> 502 503 using namespace std; 504 505 void solve() { 506 int n, m, l; 507 cin >> n >> m >> l; 508 509 int const inf = 2e9 + 1; 510 int sum = 0, min_odd = inf; 511 vector<int> a(l); 512 for (int i = 0; i < l; ++i) { 513 cin >> a[i]; 514 sum += a[i]; 515 if (a[i] % 2) { 516 min_odd = min(min_odd, a[i]); 517 } 518 } 519 520 vector adj(n, vector<int>()); 521 for (int i = 0; i < m; ++i) { 522 int u, v; 523 cin >> u >> v; 524 --u; 525 --v; 526 adj[u].push_back(v); 527 adj[v].push_back(u); 528 } 529 530 vector<array<int, 2>> dist(n, {inf, inf}); 531 queue<pair<int, int>> q; 532 q.push({0, 0}); 533 dist[0][0] = 0; 534 while (q.size()) { 535 auto [u, p] = q.front(); 536 q.pop(); 537 for (auto v : adj[u]) { 538 if (dist[v][!p] > dist[u][p] + 1) { 539 dist[v][!p] = dist[u][p] + 1; 540 q.push({v, !p}); 541 } 542 } 543 } 544 545 for (int i = 0; i < n; ++i) { 546 bool found = 0; 547 for (int p = 0; p < 2; ++p) { 548 int s = sum - (p == sum % 2 ? 0 : min_odd); 549 if (dist[i][p] <= s) { 550 found = 1; 551 } 552 } 553 cout << found; 554 } 555 cout << "\n"; 556 } 557 558 int main() { 559 ios::sync_with_stdio(0), cin.tie(0); 560 int t = 1; 561 cin >> t; 562 while (t--) { 563 solve(); 564 } 565 } 566 ``` 567 568 **Rate the Problem** 569 570 * Amazing problem: 571 * Good problem: 572 * Average problem: 573 * Bad problem: 574 * Didn't solve: 575 576 [2109E - Ура, бинарная строка!](/contest/2109/problem/E "Codeforces Round 1025 (Div. 2)") 577 578 Idea by [Intellegent](/profile/Intellegent "Мастер Intellegent"), prepared by [Intellegent](/profile/Intellegent "Мастер Intellegent"). 579 580 **Hints** 581 582 **Hint 1** 583 584 The state of $s_i$ depend entirely on how many operations have been performed on the suffix $s_i, s_{i+1}, \ldots, s_n$. 585 586 **Hint 2** 587 588 Let $dp[i][j]$ denote the number of ways to perform exactly $j$ moves on the suffix $s_i, s_{i+1}, \ldots, s_n$. 589 590 **Solution** 591 592 Some useful insight is to see that if you operate on an element, then every element after it will be unaffected; similarly, the state of an element in the string depends only on the number of operations used on the suffix after it. More specifically, an element's state flips with each operation applied to a suffix that includes it, so its value depends entirely on the number of operations done to its suffix. 593 594 This inspires the following $dp$ state: 595 596 $ {} $ $ dp[i][j] = \text{the number of ways to make exactly } j \text{ moves on the suffix only } s_i,...,s_n. $ 597 598 Now, regarding transitions — the number of ways to move from state $dp[i][j]$ to $dp[i - 1][j + k]$ (in other words the number of ways to add $k$ operations at the $(i - 1)$-th index) can be thought of in terms of forming strings composed of characters $A$ and $B$, where $A$ represents making a move on $s_{i - 1}$ and $B$ represents making a move on $s_i,...,s_n$. Each valid string with $j$ $B$s and $k$ $A$s represents a unique sequence of moves, so the total number of transitions corresponds to the number of such valid strings. Notice that a string will be valid if and only if every $A$ occurs when $s_{i - 1}$ is $0$, because $s_{i - 1}$ flips every operation, meaning that every $A$ should occur on either only even indices or only odd indices depending on the initial value of $s_{i - 1}$. 599 600 This means that the transition will be either $\displaystyle\binom{\left\lfloor \frac{j + k}{2} \right\rfloor}{k}$ or $\displaystyle\binom{\left\lceil \frac{j + k}{2} \right\rceil}{k}$. 601 602 Finally, the answer can be found in $dp[1][k]$. 603 604 The overall time complexity is: $O(n \cdot k^2)$. 605 606 **Code** 607 608 ``` 609 #include<bits/stdc++.h> 610 using namespace std; 611 typedef long long ll; 612 #define debug(x) cout << #x << " = " << x << "\n"; 613 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 614 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 615 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 616 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 617 618 const int MOD = 998244353; 619 620 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 621 struct modnum { 622 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 623 624 using S = conditional_t<is_big_mod, ll, int>; 625 using L = conditional_t<is_big_mod, __int128, ll>; 626 627 S x; 628 629 modnum() : x(0) {} 630 modnum(ll _x) { 631 _x %= static_cast<ll>(mod); 632 if (_x < 0) { _x += mod; } 633 x = _x; 634 } 635 636 modnum pow(ll n) const { 637 modnum res = 1; 638 modnum cur = *this; 639 while (n > 0) { 640 if (n & 1) res *= cur; 641 cur *= cur; 642 n /= 2; 643 } 644 return res; 645 } 646 modnum inv() const { return (*this).pow(mod-2); } 647 648 modnum& operator+=(const modnum& a){ 649 x += a.x; 650 if (x >= mod) x -= mod; 651 return *this; 652 } 653 modnum& operator-=(const modnum& a){ 654 if (x < a.x) x += mod; 655 x -= a.x; 656 return *this; 657 } 658 modnum& operator*=(const modnum& a){ 659 x = static_cast<L>(x) * a.x % mod; 660 return *this; 661 } 662 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 663 664 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 665 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 666 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 667 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 668 669 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 670 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 671 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 672 673 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 674 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 675 }; 676 677 using mint = modnum<MOD>; 678 679 struct Combi{ 680 vector<mint> _fac, _ifac; 681 int n; 682 683 Combi() { 684 n = 1; 685 _fac.assign(n + 1, 1); 686 _ifac.assign(n + 1, 1); 687 } 688 689 void check_size(int m){ 690 int need = n; 691 while (need < m) need *= 2; 692 m = need; 693 if (m <= n) return; 694 695 _fac.resize(m + 1); 696 _ifac.resize(m + 1); 697 for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1]; 698 699 _ifac[m] = _fac[m].inv(); 700 for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1); 701 n = m; 702 } 703 704 mint fac(int m){ 705 check_size(m); 706 return _fac[m]; 707 } 708 709 mint ifac(int m){ 710 check_size(m); 711 return _ifac[m]; 712 } 713 714 mint ncr(int n, int r){ 715 if (n < r || r < 0) return 0; 716 717 return fac(n) * ifac(n - r) * ifac(r); 718 } 719 720 mint npr(int n, int r){ 721 if (n < r || r < 0) return 0; 722 723 return fac(n) * ifac(n - r); 724 } 725 } comb; 726 727 void solve(){ 728 int n, k; 729 cin >> n >> k; 730 731 string s; 732 cin >> s; 733 734 vector<vector<mint>> dp(n, vector<mint>(k + 1)); 735 dp[n - 1][0] = 1; 736 if (s[n - 1] == '0') 737 dp[n - 1][1] = 1; 738 739 for (int i = n - 2; i >= 0; i--){ 740 for (int j = 0; j <= k; j++){ 741 for (int c = 0; j + c <= k; c++){ 742 int spaces = (j + c + (s[i] == '0')) / 2; 743 dp[i][j + c] += dp[i + 1][j] * comb.ncr(spaces, c); 744 } 745 } 746 } 747 748 cout << dp[0][k] << "\n"; 749 } 750 751 int main(){ 752 ios::sync_with_stdio(false); 753 cin.tie(0); 754 cout.tie(0); 755 756 int t; 757 cin >> t; 758 while (t--) solve(); 759 } 760 ``` 761 762 **Rate the Problem** 763 764 * Amazing problem: 765 * Good problem: 766 * Average problem: 767 * Bad problem: 768 * Didn't solve: 769 770 [2109F - Шаги пингвина](/contest/2109/problem/F "Codeforces Round 1025 (Div. 2)") 771 772 Idea by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"), prepared by [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS"). 773 774 **Hints** 775 776 **Hint 1** 777 778 Suppose you need $\mathrm{dis}_F \ge x$. To achieve this, construct a "cage" — a contiguous path of cells all with values at least $x$ — that separates Fouad from the exit, while ensuring that $\mathrm{dis}_M$ remains unchanged. 779 780 **Hint 2** 781 782 Try to find a path for Mouf that impacts the building of the "cage" as little as possible. 783 784 **Solution** 785 786 First, find $\mathrm{dis}_M$ using Dijkstra's algorithm or DSU. 787 788 Define $can(x)$ to be true if you can make $\mathrm{dis}_F$ greater than or equal to $x$, and false otherwise. It's clear that if $can(x)$ is true, then $can(x−1)$ is also true, which leads us to perform a binary search on the value of $x$. 789 790 Suppose we choose a set $S$ of black cells with values strictly less than $x$ and decide to apply operations on them; the optimal strategy is to make the values of all chosen cells equal to $x$. 791 792 Now, suppose we don't care about $\mathrm{dis}_M$. How can we find the maximum possible $\mathrm{dis}_F$? 793 794 We need to create a cage that separates Fouad from the exit. The cage consists of the borders of the grid, in addition to cells with values greater than or equal to $x$ (after applying operations), forming a connected chain such that every two consecutive cells in the chain **share an edge or corner**. 795 796 By using multi-source Dijkstra's algorithm, start from one border and try to reach another, where the weight of each cell represents how many operations are needed to raise its value to at least $x$. If it cannot be reached (e.g., if the cell is white and its value is less than $x$), then set the weight to infinity. 797 798 We have six cases to build the cage, as described in the picture below: 799 800  801 802 Now we have two cases to consider: 803 804 * $x \le \mathrm{dis}_M$: In this scenario, $\mathrm{dis}_M$ will remain unchanged regardless of the set $S$ we choose. 805 806 * $x \gt \mathrm{dis}_M$: Here, we must ensure that at least one path for Mouf has a cost equal to $\mathrm{dis}_M$, while ensuring that no cell in this path is included in $S$. 807 808 But which path should we retain? 809 810 Suppose Mouf takes a path $P$. This action divides the grid into two parts: 811 812 * Every cell reachable from $(n,1)$ without passing through any cell in $P$. This portion belongs to Fouad (if $(n, 1)$ is already in $P$, then there are no cells that belong to Fouad's part). 813 * The remaining cells belong to Mouf. 814 815 As we observe, the more cells allocated to Fouad's part, the greater the options we have for constructing a cage. Therefore, we define a super path as a path that leaves the maximum number of cells available for Fouad's part. But how many super paths exist? 816 817 In fact, there is only one super path; the proof can be found below. 818 819 **Proof** 820 821 Suppose we have two super paths that intersect at certain cells (including the first and last cells). In this case, we have two scenarios to consider: 822 823 * They only intersect at the first and last cells. In this situation, one of the paths cannot be a super path, leading to a contradiction. 824 * They intersect at other cells: If this is the case, then neither of the paths can be considered a super path. We can take the optimal segments from each path to construct a superior path, which also leads to a contradiction. 825 826 For further clarification, please refer to the illustration below. 827 828  829 830 Now, how do we identify that super path? 831 832 We begin by performing a multi-source BFS, initializing the queue with the cells in the first row and the first $r$ cells of the last column (as they always belong to Mouf's part). When visiting a cell, we mark it. If its value is less than or equal to $\mathrm{dis}_M$, we pop it from the queue and continue; otherwise, we spread to the eight neighboring cells. 833 834 Through this process, we will have certainly marked the super path (and potentially some additional cells from Mouf's part). If $x \gt \mathrm{dis}_M$, it becomes impossible to utilize any marked cell to construct the cage — therefore, we set the weight for these cells to infinity. While you might consider the marked cells that are not part of the super path, this is inconsequential since any cage utilizing these cells will invariably pass through the super path. 835 836 The overall time complexity of this approach is: $O(n^2 \cdot \log(A_{MAX} + k) \cdot \log(n))$. 837 838 **Code** 839 840 ``` 841 #include<bits/stdc++.h> 842 843 using namespace std; 844 845 using i64 = long long; 846 847 constexpr int inf = 1e9; 848 array<int, 8> dx{0, 0, 1, -1, 1, 1, -1, -1}; 849 array<int, 8> dy{1, -1, 0, 0, -1, 1, -1, 1}; 850 851 void solve() { 852 int n, r, k; 853 cin >> n >> r >> k; 854 --r; 855 856 vector a(n, vector<int>(n)); 857 for (int i = 0; i < n; ++i) { 858 for (int j = 0; j < n; ++j) { 859 cin >> a[i][j]; 860 } 861 } 862 863 vector b(n, vector<int>(n)); 864 for (int i = 0; i < n; ++i) { 865 string s; 866 cin >> s; 867 for (int j = 0; j < n; ++j) { 868 b[i][j] = s[j] - '0'; 869 } 870 } 871 872 auto in = [&](int i, int j) { 873 return (0 <= i && i < n && 0 <= j && j < n); 874 }; 875 876 priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq; 877 pq.push({a[0][0], 0, 0}); 878 vector dis(n, vector<int>(n, inf)); 879 dis[0][0] = a[0][0]; 880 while (pq.size()) { 881 auto [mx, i, j] = pq.top(); 882 pq.pop(); 883 if (dis[i][j] != mx) { 884 continue; 885 } 886 for (int dir = 0; dir < 4; ++dir) { 887 int ni = i + dx[dir]; 888 int nj = j + dy[dir]; 889 if (in(ni, nj) && dis[ni][nj] > max(mx, a[ni][nj])) { 890 int nmx = max(mx, a[ni][nj]); 891 dis[ni][nj] = nmx; 892 pq.push({nmx, ni, nj}); 893 } 894 } 895 } 896 int mouf = dis[r][n - 1]; 897 898 vector dont(n, vector<int>(n)); 899 auto run = [&](auto &&run, int i, int j) -> void { 900 for (int dir = 0; dir < 8; ++dir) { 901 int ni = i + dx[dir]; 902 int nj = j + dy[dir]; 903 if (in(ni, nj) && dont[ni][nj] == 0) { 904 dont[ni][nj] = 1; 905 if (a[ni][nj] > mouf) { 906 run(run, ni, nj); 907 } 908 } 909 } 910 }; 911 912 for (int j = 0; j < n; ++j) { 913 dont[0][j] = 1; 914 if (a[0][j] > mouf) { 915 run(run, 0, j); 916 } 917 } 918 for (int i = 0; i <= r; ++i) { 919 dont[i][n - 1] = 1; 920 if (a[i][n - 1] > mouf) { 921 run(run, i, n - 1); 922 } 923 } 924 925 int L = 1, R = 2e6; 926 while (L <= R) { 927 int mid = (L + R) / 2; 928 for (int j = 0; j < n; ++j) { 929 if ((mid > mouf && dont[n - 1][j]) || (mid > a[n - 1][j] && b[n - 1][j] == 0)) { 930 continue; 931 } 932 pq.push({max(0, mid - a[n - 1][j]), n - 1, j}); 933 } 934 for (int i = r; i < n; ++i) { 935 if ((mid > mouf && dont[i][n - 1]) || (mid > a[i][n - 1] && b[i][n - 1] == 0)) { 936 continue; 937 } 938 pq.push({max(0, mid - a[i][n - 1]), i, n - 1}); 939 } 940 fill(dis.begin(), dis.end(), vector<int>(n, inf)); 941 while (pq.size()) { 942 auto [cost, i, j] = pq.top(); 943 pq.pop(); 944 dis[i][j] = min(dis[i][j], cost); 945 if (dis[i][j] != cost) { 946 continue; 947 } 948 for (int dir = 0; dir < 8; ++dir) { 949 int ni = i + dx[dir]; 950 int nj = j + dy[dir]; 951 if (in(ni, nj)) { 952 if ((mid > mouf && dont[ni][nj]) || (mid > a[ni][nj] && b[ni][nj] == 0)) { 953 continue; 954 } 955 if (dis[ni][nj] > cost + max(0, mid - a[ni][nj])) { 956 int ncost = cost + max(0, mid - a[ni][nj]); 957 dis[ni][nj] = ncost; 958 pq.push({ncost, ni, nj}); 959 } 960 } 961 } 962 } 963 int minCost = inf; 964 if (mid <= mouf) { 965 for (int j = 0; j < n; ++j) { 966 minCost = min(minCost, dis[0][j]); 967 } 968 for (int i = 0; i <= r; ++i) { 969 minCost = min(minCost, dis[i][n - 1]); 970 } 971 } 972 for (int i = 1; i < n; ++i) { 973 minCost = min(minCost, dis[i][0]); 974 } 975 if (minCost <= k) { 976 L = mid + 1; 977 } else { 978 R = mid - 1; 979 } 980 } 981 982 cout << mouf << " " << R << "\n"; 983 } 984 985 int main() { 986 ios::sync_with_stdio(0), cin.tie(0); 987 int t = 1; 988 cin >> t; 989 while (t--) { 990 solve(); 991 } 992 } 993 ``` 994 995 **Rate the Problem** 996 997 * Amazing problem: 998 * Good problem: 999 * Average problem: 1000 * Bad problem: 1001 * Didn't solve: 1002 1003 **The Making of F** 1004 1005 When [MOUFLESS](/profile/MOUFLESS "Кандидат в мастера MOUFLESS") came up with F, the intended solution was based on flows — then, thanks to the efforts of [ApraCadabra](/profile/ApraCadabra "Мастер ApraCadabra"), [Kaitokid](/profile/Kaitokid "Гроссмейстер Kaitokid"), and [Wael_Zaiback](/profile/Wael_Zaiback "Мастер Wael_Zaiback"), they helped us refine the problem until we got here.