codeforces-scrape

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

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 ![](/predownloaded/c7/70/c770191a5e71dfdaff35489b5990a88c74bf0fd7.png)
    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 ![](/predownloaded/c5/fa/c5fa9268dc556bfc0e48522933c9ba2cf42fd372.png)
    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.