2229.md (57963B)
1 Source: https://codeforces.com/blog/entry/153948 2 3 Thank you for participating in our round! We hope you enjoyed the problems as much as we enjoyed preparing them. 4 5 **Rate the contest!** 6 7 **Quality** 8 9 * Absolute Cinema contest 10 * Excellent contest 11 * Good contest 12 * Average contest 13 * Bad contest 14 * Horrible contest 15 16 **Difficulty** 17 18 * Trivial contest 19 * Easy contest 20 * Average contest 21 * Hard contest 22 * Impossible contest 23 24 [2229A - Слаймы на прямой](/contest/2229/problem/A) 25 26 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 27 28 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 29 30 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan") 31 32 **Hint 1** 33 34 Let $y$ denote the final position of all of the slimes. Then it is optimal to choose $x = y$ for every operation. 35 36 **Hint 2** 37 38 Let $\mathrm{mn}$ denote the minimum value in $a$, and let $\mathrm{mx}$ denote the maximum value in $a$. Now, the number of operations that you need to apply is equal to $\max(y - \mathrm{mn}, \mathrm{mx} - y)$. 39 40 **Solution** 41 42 We want to choose the value of $y$ that minimizes $\max(y - \mathrm{mn}, \mathrm{mx} - y)$. Therefore, we will choose the value that is closest to the middle of $\mathrm{mn}$ and $\mathrm{mx}$. This yields a final answer of $\lceil \frac{\mathrm{mx} - \mathrm{mn}}{2} \rceil$. 43 44 **Code** 45 46 ``` 47 #include<bits/stdc++.h> 48 using namespace std; 49 typedef long long ll; 50 #define debug(x) cout << #x << " = " << x << "\n"; 51 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 52 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 53 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 54 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 55 56 void solve(){ 57 int n; 58 cin >> n; 59 60 vector<int> a(n); 61 for (int &x : a) cin >> x; 62 63 int mx = *max_element(a.begin(), a.end()); 64 int mn = *min_element(a.begin(), a.end()); 65 cout << (mx - mn + 1) / 2 << "\n"; 66 } 67 68 int main(){ 69 ios::sync_with_stdio(false); 70 cin.tie(0); 71 72 int t; 73 cin >> t; 74 while (t--) solve(); 75 } 76 ``` 77 78 **Rate the problem!** 79 80 **Quality** 81 82 * Excellent problem 83 * Good problem 84 * Average problem 85 * Bad problem 86 * Horrible problem 87 88 **Difficulty** 89 90 * Trivial problem 91 * Easy problem 92 * Average problem 93 * Hard problem 94 * Impossible problem 95 96 [2229B - Это шедевр!](/contest/2229/problem/B) 97 98 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 99 100 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 101 102 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan") 103 104 **Hint 1** 105 106 Consider each index separately. For one of the indices, you will gain value equal to $a_i + b_i$. For all of the other indices, you will gain value equal to $b_i$ only. 107 108 **Hint 2** 109 110 It is never bad to put the larger value in $b_i$. 111 112 **Solution** 113 114 We should swap any $a_i$ where $a_i \gt b_i$, because we would prefer for the larger value to be in $b_i$. In total, we gain value equal to the maximums of each pair, plus the largest of the minimums of each pair. 115 116 **Code** 117 118 ``` 119 #include<bits/stdc++.h> 120 using namespace std; 121 typedef long long ll; 122 #define debug(x) cout << #x << " = " << x << "\n"; 123 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 124 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 125 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 126 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 127 128 void solve(){ 129 int n; 130 cin >> n; 131 132 vector<int> a(n), b(n); 133 for (int &x : a) cin >> x; 134 for (int &x : b) cin >> x; 135 136 ll sum = 0; 137 for (int i = 0; i < n; i++) 138 sum += max(a[i], b[i]); 139 140 ll ans = 0; 141 for (int i = 0; i < n; i++) 142 ans = max(ans, sum + min(a[i], b[i])); 143 144 cout << ans << "\n"; 145 } 146 147 int main(){ 148 ios::sync_with_stdio(false); 149 cin.tie(0); 150 151 int t; 152 cin >> t; 153 while (t--) solve(); 154 } 155 ``` 156 157 **Rate the problem!** 158 159 **Quality** 160 161 * Excellent problem 162 * Good problem 163 * Average problem 164 * Bad problem 165 * Horrible problem 166 167 **Difficulty** 168 169 * Trivial problem 170 * Easy problem 171 * Average problem 172 * Hard problem 173 * Impossible problem 174 175 [2229C1 - Время переворотов (простая версия)](/contest/2229/problem/C1) [2229C2 - Время переворотов (сложная версия)](/contest/2229/problem/C2) 176 177 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 178 179 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 180 181 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan") 182 183 **Hint 1** 184 185 Suppose you have a positive element. You can make this element negative without affecting any later elements by applying an operation onto it directly. 186 187 **Solution (Easy Version)** 188 189 You can make all of the elements negative. To do so, consider each index starting from $n$ to $1$. If it is currently positive, you can apply an operation on this index, turning it negative. 190 191 **Hint 2** 192 193 Let $\mathrm{idx}$ be the largest index you ever operate on. Then since you can never flip its sign using an operation on a later index, $a_{\mathrm{idx}}$ must initially be positive, and it will be negative after performing the operation. 194 195 **Solution (Hard Version)** 196 197 Read the hints. In fact, it is always possible to make all elements before $\mathrm{idx}$ positive. Thus, in the end you end up with either the original array (if you applied no operations), or an array of the form $[|a_1|, ..., |a_{\mathrm{idx}-1}|, -a_{\mathrm{idx}}, a_{\mathrm{idx}+1}, ..., a_n]$ for some $\mathrm{idx}$ where $a_{\mathrm{idx}}$ is initially positive. You can find the optimal choice of $\mathrm{idx}$ using prefix and suffix arrays. 198 199 To make all of the elements before $\mathrm{idx}$ positive, you can first make them all negative by applying the method in the easy version. Then at the end, you can perform an operation on $\mathrm{idx}$, yielding the optimal array. 200 201 **Code (easy version)** 202 203 ``` 204 #include<bits/stdc++.h> 205 using namespace std; 206 typedef long long ll; 207 #define debug(x) cout << #x << " = " << x << "\n"; 208 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 209 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 210 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 211 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 212 213 void solve(){ 214 int n; 215 cin >> n; 216 217 vector<int> a(n); 218 for (int &x : a) cin >> x; 219 220 int par = 0; 221 vector<int> ans; 222 for (int i = n - 1; i >= 0; i--){ 223 if (par == 1) 224 a[i] = -a[i]; 225 if (a[i] > 0){ 226 ans.push_back(i); 227 par ^= 1; 228 } 229 } 230 231 cout << ans.size() << "\n"; 232 for (int i = 0; i < ans.size(); i++) 233 cout << ans[i] + 1 << " \n"[i == ans.size() - 1]; 234 } 235 236 int main(){ 237 ios::sync_with_stdio(false); 238 cin.tie(0); 239 240 int t; 241 cin >> t; 242 while (t--) solve(); 243 } 244 ``` 245 246 **Code (hard version)** 247 248 ``` 249 #include<bits/stdc++.h> 250 using namespace std; 251 typedef long long ll; 252 #define debug(x) cout << #x << " = " << x << "\n"; 253 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 254 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 255 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 256 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 257 258 void solve(){ 259 int n; 260 cin >> n; 261 262 vector<int> a(n); 263 for (int &x : a) cin >> x; 264 265 vector<ll> pre(n), suf(n + 1); 266 pre[0] = abs(a[0]); 267 for (int i = 1; i < n; i++) 268 pre[i] = pre[i - 1] + abs(a[i]); 269 270 suf[n - 1] = a[n - 1]; 271 for (int i = n - 2; i >= 0; i--) 272 suf[i] = suf[i + 1] + a[i]; 273 274 ll best = suf[0]; 275 int idx = -1; 276 for (int i = 1; i < n; i++){ 277 if (a[i] > 0){ 278 ll score = pre[i - 1] + suf[i + 1] - a[i]; 279 if (score > best){ 280 best = score; 281 idx = i; 282 } 283 } 284 } 285 286 if (idx == -1){ 287 cout << "0\n"; 288 return; 289 } 290 291 vector<int> ans; 292 for (int i = idx - 1; i >= 0; i--){ 293 if (ans.size() & 1) 294 a[i] = -a[i]; 295 if (a[i] > 0) 296 ans.push_back(i); 297 } 298 ans.push_back(idx); 299 300 cout << ans.size() << "\n"; 301 for (int i = 0; i < ans.size(); i++) 302 cout << ans[i] + 1 << " \n"[i == ans.size() - 1]; 303 } 304 305 int main(){ 306 ios::sync_with_stdio(false); 307 cin.tie(0); 308 309 int t; 310 cin >> t; 311 while (t--) solve(); 312 } 313 ``` 314 315 **Rate the problem! (easy version)** 316 317 **Quality** 318 319 * Excellent problem 320 * Good problem 321 * Average problem 322 * Bad problem 323 * Horrible problem 324 325 **Difficulty** 326 327 * Trivial problem 328 * Easy problem 329 * Average problem 330 * Hard problem 331 * Impossible problem 332 333 **Rate the problem! (hard version)** 334 335 **Quality** 336 337 * Excellent problem 338 * Good problem 339 * Average problem 340 * Bad problem 341 * Horrible problem 342 343 **Difficulty** 344 345 * Trivial problem 346 * Easy problem 347 * Average problem 348 * Hard problem 349 * Impossible problem 350 351 [2229D - Я, когда задача на медиану](/contest/2229/problem/D) 352 353 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 354 355 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 356 357 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan") 358 359 **Hint 1** 360 361 Try solving the problem on a binary array; that is, all values of $a$ and $b$ are either $0$ or $1$. 362 363 **Hint 2** 364 365 Suppose you want to check if it is possible to achieve a final value of at least $m$. Then you can replace all smaller values with $0$, and all values at least $m$ with $1$. Now, solve the problem on the resulting binary array and check if it is possible to achieve a final value of $1$. 366 367 **Hint 3** 368 369 This allows you to binary search for the final answer. 370 371 **Solution** 372 373 Read the hints. It now suffices to solve the problem on a binary array. Let $\mathrm{diff} = \mathrm{cnt}_1 - \mathrm{cnt}_0$. Whenever you apply an operation, you lose the minimum and maximum of $S$. Therefore, the only way to change the value of $\mathrm{diff}$ is to apply an operation where the minimum and maximum of $S$ are the same; that is, all four values in $S$ are the same. If they are $0$, then $\mathrm{diff}$ increases by $2$; if they are $1$, then $\mathrm{diff}$ decreases by $2$. We want to increase $\mathrm{diff}$ as much as possible; if we can make it positive in the end, then that implies the final two values are both $1$. 374 375 Consider a subarray of indices such that there are no occurrences of ${a_i, b_i} = {1, 1}$; that is, we only have either ${a_i, b_i} = {0, 0}$ or ${a_i, b_i} = {0, 1}$. Then we want to repeatedly perform operations within this subarray, because this will maximize the number of times we can increase $\mathrm{diff}$. Note that an operation using ${0, 0}$ and ${0, 1}$ will produce a ${0, 0}$, so we will never lose an opportunity to increase $\mathrm{diff}$; we can apply operations within this subarray arbitrarily. Once we have applied as many operations as possible in this subarray, we are left with one pair, which is ${0, 0}$ if the subarray started with a ${0, 0}$, or ${0, 1}$ otherwise. 376 377 Now, it is impossible to increase $\mathrm{diff}$ any further. This is because any two pairs of ${0, 0}$ have a ${1, 1}$ in between. Clearly, if $\mathrm{diff}$ is nonpositive, then we have already lost. If $\mathrm{diff}$ is positive, we claim we win. Indeed, if there exists any ${0, 0}$ or ${0, 1}$, we can perform any operation with it, thus avoiding decreasing $\mathrm{diff}$. Otherwise, if all pairs are equal to ${1, 1}$, then we win trivially. This concludes the solution. 378 379 **Code** 380 381 ``` 382 #include<bits/stdc++.h> 383 using namespace std; 384 typedef long long ll; 385 #define debug(x) cout << #x << " = " << x << "\n"; 386 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 387 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 388 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 389 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 390 391 void solve(){ 392 int n; 393 cin >> n; 394 395 vector<int> a(n), b(n); 396 for (int &x : a) cin >> x; 397 for (int &x : b) cin >> x; 398 399 int l = 0, r = 1e9 + 5; 400 while (l < r){ 401 int mid = (l + r) / 2; 402 403 int one = 0, zero = 0; 404 int prev = -1; 405 for (int i = 0; i < n; i++){ 406 int type = 0; 407 if (a[i] >= mid) 408 type++; 409 if (b[i] >= mid) 410 type++; 411 412 if (type == 1) 413 continue; 414 415 if (type == 2){ 416 one++; 417 prev = 1; 418 } 419 420 if (type == 0){ 421 if (prev != 0) 422 zero++; 423 prev = 0; 424 } 425 } 426 427 if (one > zero) 428 l = mid + 1; 429 else 430 r = mid; 431 } 432 433 cout << l - 1 << "\n"; 434 } 435 436 int main(){ 437 ios::sync_with_stdio(false); 438 cin.tie(0); 439 440 int t; 441 cin >> t; 442 while (t--) solve(); 443 } 444 ``` 445 446 **Rate the problem!** 447 448 **Quality** 449 450 * Excellent problem 451 * Good problem 452 * Average problem 453 * Bad problem 454 * Horrible problem 455 456 **Difficulty** 457 458 * Trivial problem 459 * Easy problem 460 * Average problem 461 * Hard problem 462 * Impossible problem 463 464 [2229E - Дерево деструкции](/contest/2229/problem/E) 465 466 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 467 468 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 469 470 Editorial by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 471 472 **Hint 1** 473 474 $n$ will never be removed, and will always be added to $S$. 475 476 **Hint 2** 477 478 Try rooting at $n$. 479 480 **Solution** 481 482 Read the hints, through this editorial I will consider $n$ to be the root of the tree. 483 484 Lets try to determine the following for each node. When we add $x$ to $S$ for the first time, what can the largest element of $S$ be before this point. Lets try to find some necessary conditions for this. 485 486 * $\max(S) \lt x$, this is true because the maximum leaf is non-decreasing. 487 * $\max(S)$ is greater than the largest element in the subtree of $x$ (excluding $x$ itself). Since $n$ can never be removed, in order for $x$ to become a leaf, we must first remove everything in its subtree. For this to happen there must be some leaf outside the subtree of $x$ which is bigger than each element of the subtree. During this process a greater element will be added to $S$. 488 489 $\text{subtree}(x)$ will be used to denote the subtree of $x$ excluding $x$ itself. Remember that we rooted the tree at $n$. 490 491 It turns out that these conditions are also sufficient. i.e. if $\max(\text{subtree}(x)) \lt \max(S) \lt x$, then we are able to add $x$ into $S$ without needing to include any additional elements ($S := S \cup \lbrace x \rbrace$). We can prove that this is true because if the current largest leaf is larger than $\max(\text{subtree}(x))$, then we are able to remove the entire subtree of $x$ without changing the maximum. $x$ now becomes a leaf and because $\max(S) \lt x$, $x$ will be the new maximum and added on the next turn. 492 493 Thus we can solve this problem with dynamic programming where $dp_i$ is the number of ways to reach a state where $\max(S) = i$. The initial state has only the max leaf set to $1$. 494 495 $dp_i$ can transition to $dp_j$ if and only if $\max(\text{subtree}(j)) \lt i \lt j$. These transitions conveniently form ranges, so we can simulate all the transitions using prefix sums in $O(n)$. 496 497 It should be note that transitions to $n$ are a special case, a node $x$ can transition to $n$ if and only if we can delete all children of $n$ excluding the one with $x$ in its subtree. In other words all nodes outside the subtree that contains $x$ are smaller than it. 498 499 **Code** 500 501 ``` 502 #include<bits/stdc++.h> 503 using namespace std; 504 typedef long long ll; 505 #define debug(x) cout << #x << " = " << x << "\n"; 506 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 507 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 508 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 509 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 510 511 const int MOD = 998244353; 512 513 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 514 struct modnum { 515 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 516 517 using S = conditional_t<is_big_mod, ll, int>; 518 using L = conditional_t<is_big_mod, __int128, ll>; 519 520 S x; 521 522 modnum() : x(0) {} 523 modnum(ll _x) { 524 _x %= static_cast<ll>(mod); 525 if (_x < 0) { _x += mod; } 526 x = _x; 527 } 528 529 modnum pow(ll n) const { 530 modnum res = 1; 531 modnum cur = *this; 532 while (n > 0) { 533 if (n & 1) res *= cur; 534 cur *= cur; 535 n /= 2; 536 } 537 return res; 538 } 539 modnum inv() const { return (*this).pow(mod-2); } 540 541 modnum& operator+=(const modnum& a){ 542 x += a.x; 543 if (x >= mod) x -= mod; 544 return *this; 545 } 546 modnum& operator-=(const modnum& a){ 547 if (x < a.x) x += mod; 548 x -= a.x; 549 return *this; 550 } 551 modnum& operator*=(const modnum& a){ 552 x = static_cast<L>(x) * a.x % mod; 553 return *this; 554 } 555 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 556 557 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 558 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 559 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 560 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 561 562 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 563 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 564 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 565 566 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 567 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 568 }; 569 570 using mint = modnum<MOD>; 571 572 void solve(){ 573 int n; 574 cin >> n; 575 576 vector<vector<int>> g(n); 577 for (int i = 0; i < n - 1; i++){ 578 int u, v; 579 cin >> u >> v; 580 u--; 581 v--; 582 583 g[u].push_back(v); 584 g[v].push_back(u); 585 } 586 587 if (g[n - 1].size() == 1){ 588 cout << "1\n"; 589 return; 590 } 591 592 vector<int> mx(n); 593 auto dfs = [&](auto self, int c, int p) -> void{ 594 for (int x : g[c]){ 595 if (x == p) 596 continue; 597 598 self(self, x, c); 599 mx[c] = max({mx[c], x, mx[x]}); 600 } 601 }; 602 dfs(dfs, n - 1, -1); 603 604 set<int, greater<int>> s; 605 for (int i = 0; i < n - 1; i++) 606 s.insert(i); 607 608 vector<int> cur; 609 auto dfs2 = [&](auto self, int c, int p) -> void{ 610 s.erase(c); 611 cur.push_back(c); 612 613 for (int x : g[c]){ 614 if (x == p) 615 continue; 616 617 self(self, x, c); 618 } 619 }; 620 621 vector<bool> ok(n); // can transition to n 622 for (int x : g[n - 1]){ 623 dfs2(dfs2, x, n - 1); 624 625 for (int u : cur){ 626 if (u > (*s.begin())) 627 ok[u] = true; 628 } 629 630 for (int u : cur) 631 s.insert(u); 632 cur.clear(); 633 } 634 ok[n - 1] = true; 635 636 int idx = -1; 637 for (int i = 0; i < n; i++){ 638 if (g[i].size() == 1) 639 idx = i; 640 } 641 642 vector<mint> dp(n), pre(n); 643 dp[idx] = 1; 644 pre[idx] = 1; 645 for (int i = idx + 1; i < n - 1; i++){ 646 int l = mx[i] + 1; 647 648 if (l < i){ 649 dp[i] = pre[i - 1]; 650 if (l > 0) 651 dp[i] -= pre[l - 1]; 652 } 653 654 pre[i] = dp[i] + pre[i - 1]; 655 } 656 657 mint ans = 0; 658 for (int i = 0; i < n; i++){ 659 if (ok[i]) 660 ans += dp[i]; 661 } 662 663 cout << ans << "\n"; 664 } 665 666 int main(){ 667 ios::sync_with_stdio(false); 668 cin.tie(0); 669 670 int t; 671 cin >> t; 672 while (t--) solve(); 673 } 674 ``` 675 676 **Rate the problem!** 677 678 **Quality** 679 680 * Excellent problem 681 * Good problem 682 * Average problem 683 * Bad problem 684 * Horrible problem 685 686 **Difficulty** 687 688 * Trivial problem 689 * Easy problem 690 * Average problem 691 * Hard problem 692 * Impossible problem 693 694 [2229F - Дисбаланс нагрузки](/contest/2229/problem/F) 695 696 Idea by: [myst-6](/profile/myst-6 "Мастер myst-6") 697 698 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 699 700 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 701 702 **Hint 1** 703 704 Which element of $a$ is it optimal to use last? 705 706 **Hint 2** 707 708 Suppose you know which element you're placing last. Now what does the problem reduce to? 709 710 **Hint 3** 711 712 Binary search is your friend. 713 714 **Solution** 715 716 We will prove that it's optimal to place the maximum value of $a$ last in the array. After we've done that, the problem now becomes maximising the minimum value of $b$ after rearranging the rest of the values in $a$. 717 718 To maximise the minimum value of $b$, we can binary search it. To check whether it's $\le v$, we can do a bitmask DP which finds the maximum number of disjoint subsets of $a$ whose sum is $\ge v$, and check whether we have at least $k$ of them. There exists a simple greedy algorithm, once we have these subsets, to construct an ordering which gets us the value of v: we assign each subset to a position in array $b$, and simulate the process; whenever an index is chosen to be added to, we choose the highest remaining number from the corresponding subset. 719 720 We can make the bitmask dp in the form dp[mask] = maximum {number of groups, leftover}. There are $O(n)$ transitions from each mask (adding each possible extra element to the mask), so it runs in $O(2^n \cdot n)$. Since the difference between min and max in $b$ is at most $max(a)$, we can find an upper and lower bound for the binary search which are A apart, so time complexity ends up being $O(n \cdot 2^n \cdot log(A))$. 721 722 We can use this greedy algorithm to prove that $max(a)$ can always be placed last (let's call it $x$). Suppose we have an optimal rearrangement with $x$ not being last, and let's consider the set of values which go in each position in array $b$. Consider the last item added to the maximum pile (let's call it $y$) and the pile where $x$ was added. If we remove $y$ from its pile, its pile is now $min(b)$. If we remove $x$ from its pile and add $y$ to it, there are two cases: 1. $y$'s original pile is still the min. Greedily construct this min and add $x$ last, and $pile = ans - y + x \ge ans$ so it's a maximal construction. 2. $x$'s original pile is now the min. Greedily construct this min and add $x$ last, and $pile \ge ans - y - x + y + x = ans$ so it's a maximal construction. 723 724 **Code** 725 726 ``` 727 #include <bits/stdc++.h> 728 using namespace std; 729 730 typedef long long ll; 731 #define all(x) x.begin(), x.end() 732 #define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _; 733 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 734 735 void solve() { 736 int n, k; cin >> n >> k; 737 vecin(aa, n); sort(all(aa)); 738 n --; 739 ll extra = aa.back(); aa.pop_back(); 740 741 ll L = 0, R = extra * (ll)n; 742 while (L != R) { 743 ll mid = (L + R + 1) / 2; 744 vector<pair<int, ll>> dp(1 << n, {0, 0}); 745 for (int i = 1; i < (1 << n); i ++) { 746 for (int j = 0; (1 << j) <= i; j ++) { 747 if (!(i & (1 << j))) continue; 748 int res = i ^ (1 << j); 749 pair<int, ll> cur = dp[res]; 750 cur.second += aa[j]; 751 if (cur.second >= mid) 752 cur = {cur.first + 1, 0}; 753 dp[i] = max(dp[i], cur); 754 } 755 } 756 if (dp[(1 << n) - 1].first >= k) 757 L = mid; 758 else 759 R = mid - 1; 760 } 761 cout << L + extra << endl; 762 } 763 764 int main() { 765 ios_base::sync_with_stdio(false); 766 cin.tie(NULL); 767 int tt = 1; 768 769 cin >> tt; 770 771 while (tt--) solve(); 772 return 0; 773 } 774 ``` 775 776 **Rate the problem!** 777 778 **Quality** 779 780 * Excellent problem 781 * Good problem 782 * Average problem 783 * Bad problem 784 * Horrible problem 785 786 **Difficulty** 787 788 * Trivial problem 789 * Easy problem 790 * Average problem 791 * Hard problem 792 * Impossible problem 793 794 [2229G - Дорожные работы](/contest/2229/problem/G) 795 796 Idea by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 797 798 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 799 800 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 801 802 Special thanks to [Geothermal](/profile/Geothermal "Легендарный гроссмейстер Geothermal") for the absolute cinema solution! 803 804 **Hint 1** 805 806 When is it optimal to stay at a house for more than $1$ day? 807 808 **Hint 2** 809 810 Suppose you are staying at a house for more than $1$ day. When should you arrive at that house? 811 812 **Hint 3** 813 814 Suppose you are staying at a house for more than $1$ day. Which houses could you previously have come from? 815 816 **Main Ideas** 817 818 First, observe that any house you stay at for longer than $1$ day should be a prefix maximum on the path from house $x$, otherwise it's at least as good to stay on the previous house with greater $h_i$ on the path from house $x$. 819 820 Also, if you are going to stay at a house for longer than $1$ day, it is optimal to reach it as early as possible. Assume you stay at it for longer than 1 day but also don't reach it as early as possible: if the previous house you stayed at for longer than $1$ day had greater or equal hospitality you could have stayed there instead for an extra day and it would not be worse, and if it had lower hospitality you should have reached the new house earlier. 821 822 Finally, if you are going to switch directions in an optimal solution, you should go all the way past house $x$ before switching directions again. This is because if you switch directions at a house that is not a prefix maximum, it would have been better to just stay at the last prefix maximum for longer; and if you switch directions at a prefix maximum, but don't immediately go all the way past $x$, you should have stayed at that prefix maximum for longer. 823 824 **Solution (Boring)** 825 826 We can maintain for each house the maximum possible satisfaction we can achieve if we reach it as early as possible. We know that for each house, the optimal answer if we finish on that house at time $y$ depends only on the house with the next largest $h_i$ on the path to $x$, and the maximum answer for having previously stayed on the other side of $x$ then gone straight to that house. 827 828 For the former case, we can maintain which house is the prefix maximum on both sides, and for the latter case, we can use convex hull trick or LCT to keep track of the best satisfaction if we arrive on house $x$ at exactly time $y$ from either side. We use two pointers for the leftmost and rightmost currently reachable houses and update whenever a new prefix maximum becomes reachable. We also need prefix sums to track the increase in satisfaction of any houses we pass on the path to the next prefix maximum. You also need to be careful to not immediately insert a new house into the CHT/LCT, but only as soon as the next prefix maximum on the other side can actually reach it. The implementation is a bit horrible and the time complexity is $O(n log n)$, although it can also be implemented in $O(n)$. 829 830 **Hint 4** 831 832 Suppose you are staying at a house for more than $1$ day. Which houses could you go to next? 833 834 **Solution (Absolute Cinema)** 835 836 The boring solution uses a "pull DP". What if instead we used a "push DP"? In fact, we can show that whenever you reach a prefix maximum, the next house you will move to is either the next higher prefix maximum on that side of $x$, or the next highest prefix maximum on the other side of $x$. So we can precalculate both those things using a monotonic stack, and perform the transitions to both those houses (if they exist), assuming we reach them as early as possible. This is easy to implement in $O(n)$. 837 838  839 840 **Code (Boring Solution)** 841 842 ``` 843 #include <bits/stdc++.h> 844 using namespace std; 845 846 typedef long long ll; 847 #define all(x) x.begin(), x.end() 848 #define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _; 849 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 850 851 struct Line { 852 mutable ll k, m, p; 853 bool operator<(const Line& o) const { return k < o.k; } 854 bool operator<(ll x) const { return p < x; } 855 ll eval(ll x) { return k * x + m; } 856 }; 857 858 struct LineContainer : multiset<Line, less<>> { 859 static const ll inf = LLONG_MAX; 860 ll div(ll a, ll b) { 861 return a / b - ((a ^ b) < 0 && a % b); } 862 bool isect(iterator x, iterator y) { 863 if (y == end()) return x->p = inf, 0; 864 if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; 865 else x->p = div(y->m - x->m, x->k - y->k); 866 return x->p >= y->p; 867 } 868 void add(ll k, ll m) { 869 auto z = insert({k, m, 0}), y = z++, x = y; 870 while (isect(y, z)) z = erase(z); 871 if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); 872 while ((y = x) != begin() && (--x)->p >= y->p) 873 isect(x, erase(y)); 874 } 875 ll query(ll x) { 876 assert(!empty()); 877 auto l = *lower_bound(x); 878 return l.eval(x); 879 } 880 }; 881 882 vector<ll> h; 883 vector<ll> pref; 884 885 ll range_sum(int L, int R) { 886 return pref[R + 1] - pref[L]; 887 } 888 889 void solve() { 890 int n, t, x; cin >> n >> t >> x; 891 x --; 892 h.resize(n); pref.resize(n + 1); 893 pref[0] = 0; 894 for (int i = 0; i < n; i ++) { 895 cin >> h[i]; 896 pref[i + 1] = pref[i] + h[i]; 897 } 898 vecin(d, n - 1); 899 for (int i = x - 2; i >= 0; i --) { 900 d[i] = max(d[i], d[i + 1] + 1); 901 } 902 for (int i = x; i < n - 2; i ++) { 903 d[i + 1] = max(d[i + 1], d[i] + 1); 904 } 905 906 ll ans = h[x] * t; 907 int L = x, R = x; 908 Line curleft = {h[x], 0, 0}, curright = {h[x], 0, 0}; 909 int left_best = x, right_best = x; 910 LineContainer left, right; 911 left.add(h[x], 0); right.add(h[x], 0); 912 queue<pair<int, pair<ll, ll>>> add_left, add_right; 913 while (L > 0 || R < n - 1) { 914 int left_time = (L == 0) ? 2e9 : d[L - 1]; 915 int right_time = (R == n - 1) ? 2e9 : d[R]; 916 if (min(left_time, right_time) > t) break; 917 if (left_time <= right_time) { 918 L --; 919 if (h[L] > curleft.k) { 920 // best = max sum on day left_time-1 on house L+1 921 int pref_dist = left_best - L; 922 int start_dist = x - L; 923 while (add_right.size() && add_right.front().first <= left_time - start_dist) { 924 right.add(add_right.front().second.first, add_right.front().second.second); 925 add_right.pop(); 926 } 927 ll best = max( 928 curleft.eval(left_time - pref_dist) + range_sum(L + 1, left_best - 1), 929 right.query(left_time - start_dist) + range_sum(L + 1, x - 1) 930 ); 931 // cout << L << " " << h[L] << " " << best << endl; 932 ans = max(ans, best + (t - left_time + 1) * h[L]); 933 left_best = L; 934 curleft = {h[L], best - (left_time - 1) * h[L], 0}; 935 add_left.push({left_time + start_dist, {h[L], best - (left_time - 1 + start_dist) * h[L] + range_sum(L + 1, x)}}); 936 } 937 } else { 938 R ++; 939 if (h[R] > curright.k) { 940 // best = max sum on day right_time-1 on house R-1 941 int pref_dist = R - right_best; 942 int start_dist = R - x; 943 while (add_left.size() && add_left.front().first <= right_time - start_dist) { 944 left.add(add_left.front().second.first, add_left.front().second.second); 945 add_left.pop(); 946 } 947 ll best = max( 948 curright.eval(right_time - pref_dist) + range_sum(right_best + 1, R - 1), 949 left.query(right_time - start_dist) + range_sum(x + 1, R - 1) 950 ); 951 // cout << R << " " << h[R] << " " << best << endl; 952 ans = max(ans, best + (t - right_time + 1) * h[R]); 953 right_best = R; 954 curright = {h[R], best - (right_time - 1) * h[R], 0}; 955 add_right.push({right_time + start_dist, {h[R], best - (right_time - 1 + start_dist) * h[R] + range_sum(x, R - 1)}}); 956 } 957 } 958 } 959 cout << ans << endl; 960 } 961 962 int main() { 963 ios_base::sync_with_stdio(false); 964 cin.tie(NULL); 965 int tt = 1; 966 967 cin >> tt; 968 969 while (tt--) solve(); 970 return 0; 971 } 972 ``` 973 974 **Code (Absolute Cinema Solution)** 975 976 ``` 977 #include <bits/stdc++.h> 978 979 using namespace std; 980 981 using ll = long long; 982 using vi = vector<int>; 983 using vl = vector<ll>; 984 using pl = pair<ll, ll>; 985 template <class T> 986 using vc = vector<T>; 987 988 template <class T> 989 constexpr T infty = 0; 990 template <> 991 constexpr ll infty<ll> = 2'020'000'000'000'000'000; 992 993 #define FOR2(i, a) for (int i = 0; i < int(a); ++i) 994 #define FOR3(i, a, b) for (int i = int(a); i < int(b); ++i) 995 #define FOR2_R(i, a) for (int i = int(a) - 1; i >= 0; --i) 996 #define overload4(a, b, c, d, e, ...) e 997 #define overload3(a, b, c, d, ...) d 998 #define FOR(...) overload4(__VA_ARGS__, _4, FOR3, FOR2, _1)(__VA_ARGS__) 999 #define FOR_R(...) overload3(__VA_ARGS__, _3, FOR2_R, _1)(__VA_ARGS__) 1000 1001 #define all(x) (x).begin(), (x).end() 1002 #define trav(a, x) for (auto& a : x) 1003 #define eb emplace_back 1004 #define mp make_pair 1005 #define fi first 1006 #define se second 1007 1008 template <class T, class S> 1009 inline bool chmax(T &a, const S &b) { 1010 T c = max<T>(a, b); 1011 bool changed = (c != a); 1012 a = c; 1013 return changed; 1014 } 1015 1016 template <class T> 1017 void rd(T &x) { cin >> x; } 1018 1019 template <class T> 1020 void rd(vc<T> &x) { for (auto &d : x) rd(d); } 1021 1022 void read() {} 1023 template <class H, class... T> 1024 void read(H &h, T &...t) { rd(h), read(t...); } 1025 1026 void print() { cout << '\n'; } 1027 template <class Head, class... Tail> 1028 void print(Head &&head, Tail &&...tail) { 1029 cout << head; 1030 if (sizeof...(Tail)) cout << ' '; 1031 print(forward<Tail>(tail)...); 1032 } 1033 1034 #define INT(...) int __VA_ARGS__; read(__VA_ARGS__) 1035 #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__) 1036 #define VEC(type, name, size) vector<type> name(size); read(name) 1037 1038 1039 void solve() { 1040 INT(N); LL(tot); INT(X); 1041 X--; 1042 VEC(ll, A, N); 1043 VEC(ll, D, N-1); 1044 vl T(N); 1045 T[X] = 1; 1046 FOR(i, X, N-1) { 1047 T[i+1] = max(T[i]+1, D[i]); 1048 if (i == X && D[i] == 1) T[i+1] = 1; 1049 } 1050 FOR_R(i, X) { 1051 T[i] = max(T[i+1]+1, D[i]); 1052 if (i == X-1 && D[i] == 1) T[i] = 1; 1053 } 1054 vi nh(N), lh(N); 1055 vc<pl> stk; 1056 stk.eb(mp(N, 2e9)); 1057 FOR_R(i, N) { 1058 while (stk.back().se <= A[i]) stk.pop_back(); 1059 nh[i] = stk.back().fi; 1060 stk.eb(mp(i, A[i])); 1061 } 1062 stk.clear(); 1063 stk.eb(mp(-1, 2e9)); 1064 FOR(i, N) { 1065 while (stk.back().se <= A[i]) stk.pop_back(); 1066 lh[i] = stk.back().fi; 1067 stk.eb(mp(i, A[i])); 1068 } 1069 1070 ll dp[N]; 1071 FOR(i, N) { 1072 dp[i] = -infty<ll>; 1073 } 1074 FOR(i, N) dp[i] = 0; 1075 vc<pl> vals; FOR(i, N) vals.eb(mp(T[i], i)); 1076 sort(all(vals)); 1077 ll ans = 0; 1078 vl ps; ps.eb(0); 1079 FOR(i, N) ps.eb(ps.back()+A[i]); 1080 trav(xx, vals) { 1081 int i = xx.se; 1082 if (dp[i] < 0) continue; 1083 chmax(ans, (tot - T[i] + 1) * A[i] + dp[i]); 1084 vi ops = {nh[i], lh[i]}; 1085 trav(j, ops) { 1086 if (j < 0 || j >= N) continue; 1087 if (abs(j-i) > T[j] - T[i]) { 1088 continue; 1089 } 1090 chmax(dp[j], dp[i] + (T[j] - T[i] - abs(j-i) + 1) * A[i] + ps[max(i, j)] - ps[min(i, j) + 1]); 1091 } 1092 } 1093 1094 print(ans); 1095 } 1096 1097 signed main() { 1098 ios::sync_with_stdio(false); 1099 cin.tie(nullptr); 1100 INT(T); 1101 FOR(t, T) { 1102 solve(); 1103 } 1104 return 0; 1105 } 1106 ``` 1107 1108 **Rate the problem!** 1109 1110 **Quality** 1111 1112 * Excellent problem 1113 * Good problem 1114 * Average problem 1115 * Bad problem 1116 * Horrible problem 1117 1118 **Difficulty** 1119 1120 * Trivial problem 1121 * Easy problem 1122 * Average problem 1123 * Hard problem 1124 * Impossible problem 1125 1126 [2229H - Ух ты, бинарная строка](/contest/2229/problem/H) 1127 1128 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 1129 1130 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 1131 1132 Editorial by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent") 1133 1134 **Hint 1** 1135 1136 Imagine the string has no $\mathtt{?}$ characters, try to find a greedy which can check if a string $t$ can be generated from $s$ by applying the operation. 1137 1138 **Hint 2** 1139 1140 Try to generalise this greedy for when there are $\mathtt{?}$ characters. 1141 1142 **Solution** 1143 1144 Read the hints. A correct greedy for the no $\mathtt{?}$ character version is perhaps the simplest one you can try, which is as follows: 1145 1146 We would like to find a subsequence of $s$ which is equal to $t$, where each substring between consecutive characters contains an even number of $\mathtt{1}$. We can find this by iterating through the characters of $t$. For each character find the first character in $s$ where $s_j = t_i$ and the substring between $s_j$ and the previously chosen character contains an even number of $\mathtt{1}$. 1147 1148 We can prove correctness by contradiction. Say we have a matching where at some point we didn't chose the earliest match, say between $t_i$ and $t_{i + 1}$ (we matched with a later position for $t_{i + 1}$). We can adjust our matching to instead take the earliest position for $t_{i + 1}$, call this earliest position $x$. Since we know the substring from $t_i$ to $x$ is removable and the substring from $t_i$ to $t_{i + 1}$ is removable, we can deduce that the substring from $x$ to $t_{i + 1}$ is removable. Because $t_{i + 1}$ to $t_{i + 2}$ is removeable and $x$ to $t_{i + 1}$ is removable, we can deduce that $x$ to $t_{i + 2}$ will also be removable. Thus matching the earliest option is always optimal. 1149 1150 Now lets try to generalise this when there are $\mathtt{?}$ characters. Naïvely using the same greedy does not work, consider a case like $s = \mathtt{?10000000}$, $t = \mathtt{10000000}$. If we match the first $\mathtt{1}$ with the $\mathtt{?}$ we get stuck, instead we should set the $\mathtt{?}$ to $\mathtt{0}$ and match with the $\mathtt{1}$. 1151 1152 Let's analyse why we fail this counter case. It fails because we incorrectly assign the value of a $\mathtt{?}$, and in general this will always be why the greedy fails, since we already know this approach would be correct after replacing all $\mathtt{?}$. When we encounter a $\mathtt{?}$ during the greedy, our choice of replacement determines the parity of the count of $\mathtt{1}$ in the current suffix. If chose incorrectly we get "locked" on the incorrect parity and are forced to consume suboptimally. 1153 1154 To fix this problem, we can adjust our greedy to consider both parities at the same time. Instead of considering only the earliest match, we consider the earliest match for each parity. For each character $t_i$, we will compute the pair $(\text{best}_0, \text{best}_1)$, where $\text{best}_0$ is the earliest match with an even count of $1$ in the suffix and $\text{best}_1$ is the earliest match with an odd count of $1$ in the suffix (note that each $\mathtt{?}$ does not contribute to the suffix parity). When we transition we only need to consider the $4$ combinations of new parity and old parity. Now the entire string will be generatable if and only if the substring $s_{best_i + 1},s_{best_i + 2},\ldots,s_n$ is removable for at least one element of the final pair. 1155 1156 The proof for this greedy is similar to the naïve greedy in the no $\mathtt{?}$ version. However this time we prove that for any step, if we fix the parity of the new suffix, then taking the earliest choice is always optimal. And now since we always consider both suffix parities, we will always find a matching if one exists. 1157 1158 Now for counting, we can run dynamic programming on this greedy. Where $dp_{i, j}$ is the number of strings with ending greedy pair $(i, j)$, for transitions we only need to try appending $\mathtt{0}$ and $\mathtt{1}$ to the string. To fit the time limit of the problem, we need to be able to find transitions in $O(1)$. Because the problem allows $O(n^2)$ anyway, we can pre-calculate the earliest even and odd match for each position. This allows us to calculate the transitions for pairs in $O(1)$. 1159 1160 Thus, the final time complexity is $O(n^2)$. 1161 1162 **Code** 1163 1164 ``` 1165 #include<bits/stdc++.h> 1166 using namespace std; 1167 typedef long long ll; 1168 #define debug(x) cout << #x << " = " << x << "\n"; 1169 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 1170 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 1171 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 1172 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 1173 1174 const int MOD = 998244353; 1175 1176 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 1177 struct modnum { 1178 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 1179 1180 using S = conditional_t<is_big_mod, ll, int>; 1181 using L = conditional_t<is_big_mod, __int128, ll>; 1182 1183 S x; 1184 1185 modnum() : x(0) {} 1186 modnum(ll _x) { 1187 _x %= static_cast<ll>(mod); 1188 if (_x < 0) { _x += mod; } 1189 x = _x; 1190 } 1191 1192 modnum pow(ll n) const { 1193 modnum res = 1; 1194 modnum cur = *this; 1195 while (n > 0) { 1196 if (n & 1) res *= cur; 1197 cur *= cur; 1198 n /= 2; 1199 } 1200 return res; 1201 } 1202 modnum inv() const { return (*this).pow(mod-2); } 1203 1204 modnum& operator+=(const modnum& a){ 1205 x += a.x; 1206 if (x >= mod) x -= mod; 1207 return *this; 1208 } 1209 modnum& operator-=(const modnum& a){ 1210 if (x < a.x) x += mod; 1211 x -= a.x; 1212 return *this; 1213 } 1214 modnum& operator*=(const modnum& a){ 1215 x = static_cast<L>(x) * a.x % mod; 1216 return *this; 1217 } 1218 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 1219 1220 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 1221 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 1222 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 1223 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 1224 1225 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 1226 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 1227 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 1228 1229 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 1230 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 1231 }; 1232 1233 using mint = modnum<MOD>; 1234 1235 void solve(){ 1236 int n; 1237 cin >> n; 1238 1239 string s; 1240 cin >> s; 1241 1242 s = '0' + s; 1243 n++; 1244 1245 vector<int> pre(n); 1246 pre[0] = s[0] == '1'; 1247 for (int i = 1; i < n; i++){ 1248 pre[i] = pre[i - 1] + (s[i] == '1'); 1249 } 1250 1251 vector<array<array<int, 2>, 2>> to(n + 1); 1252 for (int i = 0; i <= n; i++){ 1253 to[i][0][0] = n; 1254 to[i][0][1] = n; 1255 to[i][1][0] = n; 1256 to[i][1][1] = n; 1257 1258 int cnt = 0; 1259 bool wowee = false; 1260 for (int j = i + 1; j < n; j++){ 1261 if ((cnt & 1) && !wowee){ 1262 if (s[j] == '1') 1263 cnt++; 1264 if (s[j] == '?') 1265 wowee = true; 1266 continue; 1267 } 1268 1269 if (s[j] == '1') 1270 cnt++; 1271 if (s[j] == '?') 1272 wowee = true; 1273 1274 int par = pre[j] & 1; 1275 if (s[j] == '?'){ 1276 to[i][0][par] = min(to[i][0][par], j); 1277 to[i][1][par] = min(to[i][1][par], j); 1278 continue; 1279 } 1280 1281 int omg = s[j] - '0'; 1282 to[i][omg][par] = min(to[i][omg][par], j); 1283 } 1284 } 1285 1286 vector<bool> good(n + 1); 1287 int cnt = 0; 1288 int wowee = false; 1289 for (int i = n - 1; i >= 0; i--){ 1290 good[i] = (cnt % 2 == 0) || wowee; 1291 if (s[i] == '1') 1292 cnt++; 1293 if (s[i] == '?') 1294 wowee = true; 1295 } 1296 1297 mint ans = 0; 1298 vector<vector<mint>> dp(n + 1, vector<mint>(n + 1)); 1299 dp[0][n] = 1; 1300 1301 vector<array<int, 2>> ord; 1302 for (int i = 0; i <= n; i++){ 1303 for (int j = i; j <= n; j++){ 1304 ord.push_back({i, j}); 1305 if (j != i) 1306 ord.push_back({j, i}); 1307 } 1308 } 1309 1310 for (auto [i, j] : ord){ 1311 for (int nxt = 0; nxt < 2; nxt++){ 1312 int even = min(to[i][nxt][0], to[j][nxt][0]); 1313 int odd = min(to[i][nxt][1], to[j][nxt][1]); 1314 dp[even][odd] += dp[i][j]; 1315 } 1316 1317 if (good[i] || good[j]) 1318 ans += dp[i][j]; 1319 } 1320 1321 cout << ans << "\n"; 1322 } 1323 1324 int main(){ 1325 ios::sync_with_stdio(false); 1326 cin.tie(0); 1327 1328 int t; 1329 cin >> t; 1330 while (t--) solve(); 1331 } 1332 ``` 1333 1334 **Rate the problem!** 1335 1336 **Quality** 1337 1338 * Excellent problem 1339 * Good problem 1340 * Average problem 1341 * Bad problem 1342 * Horrible problem 1343 1344 **Difficulty** 1345 1346 * Trivial problem 1347 * Easy problem 1348 * Average problem 1349 * Hard problem 1350 * Impossible problem 1351 1352 [2229I - Концы](/contest/2229/problem/I) 1353 1354 Idea by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 1355 1356 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 1357 1358 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri") 1359 1360 Special thanks to [p0tato](/profile/p0tato "Международный гроссмейстер p0tato") for the absolute cinema solution! 1361 1362 **Hint -1** 1363 1364 It's not convex, monotone, monge, FFT, centroid, or any other fancy trick like that. The solution is simpler than you might expect. 1365 1366 **Hint 0** 1367 1368 Reformulate the formula for score so that it's in terms of nodes in the subtree from root, not the path to the root. 1369 1370 **Hint 1** 1371 1372 Suppose you wanted to solve for a single root in $O(n^2)$. How would you do it? 1373 1374 **Answer** 1375 1376 Trick 7 from <https://codeforces.com/blog/entry/100910> is your friend. 1377 1378 **Hint 2** 1379 1380 Why is naive rerooting $O(n^3)$ on a tree like this? 1381 1382  1383 1384 **Hint 3** 1385 1386 How many DP values do you compute for the node labelled X? How many do you actually care about? 1387 1388 **Hint 4** 1389 1390 In general, how many DP values do you actually care about for a node? 1391 1392 **Main Idea** 1393 1394 Let: 1395 1396 * $dp_1[i][j]$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $i$, assuming the selected root is $i$ or an ancestor of $i$, which uses exactly $j$ nodes. 1397 * $dp_2[i][j]$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $i$ assuming the selected root is $i$ or an ancestor of $i$, which uses exactly $j$ nodes, and does not have node $i$ selected. 1398 * $dp_3[i][j]$ be the maximum score of a subset of nodes \textbf{outside} the subtree of node $i$, assuming the selected root is $i$ or in its subtree, which uses exactly $j$ nodes. 1399 1400 We can compute $dp_1$ and $dp_2$ using Trick 7 in $O(n^2)$. The tricky part is $dp_3$. The critical observation is that for each node $i$ with a subtree size of $sz(i)$, we only care about the $sz(i)$ largest values of $dp_3[i]$, that is: $dp_3[i][k - sz(i)], dp_3[i][k - sz(i) + 1], \ldots, dp3_[i][k - 1]$. This is because if we select fewer than $k - sz(i)$ nodes outside of the subtree of $i$, then we have selected fewer than $k$ nodes overall and the solution is not optimal. There are now two ways to continue. 1401 1402 **Solution (Boring)** 1403 1404 Let us compute $dp_3$ in a way similar to Trick 7. Initially we have $dp_3[0][j] = 0$ for all $j$ (since the root has no parents). 1405 1406 Suppose we are at a node $u$ with children $c_1, c_2, \ldots, c_m$ and we have already computed $dp_3[u]$. Let $pref[i][j]$ be the max score we can achieve by selecting $j$ nodes out of the subtrees of $c_1, \ldots, c_i$. And let $suf[i][j]$ be the max score we can achieve by selecting $j$ nodes out of the subtrees of $c_i, \ldots, c_m$ and nodes outside of the subtree of $u$. Then for each child we obtain the largest $sz(c_i0$ values of $dp_3[c_i]$ by merging $pref[i - 1]$ and $suf[i + 1]$. 1407 1408 Observe that we only need to compute $\Sigma_{j\le i}sz(c_i)$ values of $pref[i]$, and $\Sigma_{j\ge i}sz(c_i)$ values of $suf[i]$. So by the same argument as Trick 7 running in $O(n^2)$, this DP also runs in $O(n^2)$. 1409 1410 All that remains is to add the contribution of node $u$ to each of its child values with $dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$. Then the answer for each root is $max(dp_2[x][j] + dp_3[x][k - 1 - j] + k \cdot w[i])$. 1411 1412 **Solution (Absolute Cinema)** 1413 1414 Suppose the tree is a binary tree. Then, for a node $u$ with children $c_1, c_2$, we can just naively merge $dp_1[c_2]$ and $dp_3[u]$ to get $dp_3[c_1]$, and merge $dp_1[c_1]$ and $dp_3[u]$ to get $dp_3[c_2]$ (then add the contribution of $u$ with $dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$). And this magically runs in $O(n^2)$, because both the convolutions run in $sz(c_1) \cdot sz(c_2)$, and the sum across all nodes of $sz(c_1) \cdot sz(c_2)$ exactly corresponds to each pair of nodes once. 1415 1416 What if the tree is not a binary tree? We can make it one! If a node $u$ has $m$ children, add $m-3$ dummy nodes $d_1, d_2, \ldots, d_{m-3}$ in a chain and connect the children to them like this: 1417 1418  1419 1420 The only thing to watch out for is that the contribution of the original node $u$ must be done for each original child, not for the dummy nodes. The number of nodes is still $O(n)$ so it runs in $O(n^2)$. 1421 1422  1423 1424 **Code (Boring Solution)** 1425 1426 ``` 1427 #include <bits/stdc++.h> 1428 using namespace std; 1429 1430 typedef long long ll; 1431 #define all(x) x.begin(), x.end() 1432 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 1433 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 1434 1435 const int MAXN = 4005; 1436 1437 ll dp_down[MAXN][MAXN], dp_down_take[MAXN][MAXN], dp_up[MAXN][MAXN]; 1438 ll pref_merge[MAXN][MAXN], suff_merge[MAXN][MAXN]; 1439 vector<int> adj[MAXN]; 1440 vector<int> children[MAXN]; 1441 ll weight[MAXN]; 1442 int sz[MAXN]; 1443 int n, k; 1444 1445 void dfs1(int node, int parent) { 1446 sz[node] = 1; 1447 for (auto a : adj[node]) 1448 if (a != parent) { 1449 children[node].push_back(a); 1450 dfs1(a, node); 1451 for (int i = min(sz[node] - 1, k); i >= 0; i --) 1452 for (int j = 1; j <= sz[a] && i + j <= k; j ++) 1453 dp_down[node][i + j] = max(dp_down[node][i + j], dp_down[node][i] + dp_down_take[a][j]); 1454 sz[node] += sz[a]; 1455 } 1456 for (int i = min(k, sz[node]); i > 0; i --) 1457 dp_down_take[node][i] = max(dp_down[node][i], dp_down[node][i - 1] + (ll)i * weight[node]); 1458 } 1459 1460 void dfs2(int node) { 1461 int deg = children[node].size(); 1462 if (deg == 1) { 1463 for (int i = 0; i <= k; i ++) 1464 dp_up[children[node][0]][i] = dp_up[node][i]; 1465 } else if (deg >= 2) { 1466 int p = sz[children[node][0]]; 1467 for (int i = 0; i <= k; i ++) 1468 pref_merge[0][i] = dp_down_take[children[node][0]][i], 1469 suff_merge[deg][i] = dp_up[node][i]; 1470 for (int c = 1; c < deg; c ++) { 1471 for (int i = 0; i <= k; i ++) 1472 pref_merge[c][i] = 0; 1473 int child = children[node][c]; 1474 p += sz[child]; 1475 for (int i = min(k, p); i >= 0; i --) 1476 for (int j = min(i, sz[child]); j >= 0 && i - j <= p - sz[child]; j --) 1477 pref_merge[c][i] = max(pref_merge[c][i], pref_merge[c - 1][i - j] + dp_down_take[child][j]); 1478 } 1479 for (int c = deg - 1; c >= 0; c --) { 1480 for (int i = 0; i <= k; i ++) 1481 suff_merge[c][i] = 0; 1482 int child = children[node][c]; 1483 p -= sz[child]; 1484 for (int i = k; i >= max(0, k - p - 1); i --) 1485 for (int j = min(i, sz[child]); j >= 0; j --) 1486 suff_merge[c][i] = max(suff_merge[c][i], suff_merge[c + 1][i - j] + dp_down_take[child][j]); 1487 for (int i = k; i >= max(0, k - sz[child] - 1); i --) 1488 for (int j = min(i, p); j >= 0; j --) 1489 dp_up[child][i] = max(dp_up[child][i], suff_merge[c + 1][i - j] + (c > 0 ? pref_merge[c - 1][j] : 0)); 1490 } 1491 } 1492 for (auto a : children[node]) { 1493 for (int i = min(k, n - sz[a]); i >= 1; i --) 1494 dp_up[a][i] = max(dp_up[a][i], dp_up[a][i - 1] + (ll)i * weight[node]); 1495 dfs2(a); 1496 } 1497 } 1498 1499 void solve() { 1500 cin >> n >> k; 1501 for (int i = 0; i < n; i ++) { 1502 for (int j = 0; j <= k; j ++) 1503 dp_down[i][j] = dp_down_take[i][j] = dp_up[i][j] = 0; 1504 adj[i].clear(); children[i].clear(); 1505 cin >> weight[i]; 1506 } 1507 for (int i = 0; i < n - 1; i ++) { 1508 int a, b; cin >> a >> b; 1509 a --; b --; 1510 adj[a].push_back(b); 1511 adj[b].push_back(a); 1512 } 1513 dfs1(0, -1); 1514 dfs2(0); 1515 for (int i = 0; i < n; i ++) { 1516 ll best = 0; 1517 for (int j = 0; j < min(k, sz[i]); j ++) 1518 best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * weight[i]); 1519 cout << best << " "; 1520 } 1521 cout << endl; 1522 } 1523 1524 int main() { 1525 ios_base::sync_with_stdio(false); 1526 cin.tie(NULL); 1527 int tt = 1; 1528 1529 cin >> tt; 1530 1531 while (tt--) solve(); 1532 return 0; 1533 } 1534 ``` 1535 1536 **Code (Absolute Cinema Solution)** 1537 1538 ``` 1539 #include <bits/stdc++.h> 1540 using namespace std; 1541 1542 typedef long long ll; 1543 #define all(x) x.begin(), x.end() 1544 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 1545 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 1546 1547 const int MAXN = 4005; 1548 int n, k; 1549 int spare; 1550 vector<int> adj[MAXN], children[2 * MAXN]; 1551 ll beauty[2 * MAXN]; 1552 int sz[2 * MAXN]; 1553 ll dp_down[2 * MAXN][MAXN], dp_down_take[2 * MAXN][MAXN]; 1554 ll dp_up[2 * MAXN][MAXN]; 1555 1556 void merge(ll *target, ll *aa, ll *bb, int tsize, int asize, int bsize, int topmost) { 1557 for (int i = tsize; i > max(0, tsize - topmost); i --) 1558 for (int j = 0; j <= min(min(asize, bsize), i); j ++) 1559 target[i] = max(target[i], asize >= bsize ? aa[i - j] + bb[j] : bb[i - j] + aa[j]); 1560 } 1561 void finalise(ll *target, ll *source, ll b, int tsize) { 1562 for (int i = tsize; i > 0; i --) 1563 target[i] = max(source[i], source[i - 1] + (ll)i * b); 1564 } 1565 1566 void dfs1(int node, int parent) { 1567 vector<int> cc; 1568 for (auto a : adj[node]) 1569 if (a != parent) { 1570 dfs1(a, node); 1571 cc.push_back(a); 1572 } 1573 int cur = node; 1574 while (cc.size() > 2) { 1575 children[cur] = {cc.back(), spare}; 1576 cc.pop_back(); 1577 beauty[spare] = beauty[node]; 1578 cur = spare ++; 1579 } 1580 children[cur] = cc; 1581 } 1582 1583 void dfs2(int node) { 1584 sz[node] = (node < n); 1585 for (auto a : children[node]) { 1586 dfs2(a); 1587 sz[node] += sz[a]; 1588 } 1589 if (children[node].size() == 1) { 1590 for (int i = 0; i <= k; i ++) 1591 dp_down[node][i] = dp_down_take[children[node][0]][i]; 1592 } else if (children[node].size() == 2) { 1593 merge(dp_down[node], dp_down_take[children[node][0]], dp_down_take[children[node][1]], min(k, sz[node] - (node < n)), sz[children[node][0]], sz[children[node][1]], sz[node] - (node < n)); 1594 } 1595 finalise(dp_down_take[node], dp_down[node], node < n ? beauty[node] : 0, min(k, sz[node])); 1596 } 1597 1598 void dfs3(int node) { 1599 if (children[node].size() == 1) { 1600 finalise(dp_up[children[node][0]], dp_up[node], beauty[node], min(k, n - sz[children[node][0]])); 1601 } else if (children[node].size() == 2) { 1602 int aa = children[node][0], bb = children[node][1]; 1603 merge(dp_up[aa], dp_up[node], dp_down_take[bb], min(n - sz[aa], k), min(n - sz[node], k), min(sz[bb], k), min(sz[aa] + 2, k)); 1604 merge(dp_up[bb], dp_up[node], dp_down_take[aa], min(n - sz[bb], k), min(n - sz[node], k), min(sz[aa], k), min(sz[bb] + 2, k)); 1605 if (aa < n) 1606 finalise(dp_up[aa], dp_up[aa], beauty[node], min(n - sz[aa], k)); 1607 if (bb < n) 1608 finalise(dp_up[bb], dp_up[bb], beauty[node], min(n - sz[bb], k)); 1609 } 1610 for (auto a : children[node]) 1611 dfs3(a); 1612 } 1613 1614 void solve() { 1615 cin >> n >> k; 1616 for (int i = 0; i < n; i ++) 1617 adj[i].clear(), children[i].clear(); 1618 for (int i = n; i < 2 * n; i ++) 1619 children[i].clear(); 1620 spare = n; 1621 for (int i = 0; i < n; i ++) 1622 cin >> beauty[i]; 1623 for (int i = 0; i < n - 1; i ++) { 1624 int a, b; cin >> a >> b; 1625 a --; b --; 1626 adj[a].push_back(b); 1627 adj[b].push_back(a); 1628 } 1629 dfs1(0, -1); 1630 for (int i = 0; i < spare; i ++) 1631 for (int j = 0; j <= k; j ++) 1632 dp_down[i][j] = dp_up[i][j] = dp_down_take[i][j] = 0; 1633 dfs2(0); 1634 dfs3(0); 1635 for (int i = 0; i < n; i ++) { 1636 ll best = 0; 1637 for (int j = 0; j < min(k, sz[i]); j ++) 1638 best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * beauty[i]); 1639 cout << best << " "; 1640 } 1641 cout << endl; 1642 } 1643 1644 int main() { 1645 ios_base::sync_with_stdio(false); 1646 cin.tie(NULL); 1647 int tt = 1; 1648 1649 cin >> tt; 1650 1651 while (tt--) solve(); 1652 return 0; 1653 } 1654 ``` 1655 1656 **Rate the problem!** 1657 1658 **Quality** 1659 1660 * Excellent problem 1661 * Good problem 1662 * Average problem 1663 * Bad problem 1664 * Horrible problem 1665 1666 **Difficulty** 1667 1668 * Trivial problem 1669 * Easy problem 1670 * Average problem 1671 * Hard problem 1672 * Impossible problem