codeforces-scrape

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

2247.md (27012B)


      1 Source: https://codeforces.com/blog/entry/155337
      2 
      3 Thank you for participating in the round!
      4 
      5 [2247A - Zero Sum](/contest/2247/problem/A "Codeforces Round 1111 (Div. 2)")
      6 
      7 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro")
      8 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro")
      9 
     10 **Hints**
     11 
     12 **Hint 1**
     13 
     14 Try to find an invariant
     15 
     16 **Hint 2**
     17 
     18 Consider the sum of all elements in the array
     19 
     20 **Solution**
     21 
     22 It's easy to see that $\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4$ does not change after a single operation. Therefore, if $\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4 \neq 0$, then the answer is "NO".
     23 
     24 Otherwise, let's make $a_1 = 1, a_2 = -1, a_3 = 1, \dots, a_{n - 1} = (-1)^n$. We can always do that by performing operations with indices $1, 2, 3, \dots n - 1$ in this order, and after operation number $i$ we set the $i$-th element to the value we want. After that, $| \sum\limits_{i = 1}^n a_i | \leq 2$, so it is equal to zero because it's the only number divisible by $4$ in that range.
     25 
     26 **Code**
     27 
     28 ```
     29 #include <iostream>
     30 
     31 using namespace std;
     32 
     33 void solve() {
     34     int n; cin >> n;
     35     int sm = 0;
     36     for (int i = 0; i < n; i++) {
     37         int x; cin >> x;
     38         sm += x;
     39     }
     40     
     41     cout << (abs(sm) % 4 == 0 ? "YES\n" : "NO\n");
     42 }
     43 
     44 int main() {
     45     int t;
     46     cin >> t;
     47     while (t--) {
     48         solve();
     49     }
     50     return 0;
     51 }
     52 ```
     53 
     54 **Rate The Problem!**
     55 
     56 * Good Problem
     57 * Okay Problem
     58 * Bad Problem
     59 * Didn't Solve
     60 
     61 [2247B - Yet Another Constructive](/contest/2247/problem/B "Codeforces Round 1111 (Div. 2)")
     62 
     63 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro")
     64 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro")
     65 
     66 **Hints**
     67 
     68 **Hint 1**
     69 
     70 When is the answer "NO"?
     71 
     72 **Hint 2**
     73 
     74 The answer is "NO" when $k \gt m$
     75 
     76 **Solution**
     77 
     78 If $m \lt k$, then the answer is $-1$ because it is well known that in any array with $m$ elements there is a subarray with sum divisible by $m$. Here is a proof: Consider remainders of prefix sums by $m$. There are $m + 1$ prefix sums, and only $m$ possible remainders by modulo $m$, therefore two of the prefix sums have the same remainder and in the segment between these two prefix sums the sum is divisible by $m$.
     79 
     80 Otherwise, the solution is to make $a_j = 1$ for all $j$ such that $j \mod k \neq 0$, and $a_j = m - k + 1$ for $j \mod k \equiv 0$. In this construction, every subarray of length $k$ has the sum of exactly $m$, and every subarray whose length is less than $k$ obviously has a sum that is greater than $0$ and less than $m$, therefore it can't be divisible by $m$.
     81 
     82 **Code**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 using namespace std;
     87 
     88 int main() {
     89     ios::sync_with_stdio(false);
     90     cin.tie(nullptr);
     91 
     92     int t;
     93     cin >> t;
     94     while (t--) {
     95         int n, k, m;
     96         cin >> n >> k >> m;
     97 
     98         if (k > m) {
     99             cout << "NO\n";
    100             continue;
    101         }
    102 
    103         cout << "YES\n";
    104         for (int i = 0; i < n; i++) {
    105             cout << (i % k == 0 ? m - k + 1 : 1) << ' ';
    106         }
    107         cout << '\n';
    108     }
    109     return 0;
    110 }
    111 ```
    112 
    113 **Rate The Problem!**
    114 
    115 * Good Problem
    116 * Okay Problem
    117 * Bad Problem
    118 * Didn't Solve
    119 
    120 [2247C - Inversion of a Subsequence](/contest/2247/problem/C "Codeforces Round 1111 (Div. 2)")
    121 
    122 * Idea: [PvPro](/profile/PvPro "International Grandmaster PvPro"), [makrav](/profile/makrav "Legendary Grandmaster makrav")
    123 * Solution: [PvPro](/profile/PvPro "International Grandmaster PvPro")
    124 
    125 **Hints**
    126 
    127 **Hint 1**
    128 
    129 The answer is either $-1$, or it is $\leq 2$
    130 
    131 **Solution**
    132 
    133 If $a = b$, the answer is $0$. If $a$ contains no $1$-s in it, the answer is $-1$ because we can't make any operation. Also, if $b$ doesn't have any $0$ values, then we can't get $b$ from any array in one operation, because all values on changed positions should be $0$ before the operation, but their sum would be even in this case.
    134 
    135 If neither of these conditions holds, the answer is always $1$ or $2$. It's easy to check whether the answer is $1$: just consider the positions where $a_j \neq b_j$, and check if we can do an operation with exactly this set of indices. Otherwise, the answer is $2$.
    136 
    137 Here is a proof: if in the set of indices where $a_j \neq b_j$ there are $\geq 2$ indices where $a_j = 1$, we can just split these wrong indices into two sets with odd sums of $a_j$. Otherwise, all values that should be changed in array $a$ are $0$. Also, there are indices $i$ and $k$ such that $a_i = b_i = 0$ and $a_k = b_k = 1$ just because the answer is not $-1$. So let's make the first operation with a subsequence which includes all wrong indices (where $a_j \neq b_j$) and indices $i$ and $k$. The operation is possible because the sum of all $a$ values is $1$. After this operation, we can make an operation with only two elements, $i$ and $k$. After these two operations, $a = b$.
    138 
    139 **Code**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 using namespace std;
    144 
    145 int main() {
    146     ios::sync_with_stdio(false);
    147     cin.tie(nullptr);
    148 
    149     int t;
    150     cin >> t;
    151     while (t--) {
    152         int n;
    153         cin >> n;
    154 
    155         vector<int> a(n), b(n);
    156         for (int &x : a) cin >> x;
    157         for (int &x : b) cin >> x;
    158 
    159         if (a == b) {
    160             cout << 0 << '\n';
    161             continue;
    162         }
    163 
    164         int sum = 0;
    165 
    166         for (int i = 0; i < n; ++i) {
    167             if (a[i] != b[i]) {
    168                 sum += a[i];
    169             }
    170         }
    171         
    172         if (accumulate(a.begin(), a.end(), 0) == 0 || accumulate(b.begin(), b.end(), 0) == n) {
    173             cout << -1 << "\n";
    174             continue;
    175         }
    176 
    177         if (sum % 2 == 1) {
    178             cout << 1 << '\n';
    179         } else {
    180             cout << 2 << '\n';
    181         }
    182     }
    183     
    184     return 0;
    185 }
    186 ```
    187 
    188 **Rate The Problem!**
    189 
    190 * Good Problem
    191 * Okay Problem
    192 * Bad Problem
    193 * Didn't Solve
    194 
    195 [2247D1 - XOR Sorting (Easy Version)](/contest/2247/problem/D1 "Codeforces Round 1111 (Div. 2)")
    196 
    197 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    198 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    199 
    200 **Hints**
    201 
    202 **Hint 1**
    203 
    204 Imagine you only need to swap elements on some positions $i$ and $j$. What is the minimum $k$ such that you can do it with all XORs of indices $\leq k$
    205 
    206 **Hint 2**
    207 
    208 The answer is always zero or a power of two.
    209 
    210 **Solution**
    211 
    212 It is inefficient to perform swaps whose index XOR is not a power of two.
    213 
    214 Suppose we want to swap $a_i$ and $a_j$ $(i \lt j)$, and $i \oplus j$ is not a power of two. Let $b$ be the highest differing bit in numbers $i$ and $j$. Then perform the following swaps in order: $(i, i + 2^b), (i + 2^b, j), (i, i + 2^b)$. It's easy to see that $i \oplus (i + 2^b) = 2^b$, however, $(i + 2^b) \oplus j$ might not be a power of two. In this case, we want to replace this swap recursively with the same procedure with a sequence of swaps, such that each of which has an XOR equal to a power of $2$. It's easy to see that after performing these swaps, the only change in the array is that elements on positions $i$ and $j$ are swapped.
    215 
    216 Now we want to solve the problem. How do we check whether we can sort the array using only operations with XOR at most $2^j$? Let's split the array into contiguous blocks of elements with size $2^{j + 1}$ (the size of the last block may be less than $2^{j+1}$). It's easy to see that each element will remain in its original block after any number of swaps with XOR $\leq 2^j$. And within a single block, we can obtain any permutation of its elements just because we can always do any swap inside the block with some sequence of swaps $\leq 2^j$. Therefore, we only need to check whether sorting every contiguous block of $2^{j + 1}$ elements, the array becomes sorted.
    217 
    218 We can simplify that by only considering two values, $min_j$ and $max_j$, which correspond to the maximum and minimum elements in block $j$. Then we want to check that $ \forall j \; | \; max_j \leq min_{j + 1}$ holds.
    219 
    220 For the simple version of this task, we can check it naively in $O(n \log n)$ because there are $O(log n)$ different possible answers, and each one of them can be checked in $O(n)$.
    221 
    222 **Code**
    223 
    224 ```
    225 #include <bits/stdc++.h>
    226 #include <cassert>
    227 
    228 using namespace std;
    229 using ll = long long;
    230 
    231 #define all(x) (x).begin(), (x).end()
    232 #define sz(x) (int)(x).size()
    233 #define pb push_back
    234 
    235 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    236 
    237 void solve() {
    238     int n, q; cin >> n >> q;
    239     vector<int> a(n);
    240     for (auto &u : a) cin >> u;
    241     if (is_sorted(all(a))) {
    242         cout << "0\n";
    243         return;
    244     }
    245     for (int x = 0;; x++) {
    246         int mx = -1;
    247         bool good = 1;
    248         for (int j = 0; j * (1 << (x+1)) < n; j++) {
    249             int cmx = -1;
    250             for (int i = 0; j * (1<<(x+1)) + i < n && i < (1<<(x+1)); i++) {
    251                 int cur = a[j *(1<<(x+1)) + i];
    252                 good &= (mx <= cur);
    253                 cmx = max(cmx, cur);
    254             }
    255             mx = max(mx, cmx);
    256         }
    257         if (good) {
    258             cout << (1<<x) << '\n';
    259             return;
    260         }
    261     }
    262 }
    263 
    264 signed main() {
    265     cin.tie(0)->sync_with_stdio(false);
    266     int tt = 1;
    267     cin >> tt;
    268 
    269     while (tt--) {
    270         solve();
    271     }
    272 
    273     return 0;
    274 }
    275 ```
    276 
    277 **Rate The Problem!**
    278 
    279 * Good Problem
    280 * Okay Problem
    281 * Bad Problem
    282 * Didn't Solve
    283 
    284 [2247D2 - XOR Sorting (Hard Version)](/contest/2247/problem/D2 "Codeforces Round 1111 (Div. 2)")
    285 
    286 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    287 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    288 
    289 **Hints**
    290 
    291 **Hint 1**
    292 
    293 There are a lot of powers of two mentioned in the solution. Which data structure is usually built on an array of a size of a power of two?
    294 
    295 **Hint 2**
    296 
    297 Use the segment tree.
    298 
    299 **Solution**
    300 
    301 First, read the solution for the problem D1.
    302 
    303 In the hard version, we need to also handle queries. Let us append several $\infty$ values to the end of the array so that its length becomes a power of two. Then let's build a segment tree over this array. Now each node of the segment tree corresponds to a block. In each vertex of segment tree we want to maintain the following three values: -maximum value on the segment -minimum value on the segment -minimum $k$ needed to sort the segment
    304 
    305 It is easy to compute the values of a node from the values of its children: maximum and minimum are trivial, and for $k$ we need to take maximum among our two children, and if $max_L \gt min_R$ we need to increase $k$ to length of the segment divided by two. ($max_L$ is the maximum in the left son, and $min_R$ is the minimum in the right son).
    306 
    307 This solution works in $O(n + q \log n)$ time.
    308 
    309 **Code**
    310 
    311 ```
    312 #include <bits/stdc++.h>
    313 #include <cassert>
    314 
    315 using namespace std;
    316 using ll = long long;
    317 
    318 #define all(x) (x).begin(), (x).end()
    319 #define sz(x) (int)(x).size()
    320 #define pb push_back
    321 
    322 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    323 
    324 void solve() {
    325     int n, q; cin >> n >> q;
    326     vector<int> a(n);
    327     for (auto &u : a) cin >> u;
    328     int N = 1;
    329     while (N < n) N *= 2;
    330     while (n < N) {
    331         a.pb(1e9);
    332         n++;
    333     }
    334     vector<array<int, 3>> t(2 * n);
    335     vector<int> L(2 * n, 1);
    336     for (int j = 0; j < n; j++) t[n + j] = {a[j], a[j], 0};
    337     auto pull= [&](int j, int len) {
    338         t[j][0] = min(t[j << 1][0], t[j << 1 | 1][0]);
    339         t[j][1] = max(t[j << 1][1], t[j << 1 | 1][1]);
    340         t[j][2] = max(t[j<<1][2], t[j<<1|1][2]);
    341         if (t[j<<1][1] > t[j<<1|1][0]) t[j][2] = max(t[j][2], len / 2);
    342     };
    343     for (int j = n - 1; j >= 1; j--) {
    344         L[j] = 2 * L[j << 1];
    345         pull(j, L[j]);
    346     }
    347     cout << t[1][2] << '\n';
    348     while (q--) {
    349         int p, x; cin >> p >> x;
    350         p += n;
    351         t[p] = {x, x, 0};
    352         p >>= 1;
    353         int len = 2;
    354         while (p) {
    355             pull(p, len);
    356             p >>= 1;
    357             len *= 2;
    358         }
    359         cout << t[1][2] << '\n';
    360     }
    361 }
    362 
    363 signed main() {
    364     cin.tie(0)->sync_with_stdio(false);
    365     int tt = 1;
    366     cin >> tt;
    367 
    368     while (tt--) {
    369         solve();
    370     }
    371 
    372     return 0;
    373 }
    374 ```
    375 
    376 **Rate The Problem!**
    377 
    378 * Good Problem
    379 * Okay Problem
    380 * Bad Problem
    381 * Didn't Solve
    382 
    383 [2247E - Build a Tree](/contest/2247/problem/E "Codeforces Round 1111 (Div. 2)")
    384 
    385 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    386 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    387 
    388 **Hints**
    389 
    390 **Hint 1**
    391 
    392 $k$ should be even in order to have an answer
    393 
    394 **Hint 2**
    395 
    396 Try to find lower and upper bounds for $k$ to have an answer. Every even $k$ in this range is achievable.
    397 
    398 **Hint 3**
    399 
    400 Consider a centroid.
    401 
    402 **Solution**
    403 
    404 Thanks to [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik") for sharing this solution! My initial approach was more complicated.
    405 
    406 Consider the centroid of the answer and set it as the root of the tree. Then the sum of distances $\leq 2 \cdot$ (sum of heights of all vertices). It is easy to see that, to maximize the sum of distances, we need to make two roughly equal subtrees with sizes close to $\lfloor \frac{n}{2} \rfloor$, so we now have an upper bound for our answer. The lower bound is obviously $2 \cdot (n - 1)$ because we need to traverse each edge at least twice, because we start at vertex 1 and finish there. From this observation, we can also notice that the answer is always even because, for each edge, we must cross from one side of the edge to the other an even number of times to always come back.
    407 
    408 Now our goal is to build the tree such that after rooting it with its centroid, $2 \cdot$ (sum of heights of vertices) equals the required $x$. Let's start from a tree where the centroid has $n - 1$ direct children. Then we reroot the children one by one until the sum of heights reaches the desired $\frac{x}{2}$. We will also maintain the condition that each subtree's size doesn not exceed the $\lfloor \frac{n}{2} \rfloor$ bound. It is always possible to build such a tree because we know that our answer lies in the range of all possible answers, and we can reroot each vertex not only to the highest vertex from a big subtree, but also to all of its parents, so we can make an increase in the sum of heights by 1, 2, and all numbers up to the current maximum height.
    409 
    410 When we have built our tree, we need to label its vertices to solve the problem. Basically, we need to label vertices in such a way that $\operatorname{dist}(i, (i \bmod n) + 1) = h_i + h_{(i \bmod n) + 1}$, where $h$ corresponds to the array of all vertices' heights. For this to hold, we need to distribute labels so that vertices $i$ and $(i \bmod n) + 1$ end up in different subtrees of the centroid (we will label the centroid as vertex 1 and forget about it because for the centroid the condition holds automatically).
    411 
    412 Now it's a standard problem to put each label into some subtree so that two consecutive labels end up in different subtrees. The approach is to assign labels one by one, and we always try to put the label into the subtree with the maximum number of remaining free spots, also considering the last label's subtree. It's easy to prove by induction that, with the constraint on the size of each subtree, this approach works.
    413 
    414 This can be implemented in $O(n \log n)$ time; however, there are many different possible solutions working in linear time. Also, this problem can be solved under the condition that the tree must be a chain, but I prefer the centroid-based solution.
    415 
    416 **Code**
    417 
    418 ```
    419 #include <bits/stdc++.h>
    420 #include <cassert>
    421 
    422 using namespace std;
    423 using ll = long long;
    424 
    425 #define all(x) (x).begin(), (x).end()
    426 #define sz(x) (int)(x).size()
    427 #define pb push_back
    428 
    429 void solve() {
    430     ll n, k; cin >> n >> k;
    431     ll top = 0;
    432     for (int x = 1; x <= n / 2; x++) {
    433         top += x;
    434         if (2 * x <= n - 1) top += x;
    435     }
    436     top *= 2;
    437     if (k % 2 == 1 || k < 2 * (n - 1) || k > top) {
    438         cout << "-1\n";
    439         return;
    440     } 
    441     if (n == 2) {
    442         cout << "1 2\n";
    443         return;
    444     }
    445     vector<int> cnt(2, (n - 1) / 2);
    446     if (n % 2 == 0) cnt[1]++;
    447     ll cur = top;
    448     cur /= 2;
    449     k /= 2;
    450     for (int i = 0; ; i++) {
    451         int id = i % 2;
    452         if (cnt[id] > 1 && cur - (cnt[id] - 1) >= k) {
    453             cur -= (cnt[id] - 1);
    454             cnt.pb(1);
    455             cnt[id]--;
    456         } else if (cnt[id] > 1 || cur == k) {
    457             vector<pair<int, int>> edges;
    458             int cr = 2;
    459             vector<int> startv(sz(cnt));
    460             for (int j = 0; j < sz(cnt); j++) {
    461                 startv[j] = cr;
    462                 if (j != id) {
    463                     int prv = 1;
    464                     for (int x = 0; x < cnt[j]; x++) {
    465                         edges.pb({prv, cr++});
    466                         prv = cr - 1;
    467                     }
    468                 } else {
    469                     int prv = 1, start = cr;
    470                     for (int x = 0; x < cnt[j] - 1; x++) {
    471                         edges.pb({prv, cr++});
    472                         prv = cr - 1;
    473                     }
    474                     int was = cnt[j];
    475                     int neww = was - (cur - k);
    476                     if (neww == 1) edges.pb({1, cr++});
    477                     else edges.pb({start + (neww - 2), cr++});
    478                 }
    479             }
    480             set<pair<int, int>> st;
    481             for (int j = 0; j < sz(cnt); j++) st.insert({cnt[j], j});
    482             vector<int> per(n + 1);
    483             per[1] = 1;
    484             int lst = -1;
    485             for (int x = 2; x <= n; x++) {
    486                 auto it = --st.end();
    487                 while ((*it).second == lst) it--;
    488                 auto [c,id] = *it;
    489                 st.erase(it);
    490                 per[startv[id]] = x;
    491                 startv[id]++;
    492                 lst = id;
    493                 assert(cnt[id] > 0);
    494                 cnt[id]--;
    495                 st.insert({cnt[id], id});
    496             }
    497             for (auto &[u, v] : edges) {
    498                 u = per[u]; v = per[v];
    499                 cout << u << ' ' << v << '\n';
    500             }
    501             break;
    502         }
    503     }
    504 }
    505 
    506 signed main() {
    507     int t = 1;
    508     cin >> t;
    509 
    510     while (t--) {
    511         solve();
    512     }
    513 
    514     return 0;
    515 }
    516 ```
    517 
    518 **Rate The Problem!**
    519 
    520 * Good Problem
    521 * Okay Problem
    522 * Bad Problem
    523 * Didn't Solve
    524 
    525 [2247F - Paths on a Grid](/contest/2247/problem/F "Codeforces Round 1111 (Div. 2)")
    526 
    527 * Idea: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    528 * Solution: [makrav](/profile/makrav "Legendary Grandmaster makrav")
    529 
    530 **Hints**
    531 
    532 **Hint 1**
    533 
    534 Suppose we have two cells in a set. What condition must these two cells satisfy for the set to remain \textit{good}?
    535 
    536 **Hint 2**
    537 
    538 These two cells should have the same set of paths going through them. How can we specify \textit{good} sets then?
    539 
    540 **Hint 3**
    541 
    542 Consider the rightmost path going from $(1, 1)$ to $(i, j)$ and the leftmost path going from $(1, 1)$ to $(i, j)$. Find an intersection of these two paths.
    543 
    544 **Solution**
    545 
    546 First, let us observe that if there is at least one cell in a $\textit{good}$ set of cells through which no path from cell $(1, 1)$ to cell $(n, m)$ passes, then the same is true for all other cells in the set as well. Otherwise, there would exist at least one path contradicting the definition of a $\textit{good}$ set. Therefore, we can immediately add $2^{\text{free}} - 1$ to the answer, where $free$ is the number of free cells through which none of the required paths pass.
    547 
    548 From now on, we consider only those free cells through which at least one required path passes. Suppose our set contains some free cell $(i, j)$ and another cell $(i_1, j_1)$. Notice that one of the following two conditions must hold: $(i_1 \leq i, j_1 \leq j)$ or $(i_1 \geq i, j_1 \geq j)$. This is because at least one required path passes through each of these cells, and if neither condition holds, then such paths cannot coincide, since a path may only move either one cell down or one cell to the right;
    549 
    550 In the first case, $(i_1 \leq i, j_1 \leq j)$, we need the following condition: every path from $(1, 1)$ to $(i, j)$ must pass through cell $(i_1, j_1)$; otherwise, the set is not $\textit{good}$. Similarly, if the second condition $(i_1 \geq i, j_1 \geq j)$ holds, then every path from cell $(i, j)$ to $(n, m)$ must pass through cell $(i_1, j_1)$.
    551 
    552 Therefore, we construct directed edges from cell $(i, j)$ to all cells $(i_1, j_1)$ such that $(i_1 \leq i, j_1 \leq j)$ and every path from $(1, 1)$ to $(i, j)$ passes through $(i_1, j_1)$, and also to all cells satisfying $(i_1 \geq i, j_1 \geq j)$ such that every path from $(i, j)$ to $(n, m)$ passes through $(i_1, j_1)$. Then we find the strongly connected components of this graph. A set of cells is good if and only if all of its cells belong to the same SCC.
    553 
    554 Essentially, such edges mean that every path from $(1, 1)$ to $(n, m)$ passing through $(i, j)$ also passes through $(i_1, j_1)$. This makes it clear that if all cells of the set belong to one SCC, then the set is good; otherwise, it is not.
    555 
    556 Now let us understand how to efficiently find SCCs in this graph. Consider only the edges from cells $(i, j)$ to cells $(i_1, j_1)$ satisfying $(i_1 \leq i, j_1 \leq j)$. Notice that if there exists an edge $(i, j) \rightarrow (i_1, j_1)$ and an edge $(i_1, j_1) \rightarrow (i_2, j_2)$, then there also exists an edge $(i, j) \rightarrow (i_2, j_2)$, because the edge $(i, j) \rightarrow (i_1, j_1)$ means that all paths from $(1, 1)$ to cell $(i, j)$ pass through cell $(i_1, j_1)$.
    557 
    558 We can also observe that all cells reachable by such edges from $(i, j)$ form a path in the directed graph. Therefore, for each cell $(i, j)$ it is sufficient to find the edge to the cell $(i_1, j_1)$ with the maximum value of $i_1 + j_1$.
    559 
    560 We process cells in increasing order of $i + j$. If cell $(i - 1, j)$ is reachable from $(1, 1)$ and cell $(i, j - 1)$ is not reachable from $(1, 1)$, then the required edge goes to cell $(i - 1, j)$. Similarly, if cell $(i - 1, j)$ is not reachable from $(1, 1)$ and cell $(i, j - 1)$ is reachable from $(1, 1)$, then the required edge goes to cell $(i, j - 1)$.
    561 
    562 Otherwise, the required edge goes to the LCA of cells $(i - 1, j)$ and $(i, j - 1)$ in the tree formed by the previously constructed SCC edges.
    563 
    564 Analogously, we can construct edges $(i, j) \rightarrow (i_1, j_1)$ to cells satisfying $i_1 \geq i$ and $j_1 \geq j$.
    565 
    566 Thus, our graph contains only $O(nm)$ edges, and we can easily find its SCCs.
    567 
    568 To answer LCA queries in the tree, we use binary lifting. Therefore, the overall complexity of the solution is $O(nm \log nm)$ time and $O(nm \log nm)$ memory.
    569 
    570 In fact, building SCCs is not even necessary. We can merge two cells $A$ and $B$ in dsu if $A$ is the direct parent of $B$ in a tree built from the cell $(1, 1)$ and if $B$ is the direct parent of $A$ in a tree built from the cell $(n, m)$.
    571 
    572 **Code**
    573 
    574 ```
    575 #include <bits/stdc++.h>
    576 #include <cassert>
    577 
    578 using namespace std;
    579 using ll = long long;
    580 
    581 #define all(x) (x).begin(), (x).end()
    582 #define sz(x) (int)(x).size()
    583 #define pb push_back
    584 
    585 const int maxl = 20, maxn = 1e6 + 10;
    586 int up[maxl][maxn];
    587 
    588 constexpr ll mod = 998244353;
    589 ll sum(ll x, ll y) {
    590     return (x + y >= mod ? x + y - mod : x + y);
    591 }
    592 ll mul(ll x, ll y) {
    593     return (x * y) % mod;
    594 }
    595 ll diff(ll x, ll y) {
    596     return (x >= y ? x - y : x + mod - y);
    597 }
    598 
    599 void solve() {
    600     int n, m; cin >> n >> m;
    601     vector<string> s(n);
    602     for (auto &u : s) cin >> u;
    603 
    604     vector<vector<int>> is_path(n, vector<int>(m));
    605     vector<int> h(n * m);
    606     vector<vector<int>> g_scc(n * m);
    607     for (int j = 0; j < maxl; j++) up[j][0] = 0;
    608     auto newv = [&](int v, int p) {
    609         g_scc[v].pb(p);
    610         h[v] = h[p] + 1;
    611         up[0][v] = p;
    612         for (int j = 1; j < maxl; j++) up[j][v] = up[j - 1][up[j - 1][v]];  
    613     };
    614     auto jump = [&](int v, int where) {
    615         for (int j = maxl - 1; j >= 0; j--) {
    616             if (((h[v] - where) >> j) & 1) v = up[j][v];
    617         }    
    618         return v;
    619     };
    620     auto lca = [&](int u, int v){
    621         if (h[u] > h[v]) swap(u, v);
    622         v = jump(v, h[u]);
    623         if (u == v) return u;
    624         for (int j = maxl - 1; j >= 0; j--) {
    625             if (up[j][v] != up[j][u]) {
    626                 v = up[j][v]; u = up[j][u];
    627             }
    628         }
    629         return up[0][v];
    630     };  
    631 
    632     is_path[0][0] = (s[0][0] == '1');
    633     for (int i = 0; i < n; i++) {
    634         for (int j = 0; j < m; j++) {
    635             if (i == 0 && j == 0) continue;
    636             if (s[i][j] == '0') continue;
    637             is_path[i][j] = (i > 0 && is_path[i - 1][j]) || (j > 0 && is_path[i][j - 1]);
    638             if (is_path[i][j]) {
    639                 int par;
    640                 if (i == 0 || !is_path[i - 1][j]) par = i * m + j - 1;
    641                 else if (j == 0 || !is_path[i][j - 1]) par = (i - 1) * m + j;
    642                 else par = lca((i - 1) * m + j, i * m + j - 1);
    643                 newv(i * m + j, par);
    644             }
    645         }
    646     }
    647 
    648     h.assign(n * m, 0);
    649     for (int j =0; j < maxl; j++) up[j][n * m - 1] = n * m - 1;
    650     vector<vector<int>> is_path2(n, vector<int>(m));
    651     is_path2[n - 1][m - 1] = (s[n - 1][m - 1] == '1');
    652     for (int i = n - 1; i >= 0; i--) {
    653         for (int j = m - 1; j >= 0; j--) {
    654             if (i == n - 1 && j == m - 1) continue;
    655             if (s[i][j] == '0') continue;
    656             is_path2[i][j] = (i + 1 < n && is_path2[i + 1][j]) || (j + 1 < m && is_path2[i][j + 1]);
    657             if (is_path2[i][j]) {
    658                 int par;
    659                 if (i + 1 == n || !is_path2[i + 1][j]) par = i * m + j + 1;
    660                 else if (j + 1 == m || !is_path2[i][j + 1]) par = (i + 1) * m + j;
    661                 else par = lca((i + 1) * m + j, i * m + j + 1);
    662                 newv(i * m + j, par);
    663             }
    664         }
    665     }
    666     int cntbad = 0;
    667     for (int i = 0; i < n; i++) {
    668         for (int j = 0; j < m; j++) cntbad += (!is_path[i][j] || !is_path2[i][j]);
    669     }
    670     ll ans = 1;
    671     for (int j = 0; j < cntbad; j++) ans = mul(ans, 2);
    672     ans = diff(ans, 1);
    673     // cout << cntbad << endl;
    674 
    675     vector<int> used(n * m), ord;
    676     auto dfs = [&](int v, auto&&self) -> void {
    677         used[v] = 1;
    678         for (int u : g_scc[v]) if (!used[u]) self(u, self);
    679         ord.pb(v);
    680     };  
    681     for (int j =0; j < n * m; j++) {
    682         if (!used[j] && is_path[j/m][j % m] && is_path2[j/m][j % m]) dfs(j, dfs);
    683     }
    684     reverse(all(ord));
    685     vector<bool> is_good(n * m);
    686     for (int el : ord) is_good[el] = 1;
    687     
    688     vector<vector<int>> grev(n * m);
    689     for (int i = 0; i < n * m; i++) for (int u : g_scc[i]) grev[u].pb(i);
    690     vector<int> cnt;
    691     used.assign(n * m, 0);
    692     auto dfs2 = [&](int v, auto&&self) -> void {
    693         cnt.back()++;
    694         used[v] = 1;
    695         for (int u : grev[v]) {
    696             if (!used[u] && is_good[u]) self(u, self);
    697         }
    698     };      
    699     for (int u : ord) {
    700         if (!used[u]) {
    701             cnt.pb(0);
    702             dfs2(u, dfs2);
    703         }
    704     }
    705     for (int c : cnt) {
    706         ll cur = 1;
    707         for (int j = 0; j < c; j++) cur = mul(cur, 2);
    708         ans = sum(ans, diff(cur, 1));
    709     }
    710     cout << ans << '\n';
    711 }
    712 
    713 signed main() {
    714     int t = 1;
    715     cin >> t;
    716 
    717     while (t--) {
    718         solve();
    719     }
    720 
    721     return 0;
    722 }
    723 ```
    724 
    725 **Rate The Problem!**
    726 
    727 * Good Problem
    728 * Okay Problem
    729 * Bad Problem
    730 * Didn't Solve