2187.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 & 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