codeforces-scrape

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

2188.md (37540B)


      1 Source: https://codeforces.com/blog/entry/150649
      2 
      3 We hope you enjoyed the problems!
      4 
      5 **Rate the contest!**
      6 
      7 **Quality**
      8 
      9 * Excellent contest
     10 * Good contest
     11 * Average contest
     12 * Bad contest
     13 * Horrible contest
     14 
     15 **Difficulty**
     16 
     17 * Trivial contest
     18 * Easy contest
     19 * Average contest
     20 * Hard contest
     21 * Impossible contest
     22 
     23 [2188A - Divisible Permutation](/contest/2188/problem/A "Codeforces Round 1077 (Div. 2)")
     24 
     25 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__"), [Tobo](/profile/Tobo "Grandmaster Tobo")
     26 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
     27 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
     28 
     29 **Solution**
     30 
     31 For $|p_{n-1}-p_n|$ to be divisible by $n-1$, either $p_{n-1}=1$ and $p_n=n$, or $p_{n-1}=n$ and $p_n=1$. Either way, we can construct $p$ backwards. For $i$ from $n-2$ to $1$, there will only by one possible choice for $p_i$, where $p_i$ is either $p_{i+1}-i$ or $p_{i+1}+i$, depending on the parity of $i$.
     32 
     33 **Code (Python)**
     34 
     35 ```
     36 for _ in range(int(input())):
     37     n = int(input())
     38     p = [1, n]
     39     used = {1, n}
     40     for i in range(n - 2, 0, -1):
     41         prev = p[-1]
     42         if 1 <= prev - i <= n and prev - i not in used:
     43             p.append(prev - i)
     44             used.add(prev - i)
     45         else:
     46             p.append(prev + i)
     47             used.add(prev + i)
     48     p.reverse()
     49     print(*p)
     50 ```
     51 
     52 **Rate the problem!**
     53 
     54 **Quality**
     55 
     56 * Excellent problem
     57 * Good problem
     58 * Average problem
     59 * Bad problem
     60 * Horrible problem
     61 
     62 **Difficulty**
     63 
     64 * Trivial problem
     65 * Easy problem
     66 * Average problem
     67 * Hard problem
     68 * Impossible problem
     69 
     70 [2188B - Seats](/contest/2188/problem/B "Codeforces Round 1077 (Div. 2)")
     71 
     72 * Idea: [-firefly-](/profile/-firefly- "Master -firefly-")
     73 * Solution: [-firefly-](/profile/-firefly- "Master -firefly-")
     74 * Editorial: [-firefly-](/profile/-firefly- "Master -firefly-")
     75 
     76 **Solution**
     77 
     78 We can divide the string into segments that contain only zeros. For one segment that is bounded by two ones, the answer is $\lfloor \frac{len}{3} \rfloor$.
     79 
     80 **Proof**
     81 
     82 Each new student added to the segment can cover a maximum of $3$ empty seats (the seat they occupy plus one on each side).
     83 
     84 For every $3$ zeros, we must place exactly $1$ student to satisfy the condition while keeping the total count minimal.
     85 
     86 After placing these $\lfloor \frac{len}{3} \rfloor$ students, we can let the remaining zeros placed at the boundaries so that they're covered by the neighbor $1$s.
     87 
     88 If a segment of zeros is adjacent to the start or the end of the row, we need to introduce extra zeros. This is because in the proof, the boundary that the remaining zeros can be placed are reduced. If the whole string consist of zeors, we need to introduce two zeros. Otherwise, we need to introduce one zero.
     89 
     90 By summing up the contributions of the segments, we can solve the answer.
     91 
     92 **Code (C++)**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96 using i64 = long long;
     97 
     98 void solve() {
     99     int n;
    100     std::cin >> n;
    101     std::string s;
    102     std::cin >> s;
    103     s = '1' + s + '1';
    104     int ans = 0;
    105     for (int i = 1, l = 0; i <= n; ++i) {
    106         if (s[i] == '0') {
    107             if (s[i-1] == '1') {
    108                 l = i;
    109             }
    110             if (s[i+1] == '1') {
    111                 int c = (l == 1) + (i == n);
    112                 ans += (i - l + 1 + c) / 3;
    113             }
    114         } else {
    115             ++ans;
    116         }
    117     }
    118     std::cout << ans << '\n';
    119 }
    120 
    121 int main() {
    122     std::cin.tie(nullptr)->sync_with_stdio(false);
    123     int T;
    124     std::cin >> T;
    125     while (T--) solve();
    126     return 0;
    127 }
    128 ```
    129 
    130 **Rate the problem!**
    131 
    132 **Quality**
    133 
    134 * Excellent problem
    135 * Good problem
    136 * Average problem
    137 * Bad problem
    138 * Horrible problem
    139 
    140 **Difficulty**
    141 
    142 * Trivial problem
    143 * Easy problem
    144 * Average problem
    145 * Hard problem
    146 * Impossible problem
    147 
    148 [2187A - Restricted Sorting](/contest/2187/problem/A "Codeforces Round 1077 (Div. 1)")
    149 
    150 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    151 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    152 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    153 
    154 **Hint 1**
    155 
    156 For any array of elements, if you can somehow swap any pair of elements (maybe indirectly), you can always sort the array.
    157 
    158 **Hint 2**
    159 
    160 For some $i,j$ such that $|a_i-a_j| \lt k$, how to swap them with help from other elements?
    161 
    162 **Solution**
    163 
    164 Tutorial is loading...
    165 
    166 **Code (Python)**
    167 
    168 ```
    169 for _ in range(int(input())):
    170     n = int(input())
    171     a = list(map(int, input().split()))
    172     b = sorted(a)
    173     if a == b:
    174         print(-1)
    175         continue
    176     print(min(max(a[i] - b[0], b[-1] - a[i]) for i in range(n) if a[i] != b[i]))
    177 ```
    178 
    179 **Rate the problem!**
    180 
    181 **Quality**
    182 
    183 * Excellent problem
    184 * Good problem
    185 * Average problem
    186 * Bad problem
    187 * Horrible problem
    188 
    189 **Difficulty**
    190 
    191 * Trivial problem
    192 * Easy problem
    193 * Average problem
    194 * Hard problem
    195 * Impossible problem
    196 
    197 [2187B - Shortest Statement Ever](/contest/2187/problem/B "Codeforces Round 1077 (Div. 1)")
    198 
    199 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    200 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    201 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__"), [rucaco](/profile/rucaco "Grandmaster rucaco")
    202 
    203 **Hint 1**
    204 
    205 Greedy.
    206 
    207 **Solution**
    208 
    209 Tutorial is loading...
    210 
    211 **Proof of the interesting fact**
    212 
    213 Let $ x, y \in \mathbb{Z}_{\ge 0} $.  
    214 We consider the optimization problem
    215 
    216 $ \min_{p,q \in \mathbb{Z}_{\ge 0}} \; |x - p| + |y - q| \quad \text{subject to} \quad p \,\&\, q = 0, $
    217 
    218 where $\&$ denotes the bitwise AND operation.
    219 
    220 ## Equivalent Formulation
    221 
    222 Define
    223 
    224 $ \mathrm{OPT}(x,y) := \min_{\substack{p,q \ge 0 \\ p \& q = 0}} \bigl(|x-p| + |y-q|\bigr). $
    225 
    226 Define also the restricted optima
    227 
    228 $ \mathrm{OPT}_x(x,y) := \min_{\substack{q \ge 0 \\ x \& q = 0}} |y - q|, \qquad \mathrm{OPT}_y(x,y) := \min_{\substack{p \ge 0 \\ p \& y = 0}} |x - p|. $
    229 
    230 ### Proposition
    231 
    232 $ \boxed{ \mathrm{OPT}(x,y)= \min\{\mathrm{OPT}_x(x,y), \mathrm{OPT}_y(x,y)\} } $
    233 
    234 Equivalently:
    235 
    236 > There exists an optimal solution $(p,q)$ such that $p = x$ **or** $q = y$.
    237 
    238 #### Proof of Equivalence
    239 
    240 * If an optimal solution satisfies $p = x$, then its cost equals $|y - q|$ for some $q$ with $x \& q = 0$, hence $\mathrm{OPT} = \mathrm{OPT}_x$.
    241 * Similarly, if an optimal solution satisfies $q = y$, then $\mathrm{OPT} = \mathrm{OPT}_y$.
    242 * Conversely, if the equality holds, the minimizer in the attaining branch gives an optimal solution with $p=x$ or $q=y$.
    243 
    244 ## Inductive Proof on Bit-Length
    245 
    246 Fix an integer $n \ge 1$.  
    247 Assume
    248 
    249 $ 0 \le x,y \lt 2^n, \quad 0 \le p,q \lt 2^n. $
    250 
    251 Let
    252 
    253 $ W := 2^{n-1}. $
    254 
    255 Write the binary decompositions
    256 
    257 $ x = x_1 W + x_0, \quad y = y_1 W + y_0, $ $ p = p_1 W + p_0, \quad q = q_1 W + q_0, $
    258 
    259 where
    260 
    261 $ x_1,y_1,p_1,q_1 \in \{0,1\}, \quad x_0,y_0,p_0,q_0 \in [0,W). $
    262 
    263 The constraint $p \& q = 0$ implies:
    264 
    265 1. $p_1$ and $q_1$ cannot both be $1$,
    266 2. $p_0 \& q_0 = 0$.
    267 
    268 ## Case 1: No Conflict $(x_1,y_1) \neq (1,1)$
    269 
    270 In this case, the highest bit does not force a trade-off.
    271 
    272 ### Lemma 1
    273 
    274 If $x_1 = 0$, then there exists an optimal solution with $p_1 = 0$. Similarly, if $y_1 = 0$, there exists an optimal solution with $q_1 = 0$.
    275 
    276 #### Proof
    277 
    278 Assume $x_1 = 0$ but $p_1 = 1$. Replace $p$ by $p' = p - W$.
    279 
    280 * Feasibility: clearing a bit of $p$ cannot create a new $1 \& 1$ conflict.
    281 * Optimality: since $x \lt W$,
    282 
    283 $ |x - p'| = |x - (p-W)| \le |x - p|. $
    284 
    285 Thus $p_1$ can be set to $0$ without increasing cost.  
    286 The argument for $q$ is symmetric.
    287 
    288 Hence we may assume
    289 
    290 $ p_1 = x_1, \quad q_1 = y_1. $
    291 
    292 The objective becomes
    293 
    294 $ |x - p| + |y - q|= |x_0 - p_0| + |y_0 - q_0|. $
    295 
    296 This reduces the problem to the $(n-1)$-bit instance $(x_0,y_0)$. By the inductive hypothesis, there exists an optimal solution with $p_0 = x_0$ or $q_0 = y_0$, hence $p = x$ or $q = y$.
    297 
    298 ## Case 2: Conflict $(x_1,y_1) = (1,1)$
    299 
    300 Now the highest bit conflicts, so
    301 
    302 $ (p_1,q_1) \in \{(1,0),(0,1),(0,0)\}. $
    303 
    304 ### Lemma 2
    305 
    306 We could Exclusion of $(0,0)$.
    307 
    308 #### Proof
    309 
    310 Any feasible solution with
    311 
    312 $ p,q \in [0,W) $
    313 
    314 satisfies
    315 
    316 $ |x - p| + |y - q| \ge W + x_0 + y_0 + 1. $
    317 
    318 Moreover, there exists a feasible solution with $(p_1,q_1) = (1,0)$ and cost
    319 
    320 $ x_0 + y_0 + 1. $
    321 
    322 Since $x = W + x_0 \gt p$ and $y = W + y_0 \gt q$,
    323 
    324 $ |x - p| + |y - q|= (W + x_0 - p) + (W + y_0 - q)= 2W + x_0 + y_0 - (p + q). $
    325 
    326 If $p &amp; q = 0$, then binary addition has no carry, hence
    327 
    328 $ p + q = p \oplus q = p \mid q \le W - 1. $
    329 
    330 Therefore
    331 
    332 $ |x - p| + |y - q| \ge 2W + x_0 + y_0 - (W - 1)= W + x_0 + y_0 + 1. $
    333 
    334 Now define
    335 
    336 $ p' := x = W + x_0, \quad q' := W - 1 - x_0. $
    337 
    338 Since $q'$ is the bitwise complement of $x_0$ on the lower $n-1$ bits,
    339 
    340 $ p' \& q' = x_0 \& (W - 1 - x_0) = 0. $
    341 
    342 The cost is
    343 
    344 $ |x - p'| + |y - q'|= 0 + \bigl((W + y_0) - (W - 1 - x_0)\bigr)= x_0 + y_0 + 1. $
    345 
    346 Since $W \ge 1$,
    347 
    348 $ W + x_0 + y_0 + 1 \gt x_0 + y_0 + 1. $
    349 
    350 Thus the $(0,0)$ case cannot be optimal.
    351 
    352 ### Lemma 3
    353 
    354 Fix $(p_1,q_1) = (1,0)$. Then there exists an optimal solution with $p = x$.
    355 
    356 #### Proof
    357 
    358 Write $p = W + p_0$, $q = q_0$. The cost is
    359 
    360 $ |x_0 - p_0| + (W + y_0 - q_0). $
    361 
    362 For fixed $p_0$, this is minimized by maximizing $q_0$ subject to $p_0 \& q_0 = 0$, i.e.
    363 
    364 $ q_0 = W - 1 - p_0. $
    365 
    366 The resulting cost is
    367 
    368 $ y_0 + 1 + \bigl(p_0 + |x_0 - p_0|\bigr). $
    369 
    370 Define $g(t) = t + |x_0 - t|$. Then
    371 
    372 $ g(t) = \begin{cases} x_0, & t \le x_0, \\ 2t - x_0, & t \ge x_0. \end{cases} $
    373 
    374 Hence the minimum is attained at $t = x_0$, yielding $p = x$.
    375 
    376 By symmetry, in the $(0,1)$ case there exists an optimal solution with $q = y$.
    377 
    378 ## Conclusion
    379 
    380 In all cases, there exists an optimal solution $(p,q)$ satisfying
    381 
    382 $ p = x \quad \text{or} \quad q = y. $
    383 
    384 Equivalently,
    385 
    386 $ \mathrm{OPT}(x,y)= \min\{\mathrm{OPT}_x(x,y),\mathrm{OPT}_y(x,y)\}. $
    387 
    388 Proofs of the intended solution are similar with this.
    389 
    390 **Code (C++)**
    391 
    392 ```
    393 #include <bits/stdc++.h>
    394 
    395 using i64 = long long;
    396 
    397 void solve() {
    398     i64 x, y;
    399     std::cin >> x >> y;
    400     i64 min = 1e18, p, q;
    401     auto upd = [&](i64 _p, i64 _q) -> void {
    402         if ((_p & _q) == 0 && abs(_p - x) + abs(_q - y) < min) {
    403             min = abs(_p - x) + abs(_q - y);
    404             p = _p;
    405             q = _q;
    406         }  
    407     };
    408     upd(x, y);
    409     for (int i = 29; i >= 0; i--) {
    410         if ((x & y) >> i & 1) {
    411             upd((x >> i << i) + (1LL << i), y);
    412             upd(x, (y >> i << i) + (1LL << i));
    413             upd(x >> i << i, (y >> i << i) - 1);
    414             upd((x >> i << i) - 1, y >> i << i);
    415         }
    416     }
    417     std::cout << p << " " << q << "\n";
    418 }
    419 
    420 int main() {
    421     std::ios::sync_with_stdio(false);
    422     std::cin.tie(nullptr);
    423     std::cout.tie(nullptr);
    424 
    425     int t;
    426     std::cin >> t;
    427     while (t--) {
    428         solve();
    429     }
    430 }
    431 ```
    432 
    433 **Rate the problem!**
    434 
    435 **Quality**
    436 
    437 * Excellent problem
    438 * Good problem
    439 * Average problem
    440 * Bad problem
    441 * Horrible problem
    442 
    443 **Difficulty**
    444 
    445 * Trivial problem
    446 * Easy problem
    447 * Average problem
    448 * Hard problem
    449 * Impossible problem
    450 
    451 [2187C - Jerry and Tom](/contest/2187/problem/C "Codeforces Round 1077 (Div. 1)")
    452 
    453 * Idea: [Bronya_H](/profile/Bronya_H "Master Bronya_H"), [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    454 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    455 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    456 
    457 **Hint 1**
    458 
    459 What is the optimal strategy for both players?
    460 
    461 **Hint 2**
    462 
    463 If you have obtained a formula for $f(x,y)$, how do you calculate the required sum efficiently, perhaps using some tree techniques?
    464 
    465 **Solution**
    466 
    467 Tutorial is loading...
    468 
    469 **Code (C++)**
    470 
    471 ```
    472 #include <bits/stdc++.h>
    473  
    474 using namespace std;
    475  
    476 using i64 = long long;
    477  
    478 i64 solve_tree(int n, int r, vector<vector<int>> g) {
    479     vector<int> dep(n), sz(n, 1), pa(n);
    480     i64 ans = 0;
    481     auto dfs = [&](auto &&self, int u, int p) -> map<int, int> {
    482         pa[u] = p;
    483         map<int, int> mp;
    484         mp[dep[u]] = 1;
    485         for (auto v : g[u]) if (v != p) {
    486             dep[v] = dep[u] + 1;
    487             auto nmp = self(self, v, u);
    488             if (mp.size() < nmp.size()) swap(mp, nmp);
    489             for (auto &[d, f] : nmp) {
    490                 ans += 1LL * f * mp[d] * (d - dep[u]);
    491                 mp[d] += f;
    492             }
    493             sz[u] += sz[v];
    494         }
    495         return mp;
    496     };
    497     dfs(dfs, r, -1);
    498     for (int u = 0; u < n; u++) {
    499         i64 s = 1LL * sz[u] * (sz[u] - 1) / 2;
    500         for (auto v : g[u]) if (v != pa[u]) s -= 1LL * sz[v] * (sz[v] - 1) / 2;
    501         ans -= 1LL * dep[u] * s;
    502     }
    503     sort(dep.begin(), dep.end());
    504     for (int u = 0; u < n; u++) ans += 1LL * dep[u] * (n - u - 1);
    505     return ans;
    506 }
    507  
    508 void solve() {
    509     int n, m;
    510     cin >> n >> m;
    511     vector<int> a(n);
    512     for (int i = 0; i < n - 1; i++) a[i] = i + 1;
    513     for (int i = 0; i < m; i++) {
    514         int u, v;
    515         cin >> u >> v;
    516         u--;
    517         v--;
    518         a[u] = max(a[u], v);
    519     }
    520     vector<vector<int>> g(n);
    521     for (int i = 0; i < n - 1; i++) g[a[i]].push_back(i);
    522     cout << solve_tree(n, n - 1, g) << "\n";
    523 }
    524  
    525 int main() {
    526     ios::sync_with_stdio(0);
    527     cin.tie(0);
    528  
    529     int t;
    530     cin >> t;
    531     while (t--) solve();
    532 }
    533 ```
    534 
    535 **Bonus**
    536 
    537 Solve the problem in $O(n)$.
    538 
    539 **Rate the problem!**
    540 
    541 **Quality**
    542 
    543 * Excellent problem
    544 * Good problem
    545 * Average problem
    546 * Bad problem
    547 * Horrible problem
    548 
    549 **Difficulty**
    550 
    551 * Trivial problem
    552 * Easy problem
    553 * Average problem
    554 * Hard problem
    555 * Impossible problem
    556 
    557 [2187D - Cool Problem](/contest/2187/problem/D "Codeforces Round 1077 (Div. 1)")
    558 
    559 * Idea: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")
    560 * Solution: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")
    561 * Editorial: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan")
    562 
    563 **Solution**
    564 
    565 Tutorial is loading...
    566 
    567 **Code (C++)**
    568 
    569 ```
    570 #include <bits/stdc++.h>
    571 
    572 using namespace std;
    573 
    574 using B = bitset<100001>;
    575 
    576 using i64 = long long;
    577 using i128 = __int128_t;
    578 
    579 constexpr i64 MOD = 998244353;
    580 
    581 vector<i64> calc(int n, string &s, i64 x, i64 y) {
    582     B bf0, bf1, br0, br1;
    583     bf0.set(0);
    584     br0.set(0);
    585     for (auto c : s) {
    586         B nbf0, nbf1, nbr0, nbr1;
    587         if (c != '1') {
    588             nbf0 |= bf0 << 1;
    589             nbf1 |= bf1 << 1;
    590             nbr0 |= br0 >> 1;
    591             nbr1 |= br1 >> 1;
    592         }
    593         if (c != '0') {
    594             nbf0 |= br1;
    595             nbf1 |= br0;
    596             nbr0 |= bf1;
    597             nbr1 |= bf0;
    598         }
    599         nbf0[0] = nbf0[0] | nbr0[0];
    600         nbr0[0] = nbr0[0] | nbf0[0];
    601         nbf1[0] = nbf1[0] | nbr1[0];
    602         nbr1[0] = nbr1[0] | nbf1[0];
    603         bf0 = nbf0;
    604         bf1 = nbf1;
    605         br0 = nbr0;
    606         br1 = nbr1;
    607     }
    608     vector<i64> res;
    609     auto tosum = [&](i64 c) -> i64 {
    610         return (i128(c) * c + i128(x - y) * c + i128(n) * x * y) / (2 * x);
    611     };
    612     for (int i = 0; i <= n; i++) {
    613         if (bf0[i]) res.push_back(tosum(i * x));
    614         if (bf1[i]) res.push_back(tosum(i * x + y));
    615     }
    616     for (int i = 1; i <= n; i++) {
    617         if (br0[i]) res.push_back(tosum(-i * x));
    618         if (br1[i]) res.push_back(tosum(-i * x + y));
    619     }
    620     sort(res.begin(), res.end());
    621     res.erase(unique(res.begin(), res.end()), res.end());
    622     return res;
    623 }
    624 
    625 void solve() {
    626     int n;
    627     cin >> n;
    628     i64 x, y;
    629     cin >> x >> y;
    630     string s;
    631     cin >> s;
    632     auto rs = calc(n, s, x, y);
    633     i64 ans = 0;
    634     for (auto v : rs) ans = (ans + (v % MOD + MOD)) % MOD;
    635     cout << ans << "\n";
    636 }
    637 
    638 int main() {
    639     ios::sync_with_stdio(0);
    640     cin.tie(0);
    641 
    642     int t;
    643     cin >> t;
    644     while (t--) solve();
    645 
    646 }
    647 ```
    648 
    649 **Rate the problem!**
    650 
    651 **Quality**
    652 
    653 * Excellent problem
    654 * Good problem
    655 * Average problem
    656 * Bad problem
    657 * Horrible problem
    658 
    659 **Difficulty**
    660 
    661 * Trivial problem
    662 * Easy problem
    663 * Average problem
    664 * Hard problem
    665 * Impossible problem
    666 
    667 [2187E - Doors and Keys](/contest/2187/problem/E "Codeforces Round 1077 (Div. 1)")
    668 
    669 * Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
    670 * Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
    671 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    672 
    673 **Hint 1**
    674 
    675 Can you transform some constraints of the problem into something easier to handle?
    676 
    677 **Hint 2**
    678 
    679 Try to come up with a dynamic programming solution that runs in polynomial time.
    680 
    681 **Hint 3**
    682 
    683 How do you optimize your solution? Pay attention to any unusual constraints.
    684 
    685 **Solution**
    686 
    687 Tutorial is loading...
    688 
    689 **Code (Python)**
    690 
    691 ```
    692 for _ in range(int(input())):
    693     n = int(input())
    694     a = list(map(int, input().split()))
    695     s = input()
    696     f = [10 ** 9] * 320
    697     f[0] = 0
    698     for i in range(n):
    699         if s[i] == "1":
    700             for j in range(318, -1, -1):
    701                 f[j + 1] = min(f[j + 1], f[j])
    702         nf = [10 ** 9] * 320
    703         for j in range(320):
    704             nf[j] = min(nf[j], max(f[j], a[i]) + max(1, 2 * j - 1))
    705             if j:
    706                 nf[j - 1] = min(nf[j - 1], f[j] + 2 * j - 1)
    707         print(nf[0]) 
    708         f = nf
    709 ```
    710 
    711 **Bonus**
    712 
    713 Solve the problem in $O(n \operatorname{polylog} n)$.
    714 
    715 **Rate the problem!**
    716 
    717 **Quality**
    718 
    719 * Excellent problem
    720 * Good problem
    721 * Average problem
    722 * Bad problem
    723 * Horrible problem
    724 
    725 **Difficulty**
    726 
    727 * Trivial problem
    728 * Easy problem
    729 * Average problem
    730 * Hard problem
    731 * Impossible problem
    732 
    733 [2187F1 - Al Fine (Maximizing Version)](/contest/2187/problem/F1 "Codeforces Round 1077 (Div. 1)")
    734 
    735 * Idea: [-firefly-](/profile/-firefly- "Master -firefly-")
    736 * Solution: [-firefly-](/profile/-firefly- "Master -firefly-")
    737 * Editorial: [-firefly-](/profile/-firefly- "Master -firefly-")
    738 
    739 **Hint 1**
    740 
    741 Processing two permutations is difficult. How can we reduce them to one?
    742 
    743 **Answer**
    744 
    745 To simplify the problem, we can relabel the vertices such that one of the DFS orders becomes the identity permutation $[0,1,2,\dots,n]$.
    746 
    747 Specifically, let $mp[v]$ be the index of vertex $v$ in Arietta's DFS order $b$. We then transform Tortinita's DFS order $a$ into a new sequence $c$, where $c_i = mp[a_i]$. After this transformation:
    748 
    749 * Arietta's sequence is effectively normalized to $0, 1, 2, \dots, n$.
    750 * Tortinita's sequence $c$ now represents the relative positions of her nodes in Arietta's tree.
    751 
    752 This reduces the problem from handling two arbitrary permutations to analyzing a single permutation $c$ relative to the natural order.
    753 
    754 **Hint 2**
    755 
    756 In a DFS order, the nodes of any subtree form a contiguous segment, with the root of the subtree appearing at the very beginning of that segment. What property does this imply for our problem?
    757 
    758 **Answer**
    759 
    760 After relabeling, any subtree in Arietta's tree not only forms a contiguous segment in terms of positions but also in terms of values (i.e., the set of values will be $[L, L+1, \dots, R]$).
    761 
    762 This implies that for a common subtree to exist, if a segment $[L, L+1, \dots, R]$ represents a subtree in Arietta's tree, there must exist a corresponding segment in Tortinita's DFS order $c$ such that:
    763 
    764 * The first element of the segment is $l$.
    765 * The remaining $r-l$ elements are a permutation of the set ${L+1, L+2, \dots, R}$.
    766 
    767 **Hint 3**
    768 
    769 The property that a segment must be a "permutation of a specific set" is not straightforward to check directly. Is there a way to simplify this condition into something more computationally efficient?
    770 
    771 **Answer**
    772 
    773 We can simplify this condition by leveraging the relationship between the maximum, minimum, and the length of the segment.
    774 
    775 For a subsegment of $c$ starting at index $l$ and ending at index $r$ (i.e., $c[l \dots r]$), it represents a common subtree if and only if:
    776 
    777 * $c[l] = \min(c[l \dots r])$: The first element must be the minimum value in the segment (acting as the root).
    778 * $\max(c[l \dots r]) - \min(c[l \dots r]) = r - l$: The range of values is exactly equal to the number of edges, meaning the values are consecutive.
    779 
    780 **Hint 4**
    781 
    782 Because each valid segment can be mapped to a subtree, the valid segments form a laminar family (i.e., they do not cross). Any two valid segments are either completely disjoint or one is strictly contained inside the other.
    783 
    784 **Hint 5**
    785 
    786 The problem asks for the largest depth. To achieve this, we can greedily find the largest valid segment for every fixed start position.
    787 
    788 **Solution**
    789 
    790 Read the hints above.
    791 
    792 Recall that we need to solve for any $1 \le l \le n$, the largest $r$ such that:
    793 
    794 * $c[l] = \min(c[l \dots r])$
    795 * $\max(c[l \dots r]) - \min(c[l \dots r]) = r - l$
    796 
    797 There are multiple ways to solve this. We will introduce a divide-and-conquer approach.
    798 
    799 To solve this problem using a divide-and-conquer approach, we define a recursive function that processes the interval $[l, r]$. The core logic handles the sub-problems where the valid range $[i, j]$ crosses the midpoint $mid$ (with $l \le i \le mid \lt j \le r$).
    800 
    801 We precompute the prefix minimums and maximums for the right half ($mid + 1 \dots r$) and the suffix minimums and maximums for the left half ($l \dots mid$). Let's denote the suffix values for index $i$ as $min[i]$ and $max[i]$, and similarly for the prefix values at index $j$.
    802 
    803 The problem requires $c[i] = \min(c[i \dots j])$. Since we are iterating $i$ from $mid$ down to $l$, this condition implies that $c[i]$ must be the minimum of the left part $c[i \dots mid]$. If $min[i] \neq min[i+1]$, it indicates that $c[i]$ is strictly smaller than the minimum of the range to its right, making it a candidate for the global minimum.
    804 
    805 For such valid $i$, we consider two cases based on the location of the maximum value in the range $[i, j]$:
    806 
    807 **Case 1: The Maximum is on the Left**
    808 
    809 If the maximum value of the range is determined by the left side (i.e., $\max(c[i \dots j]) = max[i]$), the equation $\max - \min = j - i$ can be rewritten to determine the specific target index $j$:
    810 
    811 $j = i + max[i] - min[i]$
    812 
    813 We simply calculate this candidate $j$ and verify three conditions:
    814 
    815 * $j$ is within the valid right range ($mid \lt j \le r$).
    816 * The minimum on the right does not contradict our global minimum assumption ($min[j] \gt min[i]$).
    817 * The maximum on the right is not larger than our current maximum ($max[j] \lt max[i]$).
    818 
    819 If these hold, we update the answer for $i$.
    820 
    821 **Case 2: The Maximum is on the Right**
    822 
    823 If the maximum value is on the right side (i.e., $\max(c[i \dots j]) = max[j]$), the equation becomes:
    824 
    825 $max[j] - min[i] = j - i$
    826 
    827 Rearranging the terms to separate $i$ and $j$, we get:
    828 
    829 $max[j] - j = min[i] - i$
    830 
    831 To solve this efficiently, we group the indices $j$ from the right half based on the value of $max[j] - j$. For each $i$, we simply access the corresponding group to find the largest $j$ that satisfies the remaining validity conditions ($min[j] \gt min[i]$ and $max[j] \gt max[i]$). Because $max[j]$ is monotonic, we can introduce two-pointer strategy to avoid the $\log$ factor.
    832 
    833 By conducting this algorithm, we can solve the largest valid segments for each start position. Then, we can use a stack to simulate the dfs process of the common tree, and solve the maximum depth easily.
    834 
    835 The time complexity is $O(n\log n)$ by careful implementation.
    836 
    837 **Code (C++)**
    838 
    839 ```
    840 #include <bits/stdc++.h>
    841 using i64 = long long;
    842 
    843 void solve() {
    844     int n;
    845     std::cin >> n;
    846     std::vector<int> a(n+1), b(n+1);
    847     for (int i = 1; i <= n; ++i) std::cin >> a[i];
    848     for (int i = 1; i <= n; ++i) std::cin >> b[i];
    849     std::vector<int> mp(n+1), c(n+1), R(n+1);
    850     for (int i = 1; i <= n; ++i) mp[b[i]] = i;
    851     for (int i = 1; i <= n; ++i) c[i] = mp[a[i]];
    852     for (int i = 1; i <= n; ++i) mp[c[i]] = i;
    853     std::vector<int> min(n + 1), max(n + 1);
    854     std::vector<std::vector<std::pair<int, int>>> rmax(2 * n + 1);
    855     std::vector<int> p(2 * n + 1);
    856 
    857     auto work = [&](auto &&self, int l, int r) -> void {
    858         if (l >= r) return;
    859         int mid = l + (r - l) / 2;
    860         self(self, l, mid);
    861         self(self, mid + 1, r);
    862         min[mid] = max[mid] = c[mid];
    863         for (int i = mid - 1; i >= l; --i) {
    864             min[i] = std::min(min[i + 1], c[i]);
    865             max[i] = std::max(max[i + 1], c[i]);
    866         }
    867         min[mid + 1] = max[mid + 1] = c[mid + 1];
    868         rmax[c[mid + 1] - mid - 1 + n].emplace_back(c[mid + 1], mid + 1);
    869         for (int i = mid + 2; i <= r; ++i) {
    870             min[i] = std::min(min[i - 1], c[i]);
    871             max[i] = std::max(max[i - 1], c[i]);
    872             rmax[max[i] - i + n].emplace_back(min[i], i);
    873         }
    874         for (int i = mid; i >= l; --i) {
    875             if (min[i] != min[i + 1]) {
    876                 int j = i + max[i] - min[i];
    877                 if (j > mid && j <= r && min[j] > min[i] && max[j] < max[i]) {
    878                     R[i] = std::max(R[i], j);
    879                 }
    880                 j = min[i] - i + n;
    881                 while (p[j] < std::ssize(rmax[j]) && rmax[j][p[j]].first > min[i]) {
    882                     ++p[j];
    883                 }
    884                 if (p[j]) {
    885                     int k = rmax[j][p[j] - 1].second;
    886                     if (max[k] > max[i]) R[i] = std::max(R[i], k);
    887                 }
    888             }
    889         }
    890         for (int i = mid + 1; i <= r; ++i) {
    891             rmax[max[i] - i + n].clear();
    892             p[max[i] - i + n] = 0;
    893         }
    894     };
    895     work(work, 1, n);
    896 
    897     std::stack<int> st;
    898     int ans = 0;
    899     for (int i = 1; i <= n; ++i) {
    900         while (!st.empty() && st.top() <= i) st.pop();
    901         if (R[i]) {
    902             st.push(R[i]);
    903             ans = std::max(ans, int(st.size()));
    904         }
    905     }
    906     std::cout << (ans + 1) << '\n';
    907 }
    908 
    909 int main() {
    910     std::cin.tie(nullptr)->sync_with_stdio(false);
    911     int T = 1;
    912     std::cin >> T;
    913     while (T--) solve();
    914     return 0;
    915 }
    916 ```
    917 
    918 **Fun Fact**
    919 
    920 The problem background is a tribute to the visual novel *Symphonic Rain*. I highly recommend you to play it!
    921 
    922 **Rate the problem!**
    923 
    924 **Quality**
    925 
    926 * Excellent problem
    927 * Good problem
    928 * Average problem
    929 * Bad problem
    930 * Horrible problem
    931 
    932 **Difficulty**
    933 
    934 * Trivial problem
    935 * Easy problem
    936 * Average problem
    937 * Hard problem
    938 * Impossible problem
    939 
    940 [2187F2 - Al Fine (Counting Version)](/contest/2187/problem/F2 "Codeforces Round 1077 (Div. 1)")
    941 
    942 * Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
    943 * Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
    944 * Editorial: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
    945 
    946 **Solution**
    947 
    948 Construct the optimal tree by following the approach used in F1. Two child nodes $a$ and $b$ of a node are defined as entangled if and only if $a$ and $b$ appear in different orders in the two permutations. The maximal entangled set of a node's children is defined as the largest connected component formed by the entangled relationships among its children.
    949 
    950 Theorem $1$: Each maximal entangled set and the points in its subtree must form an interval in both DFS sequences.
    951 
    952 Proof: Suppose one DFS sequence contains nodes $a, b, c$ such that $a$ and $c$ belong to the same maximal entanglement set while $b$ does not. Then in the other DFS sequence, all nodes after $b$ must appear after $a$ and before $c$. Thus $a$ and $c$ cannot be entangled, leading to a contradiction.
    953 
    954 Theorem $2$: Among the maximal entangled sets of a leaf node, if any maximal entangled set contains only one node, then this maximal entangled set must be the last maximal entangled set to appear in both DFS sequences.
    955 
    956 Proof: Suppose there exists a maximal entanglement set with a single node that is not the latest maximal entanglement set in either DFS sequence. Then all subsequent maximal entanglement sets must be able to be connected under this node, contradicting the optimal tree property.
    957 
    958 Theorem $3$: A maximal entanglement set must be connected under the same node in any valid tree.
    959 
    960 Proof: For a pair of entangled child nodes $x, y$ of node $a$ in an optimal tree, let $p_x$ and $p_y$ be the ancestors of $x$ and $y$, respectively. Since $p_x$ and $p_y$ cannot be points in the subtree of $a$ other than $a$ itself (otherwise it contradicts the optimal tree structure). Furthermore, since $x$ appears earlier than $y$ in some DFS sequence, traversing from $x$ to $y$ requires popping all other nodes in $a$'s subtree (because $p_y$ is not within the maximal entangled group's range). This implies that traversing from $x$ to $y$ can only be achieved by popping $p_y$ multiple times from $x$ and then attaching $y$ to $p_y$. Thus, $p_y$ must be an ancestor of $p_x$. Similarly, $p_x$ must also be an ancestor of $p_y$, so $p_x = p_y$.
    961 
    962 Theorem $4$: If a maximal entanglement set has size greater than 1, then on any valid tree, if the parent node of this maximal entanglement set is $p$, then the subtree of all nodes within this maximal entanglement set must lie within the subtree of $p$.
    963 
    964 Proof: Suppose a node $d$ in the subtree of some node $x$ within the maximal entanglement set does not lie within the subtree of $p$. Find a node $y$ entangled with $x$. Then, in the DFS sequence where $x$ appears before $y$, $d$ must lie between $x$ and $y$, contradicting that $d$ is not in the subtree of $p$.
    965 
    966 Therefore, each maximal entanglement set greater than $1$ can be collapsed into a single node, treated as a leaf attached to its parent. At this point, the two DFS sequences become identical. The number of solutions is thus equal to the number of trees where the DFS sequences perfectly match and every node that was originally in a maximal entanglement set remains a leaf in the new tree. For solutions within each maximal entanglement set, we can recursively compute the number of trees matching the DFS sequence for each node within that set. Multiplying these values yields the total number of valid trees.
    967 
    968 Consider counting the number of trees where the DFS sequence is identical to the given sequence, and every node that was originally in a maximal entanglement set remains a leaf in the new tree. Treat the DFS process as a bracket sequence: entering a new node is treated as a left bracket, and exiting a node is treated as a right bracket. If a node is a leaf, then the next bracket after its left bracket must be a right bracket. Thus, the problem asks for the number of bracket sequences that satisfy having $n$ left brackets and right brackets, where the next bracket after the $a_1, a_2, \dots, a_m$th left bracket is always a right bracket. A simple $O(n^2)$ dynamic programming approach suffices to find the answer.
    969 
    970 The overall time complexity is $O(n^2)$.
    971 
    972 **Code (C++)**
    973 
    974 ```
    975 #include<bits/stdc++.h>
    976 using namespace std;
    977 const long long mod=1000000007;
    978 long long ans;
    979 int a[5000],b[5000],pa[5000],pb[5000],tvis[5000],cvis[5000],zvis[5000];
    980 vector<int>line[5001];
    981 int dep[5001],cntsg[5001],wp[5001];
    982 vector<int>vec;
    983 long long dp[5001],tdp[5001];
    984 long long solve(){
    985 	long long i,j,n=vec.size(),csum;
    986 	for(i=0;i<=n;i++)dp[i]=0;
    987 	dp[0]=1;
    988 	for(i=0;i<n;i++)
    989 	{
    990 		for(j=0;j<n;j++)tdp[j+vec[i]]=(tdp[j+vec[i]]+dp[j])%mod;
    991 		csum=0;
    992 		for(j=n;j>=0;j--)
    993 		{
    994 			csum=(csum+tdp[j])%mod;
    995 			dp[j]=csum;
    996 			tdp[j]=0;
    997 		}
    998 	}
    999 	vec.clear();
   1000 	return dp[0];
   1001 }
   1002 void dfs(int t){
   1003 	vector<int>::iterator it;
   1004 	int i;
   1005 	for(i=0;i<cntsg[t];i++)vec.push_back(0);
   1006 	if(wp[t]==-1)ans=ans*solve()%mod;
   1007 	else
   1008 	{
   1009 		vec.push_back(1);
   1010 		dfs(wp[t]);
   1011 	}
   1012 	for(it=line[t].begin();it!=line[t].end();it++)
   1013 	{
   1014 		if(*it==wp[t])continue;
   1015 		vec.push_back(1);
   1016 		dfs(*it);
   1017 	}
   1018 }
   1019 int main(){
   1020 	ios::sync_with_stdio(false),cin.tie(0);
   1021 	int T,n,i,j,t,ccnt,r;
   1022 	for(cin>>T;T>0;T--)
   1023 	{
   1024 		cin>>n;
   1025 		for(i=0;i<n;i++)
   1026 		{
   1027 			cin>>a[i];
   1028 			a[i]--;
   1029 			pa[a[i]]=i;
   1030 		}
   1031 		for(i=0;i<n;i++)
   1032 		{
   1033 			cin>>b[i];
   1034 			b[i]--;
   1035 			pb[b[i]]=i;
   1036 		}
   1037 		for(i=0;i<n;i++)tvis[i]=0;
   1038 		for(i=n-1;i>-1;i--)
   1039 		{
   1040 			t=pb[a[i]];
   1041 			cntsg[i]=0;
   1042 			wp[i]=-1;
   1043 			for(j=0;j<n;j++)
   1044 			{
   1045 				cvis[j]=0;
   1046 				zvis[j]=0;
   1047 			}
   1048 			ccnt=0;
   1049 			r=-1;
   1050 			for(j=0;i+j<n&&t+j<n;j++)
   1051 			{
   1052 				if(cvis[a[i+j]]==0)ccnt++;
   1053 				cvis[a[i+j]]++;
   1054 				if(cvis[a[i+j]]==0)ccnt--;
   1055 				if(cvis[b[t+j]]==0)ccnt++;
   1056 				cvis[b[t+j]]--;
   1057 				if(cvis[b[t+j]]==0)ccnt--;
   1058 				if(ccnt==0)
   1059 				{
   1060 					zvis[i+j]=1;
   1061 					r=i+j;
   1062 				}
   1063 			}
   1064 			for(j=i+1;j<=r;j++)
   1065 			{
   1066 				if(tvis[j])
   1067 				{
   1068 					line[i].push_back(j);
   1069 					tvis[j]=0;
   1070 					if(zvis[j-1])
   1071 					{
   1072 						cntsg[i]++;
   1073 						wp[i]=j;
   1074 					}
   1075 					else wp[i]=-1;
   1076 				}
   1077 			}
   1078 			if(wp[i]!=-1)cntsg[i]--;
   1079 			tvis[i]=1;
   1080 		}
   1081 		cntsg[n]=0;
   1082 		wp[n]=-1;
   1083 		for(i=0;i<n;i++)
   1084 		{
   1085 			cvis[i]=0;
   1086 			zvis[i]=0;
   1087 		}
   1088 		ccnt=0;
   1089 		r=-1;
   1090 		for(i=0;i<n;i++)
   1091 		{
   1092 			if(cvis[a[i]]==0)ccnt++;
   1093 			cvis[a[i]]++;
   1094 			if(cvis[a[i]]==0)ccnt--;
   1095 			if(cvis[b[i]]==0)ccnt++;
   1096 			cvis[b[i]]--;
   1097 			if(cvis[b[i]]==0)ccnt--;
   1098 			if(ccnt==0)
   1099 			{
   1100 				zvis[i]=1;
   1101 				r=i;
   1102 			}
   1103 		}
   1104 		for(i=0;i<n;i++)
   1105 		{
   1106 			if(tvis[i])
   1107 			{
   1108 				line[n].push_back(i);
   1109 				tvis[i]=0;
   1110 				if(i==0||zvis[i-1])
   1111 				{
   1112 					cntsg[n]++;
   1113 					wp[n]=i;
   1114 				}
   1115 				else wp[n]=-1;
   1116 			}
   1117 		}
   1118 		if(wp[n]!=-1)cntsg[n]--;
   1119 		ans=1;
   1120 		dep[n]=0;
   1121 		dfs(n);
   1122 		for(i=0;i<=n;i++)line[i].clear();
   1123 		cout<<ans<<'\n';
   1124 	}
   1125 	return 0;
   1126 }
   1127 ```
   1128 
   1129 **Bonus**
   1130 
   1131 Solve the problem in $O(n \log^2 n)$.
   1132 
   1133 **Rate the problem!**
   1134 
   1135 **Quality**
   1136 
   1137 * Excellent problem
   1138 * Good problem
   1139 * Average problem
   1140 * Bad problem
   1141 * Horrible problem
   1142 
   1143 **Difficulty**
   1144 
   1145 * Trivial problem
   1146 * Easy problem
   1147 * Average problem
   1148 * Hard problem
   1149 * Impossible problem
   1150 
   1151 [2187G - Many Cartesian Trees](/contest/2187/problem/G "Codeforces Round 1077 (Div. 1)")
   1152 
   1153 * Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
   1154 * Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
   1155 * Editorial: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk")
   1156 
   1157 **Solution**
   1158 
   1159 Observation 0: If $q_1,q_2,\dots,q_n$ is valid, then $q_1\bmod n+1,q_2\bmod n+1,\dots,q_n\bmod n+1$ is another valid $q$. This is obvious.
   1160 
   1161 Therefore, we do not need the exact original labeling of values. We may assume $q_v=n$.
   1162 
   1163 Define $Child_v={u\mid s[u][v]=1}$; Define $smn_v = min_{u\in Child_v}u$; Define $smx_v = max_{u\in Child_v}u$.
   1164 
   1165 Observation 1: If the value at index $v$ is $n$, then the position of $n−1$ must be either $mn_v$ or $mx_v$.
   1166 
   1167 Proof: If $q_{x}=n-1$, and $smn_v \lt x \lt smx_v$. Then the parent node of at least one of $mn_v$ and $mx_v$ must be $x$. This is contrary to the previous assumption.
   1168 
   1169 So we only need to choose between these two candidates. We may assume $q_u=n-1$.
   1170 
   1171 Define an edge $(u, parent_u)$ to cross index $v$ if $u$ and its parent lie on different sides of $v$, in other words, $(u-v)\cdot(parent_u-v) \lt 0$.
   1172 
   1173 Observation 2: In every Cartesian tree during the process, the edge between index $u$ ($q_u=n-1$) and its parent $(u, parent_u)$ never cross the index $v$ ($q_v=n$).
   1174 
   1175 Proof: For every node on a Cartesian tree, its parent node must be the closest node greater than it. If this edge $(u, parent_u)$ crosses node v, then one side's closest point to node u becomes v, leading to a contradiction.
   1176 
   1177 Now let's decide whether $n−1$ is on the left or right. We are at index $v$ (treat it as value $n$).
   1178 
   1179 Case A: all extreme children are on one side. If $smx_v \lt v$, then every child that ever attaches to $v$ lies left of $v$. Therefore $n−1$ must be on the left, and by Observation 1 it must be $smn_v$. If $smn_v \gt v$, similarly $n−1$ must be on the right, hence it must be $smx_v$.
   1180 
   1181 Case B: children exist on both sides ($smn_v \lt v \lt smx_v$)
   1182 
   1183 Observation 3: In the case B ($smn_v \lt v \lt smx_v$), among these two extreme children, one must have at least one parent edge crosses $v$, and the other one mustn't.
   1184 
   1185 Proof: One child $q_x=n-1$ mustn't have a parent edge that crosses the index $v$ ($q_v=n$) due to the observation 2. For the other child node $q_y$, when $q_x=n-1$ is the root node, the parent node of $q_y$ must be $q_x$. They are on both sides of index $v$ ($q_v=n$). Therefore, it has at least one parent edge that crosses the index $v$ ($q_v=n$).
   1186 
   1187 Similarly, define $Fa_v={u\mid s[v][u]=1}$; Define $fmn_v = min_{u\in Fa_v}u$; Define $fmx_v = max_{u\in Fa_v}u$.
   1188 
   1189 If $fmx_{smn_v} \lt v$, then $smn_v$ doesn't have a parent edge that crosses $v$, then $q_{smn_v} = n - 1$. And vice versa.
   1190 
   1191 The time complexity is $O(n^2)$. The bottleneck is preprocessing the input data.
   1192 
   1193 **Code (C++)**
   1194 
   1195 ```
   1196 #include <bits/stdc++.h>
   1197 using namespace std;
   1198 using i64 = long long;
   1199 
   1200 signed main() {
   1201     cin.tie(nullptr)->sync_with_stdio(false);
   1202 
   1203     int t;
   1204     cin >> t;
   1205     while (t--) {
   1206         int n;
   1207         cin >> n;
   1208         vector<int> fa_mx(n + 1), fa_mn(n + 1, n);
   1209         vector<int> son_mx(n + 1), son_mn(n + 1, n);
   1210         vector<vector<int>> fa(n + 1), son(n + 1);
   1211         for (int i = 1; i <= n; i++) {
   1212             string s;
   1213             cin >> s;
   1214             s = ' ' + s;
   1215             for (int j = 1; j <= n; j++) {
   1216                 if (i == j or s[j] == '0') continue;
   1217                 int u = j, v = i;
   1218                 fa_mx[v] = max(fa_mx[v], u);
   1219                 fa_mn[v] = min(fa_mn[v], u);
   1220                 son_mx[u] = max(son_mx[u], v);
   1221                 son_mn[u] = min(son_mn[u], v);
   1222             }
   1223         }
   1224         vector<int> a(n + 1);
   1225         for (int p = n, val = n; ; val--) {
   1226             a[p] = val;
   1227             if (val == 1) break;
   1228             int mn = son_mn[p], mx = son_mx[p];
   1229             if (mx < p) {
   1230                 p = mn;
   1231             } else if (mn > p) {
   1232                 p = mx;
   1233             } else {
   1234                 int mx1 = fa_mx[mn];
   1235                 if (mx1 <= p) {
   1236                     p = mn;
   1237                 } else {
   1238                     int mn2 = fa_mn[mx];
   1239                     assert(mn2 >= p);
   1240                     p = mx;
   1241                 }
   1242             }
   1243         }
   1244         for (int i = 1; i <= n; i++) {
   1245             cout << a[i] << " \n"[i == n];
   1246         }
   1247     }
   1248 }
   1249 ```
   1250 
   1251 **Rate the problem!**
   1252 
   1253 **Quality**
   1254 
   1255 * Excellent problem
   1256 * Good problem
   1257 * Average problem
   1258 * Bad problem
   1259 * Horrible problem
   1260 
   1261 **Difficulty**
   1262 
   1263 * Trivial problem
   1264 * Easy problem
   1265 * Average problem
   1266 * Hard problem
   1267 * Impossible problem