1437.md (13492B)
1 Source: https://codeforces.com/blog/entry/84149 2 3 [1437A - Marketing Scheme](/contest/1437/problem/A "Educational Codeforces Round 97 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main() { 15 repeat(readLine()!!.toInt()) { 16 val (l, r) = readLine()!!.split(' ').map { it.toInt() } 17 println(if (2 * l > r) "YES" else "NO"); 18 } 19 } 20 ``` 21 22 [1437B - Reverse Binary Strings](/contest/1437/problem/B "Educational Codeforces Round 97 (Rated for Div. 2)") 23 24 Idea: [adedalic](/profile/adedalic "International Master adedalic") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (adedalic)** 31 32 ``` 33 #include<bits/stdc++.h> 34 35 using namespace std; 36 37 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 38 #define sz(a) int((a).size()) 39 40 const int INF = int(1e9); 41 42 int n; 43 string s; 44 45 inline bool read() { 46 if(!(cin >> n >> s)) 47 return false; 48 return true; 49 } 50 51 int cntSame(const string &s) { 52 int ans = 0; 53 fore (i, 1, sz(s)) 54 ans += (s[i - 1] == s[i]); 55 assert(ans % 2 == 0); 56 return ans / 2; 57 } 58 59 inline void solve() { 60 int ans = INF; 61 fore (k, 0, 2) { 62 ans = min(ans, cntSame(string(1, '0' + k) + s + string(1, '1' - k))); 63 } 64 cout << ans << endl; 65 } 66 67 int main() { 68 ios_base::sync_with_stdio(false); 69 cin.tie(0), cout.tie(0); 70 cout << fixed << setprecision(15); 71 72 int tc; cin >> tc; 73 while(tc--) { 74 assert(read()); 75 solve(); 76 } 77 return 0; 78 } 79 ``` 80 81 [1437C - Chef Monocarp](/contest/1437/problem/C "Educational Codeforces Round 97 (Rated for Div. 2)") 82 83 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution 1 (pikmike)** 90 91 ``` 92 #include <bits/stdc++.h> 93 94 #define forn(i, n) for (int i = 0; i < int(n); i++) 95 96 using namespace std; 97 98 const int INF = 1e9; 99 100 void solve(){ 101 int n; 102 scanf("%d", &n); 103 vector<int> t(n); 104 forn(i, n){ 105 scanf("%d", &t[i]); 106 --t[i]; 107 } 108 sort(t.begin(), t.end()); 109 vector<vector<int>> dp(n + 1, vector<int>(2 * n, INF)); 110 dp[0][0] = 0; 111 forn(i, n + 1) forn(j, 2 * n - 1) if (dp[i][j] < INF){ 112 if (i < n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j)); 113 dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]); 114 } 115 printf("%d\n", dp[n][2 * n - 1]); 116 } 117 118 int main() { 119 int q; 120 scanf("%d", &q); 121 forn(_, q) solve(); 122 } 123 ``` 124 125 **Solution 2 (pikmike)** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 #define forn(i, n) for (int i = 0; i < int(n); i++) 131 132 using namespace std; 133 134 template<typename T> 135 T hungarian(const vector<vector<T>>& cost) { 136 const T INF = numeric_limits<T>::max(); 137 int n = cost.size(), m = cost[0].size(); 138 vector<T> u(n + 1), v(m + 1), dist(m + 1); 139 vector<int> p(m + 1), way(m + 1), used(m + 1); 140 for (int i = 1; i <= n; ++i) { 141 p[0] = i; 142 int j0 = 0; 143 fill(dist.begin(), dist.end(), INF); 144 do { 145 used[j0] = i; 146 int i0 = p[j0], j1 = -1; 147 T delta = INF; 148 for (int j = 1; j <= m; ++j) if (used[j] != i) { 149 T cur = cost[i0 - 1][j - 1] - u[i0] - v[j]; 150 if (cur < dist[j]) dist[j] = cur, way[j] = j0; 151 if (dist[j] < delta) delta = dist[j], j1 = j; 152 } 153 forn(j, m + 1) { 154 if (used[j] == i) u[p[j]] += delta, v[j] -= delta; 155 else dist[j] -= delta; 156 } 157 j0 = j1; 158 } while (p[j0] != 0); 159 for (int j1; j0; j0 = j1) 160 p[j0] = p[j1 = way[j0]]; 161 } 162 163 return -v[0]; 164 } 165 166 void solve(){ 167 int n; 168 scanf("%d", &n); 169 vector<int> t(n); 170 forn(i, n){ 171 scanf("%d", &t[i]); 172 --t[i]; 173 } 174 vector<vector<int>> cost(n, vector<int>(2 * n)); 175 forn(i, n) forn(j, 2 * n) cost[i][j] = abs(t[i] - j); 176 printf("%d\n", hungarian(cost)); 177 } 178 179 int main() { 180 int q; 181 scanf("%d", &q); 182 forn(_, q) solve(); 183 } 184 ``` 185 186 [1437D - Minimal Height Tree](/contest/1437/problem/D "Educational Codeforces Round 97 (Rated for Div. 2)") 187 188 Idea: [adedalic](/profile/adedalic "International Master adedalic") 189 190 **Tutorial** 191 192 Tutorial is loading... 193 194 **Solution (adedalic)** 195 196 ``` 197 #include<bits/stdc++.h> 198 199 using namespace std; 200 201 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 202 #define sz(a) int((a).size()) 203 204 #define x first 205 #define y second 206 207 typedef long long li; 208 typedef pair<int, int> pt; 209 210 const int INF = int(1e9); 211 const li INF64 = li(1e18); 212 213 int n; 214 vector<int> a; 215 216 inline bool read() { 217 if(!(cin >> n)) 218 return false; 219 a.resize(n); 220 fore (i, 0, n) 221 cin >> a[i]; 222 return true; 223 } 224 225 inline void solve() { 226 vector<int> h(n, INF); 227 h[0] = 0; 228 int lst = 0; 229 fore (i, 1, n) { 230 if (i - 1 > 0 && a[i - 1] > a[i]) 231 lst++; 232 h[i] = h[lst] + 1; 233 } 234 cout << h[n - 1] << endl; 235 } 236 237 int main() { 238 #ifdef _DEBUG 239 freopen("input.txt", "r", stdin); 240 int tt = clock(); 241 #endif 242 ios_base::sync_with_stdio(false); 243 cin.tie(0), cout.tie(0); 244 cout << fixed << setprecision(15); 245 246 int tc; cin >> tc; 247 while(tc--) { 248 read(); 249 solve(); 250 251 #ifdef _DEBUG 252 cerr << "TIME = " << clock() - tt << endl; 253 tt = clock(); 254 #endif 255 } 256 return 0; 257 } 258 ``` 259 260 [1437E - Make It Increasing](/contest/1437/problem/E "Educational Codeforces Round 97 (Rated for Div. 2)") 261 262 Idea: [Neon](/profile/Neon "Candidate Master Neon") 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution (Ne0n25)** 269 270 ``` 271 #include <bits/stdc++.h> 272 273 using namespace std; 274 275 #define forn(i, n) for (int i = 0; i < int(n); ++i) 276 277 const int N = 500 * 1000 + 13; 278 279 int n, k; 280 int a[N], b[N]; 281 282 int main() { 283 scanf("%d%d", &n, &k); 284 forn(i, n) scanf("%d", &a[i + 1]); 285 a[0] = -1e9; 286 a[n + 1] = 2e9; 287 forn(i, n + 2) a[i] -= i; 288 forn(i, k) scanf("%d", &b[i + 1]); 289 b[k + 1] = n + 1; 290 291 int ans = 0; 292 forn(i, k + 1) { 293 int l = b[i], r = b[i + 1]; 294 if (a[l] > a[r]) { 295 puts("-1"); 296 return 0; 297 } 298 vector<int> lis; 299 for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) { 300 auto pos = upper_bound(lis.begin(), lis.end(), a[j]); 301 if (pos == lis.end()) lis.push_back(a[j]); 302 else *pos = a[j]; 303 } 304 ans += (r - l - 1) - int(lis.size()); 305 } 306 307 printf("%d\n", ans); 308 } 309 ``` 310 311 [1437F - Emotional Fishermen](/contest/1437/problem/F "Educational Codeforces Round 97 (Rated for Div. 2)") 312 313 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution (BledDest)** 320 321 ``` 322 #include<bits/stdc++.h> 323 324 using namespace std; 325 326 const int N = 5043; 327 const int MOD = 998244353; 328 329 int dp[N][N]; 330 int pdp[N][N]; 331 int cntLess[N]; 332 int lastLess[N]; 333 int a[N]; 334 int n; 335 336 int add(int x, int y) 337 { 338 x += y; 339 while(x >= MOD) x -= MOD; 340 while(x < 0) x += MOD; 341 return x; 342 } 343 344 int sub(int x, int y) 345 { 346 return add(x, MOD - y); 347 } 348 349 int mul(int x, int y) 350 { 351 return (x * 1ll * y) % MOD; 352 } 353 354 int main() 355 { 356 cin >> n; 357 for(int i = 0; i < n; i++) 358 cin >> a[i]; 359 sort(a, a + n); 360 for(int i = 0; i < n; i++) 361 { 362 cntLess[i] = 0; 363 lastLess[i] = -1; 364 for(int j = 0; j < n; j++) 365 if(a[j] * 2 <= a[i]) 366 { 367 lastLess[i] = j; 368 cntLess[i]++; 369 } 370 } 371 for(int i = 0; i < n; i++) 372 { 373 dp[i][1] = 1; 374 pdp[i + 1][1] = add(pdp[i][1], dp[i][1]); 375 } 376 for(int k = 2; k <= n; k++) 377 for(int i = 0; i < n; i++) 378 { 379 if(cntLess[i] + 1 >= k) 380 dp[i][k] = add(mul(dp[i][k - 1], add(cntLess[i], sub(2, k))), pdp[lastLess[i] + 1][k - 1]); 381 else 382 dp[i][k] = 0; 383 //cerr << i << " " << k << " " << dp[i][k] << endl; 384 pdp[i + 1][k] = add(pdp[i][k], dp[i][k]); 385 } 386 387 cout << dp[n - 1][n] << endl; 388 } 389 ``` 390 391 [1437G - Death DBMS](/contest/1437/problem/G "Educational Codeforces Round 97 (Rated for Div. 2)") 392 393 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 394 395 **Tutorial** 396 397 Tutorial is loading... 398 399 **Solution 1 (pikmike)** 400 401 ``` 402 #include <bits/stdc++.h> 403 404 #define forn(i, n) for (int i = 0; i < int(n); i++) 405 406 using namespace std; 407 408 const int AL = 26; 409 410 vector<int> val; 411 vector<int> pos; 412 413 struct aho_corasick { 414 struct node { 415 map<int, int> nxt, go; 416 int p, pch; 417 int suf, ssuf; 418 multiset<int> vals; 419 bool term; 420 421 node() { 422 nxt.clear(); 423 go.clear(); 424 suf = ssuf = -1; 425 term = false; 426 vals.clear(); 427 p = -1, pch = -1; 428 } 429 }; 430 431 vector<node> nodes; 432 433 aho_corasick() { 434 nodes = vector<node>(1, node()); 435 } 436 437 int add(const string& s) { 438 int v = 0; 439 forn(i, s.size()) { 440 int c = s[i] - 'a'; 441 if (!nodes[v].nxt.count(c)) { 442 nodes.push_back(node()); 443 nodes[v].nxt[c] = int(nodes.size()) - 1; 444 nodes.back().p = v; 445 nodes.back().pch = c; 446 } 447 v = nodes[v].nxt[c]; 448 } 449 nodes[v].term = true; 450 nodes[v].vals.insert(0); 451 return v; 452 } 453 454 int feed(const string &s){ 455 int v = 0; 456 int ans = -1; 457 forn(i, s.size()){ 458 int c = s[i] - 'a'; 459 v = go(v, c); 460 int u = v; 461 while (u != 0){ 462 if (!nodes[u].vals.empty()) 463 ans = max(ans, *nodes[u].vals.rbegin()); 464 u = ssuf(u); 465 } 466 } 467 return ans; 468 } 469 470 int go(int v, int c) { 471 if (nodes[v].go.count(c)) 472 return nodes[v].go[c]; 473 if (nodes[v].nxt.count(c)) 474 return nodes[v].go[c] = nodes[v].nxt[c]; 475 if (v == 0) 476 return nodes[v].go[c] = 0; 477 return nodes[v].go[c] = go(suf(v), c); 478 } 479 480 int suf(int v) { 481 if (nodes[v].suf != -1) 482 return nodes[v].suf; 483 if (v == 0 || nodes[v].p == 0) 484 return nodes[v].suf = 0; 485 return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch); 486 } 487 488 int ssuf(int v) { 489 if (nodes[v].ssuf != -1) 490 return nodes[v].ssuf; 491 if (v == 0 || nodes[v].p == 0) 492 return nodes[v].ssuf = 0; 493 int s = suf(v); 494 if (nodes[s].term) 495 return nodes[v].ssuf = s; 496 return nodes[v].ssuf = ssuf(s); 497 } 498 }; 499 500 aho_corasick ac; 501 502 int main() { 503 int n, m; 504 ios::sync_with_stdio(!cin.tie(0)); 505 cin >> n >> m; 506 pos.resize(n); 507 val.resize(n, 0); 508 509 vector<int> tp2; 510 511 ac = aho_corasick(); 512 513 forn(i, n){ 514 string s; 515 cin >> s; 516 pos[i] = ac.add(s); 517 } 518 519 forn(i, m){ 520 int t; 521 cin >> t; 522 if (t == 1){ 523 int j, x; 524 cin >> j >> x; 525 --j; 526 ac.nodes[pos[j]].vals.erase(ac.nodes[pos[j]].vals.find(val[j])); 527 val[j] = x; 528 ac.nodes[pos[j]].vals.insert(val[j]); 529 } 530 else{ 531 string q; 532 cin >> q; 533 printf("%d\n", ac.feed(q)); 534 } 535 } 536 537 return 0; 538 } 539 ``` 540 541 **Solution 2 (pikmike)** 542 543 ``` 544 #include <bits/stdc++.h> 545 546 #define forn(i, n) for (int i = 0; i < int(n); i++) 547 548 using namespace std; 549 550 const int AL = 26; 551 vector<vector<pair<int, int>>> upd; 552 vector<int> ans; 553 int n, m; 554 555 struct segtree{ 556 vector<int*> where; 557 vector<int> vals; 558 vector<int> t; 559 int n; 560 561 segtree(){} 562 563 segtree(int n) : n(n){ 564 t.assign(4 * n, -1); 565 where.clear(); 566 vals.clear(); 567 } 568 569 void updh(int v, int l, int r, int L, int R, int val){ 570 if (L >= R) 571 return; 572 if (l == L && r == R){ 573 where.push_back(&t[v]); 574 vals.push_back(t[v]); 575 t[v] = max(t[v], val); 576 return; 577 } 578 int m = (l + r) / 2; 579 updh(v * 2, l, m, L, min(m, R), val); 580 updh(v * 2 + 1, m, r, max(m, L), R, val); 581 } 582 583 void upd(int l, int r, int val){ 584 updh(1, 0, n, l, r, val); 585 } 586 587 int geth(int v, int l, int r, int pos){ 588 if (l == r - 1) 589 return t[v]; 590 int m = (l + r) / 2; 591 if (pos < m) 592 return max(t[v], geth(v * 2, l, m, pos)); 593 return max(t[v], geth(v * 2 + 1, m, r, pos)); 594 } 595 596 int get(int pos){ 597 return geth(1, 0, n, pos); 598 } 599 600 void rollback(){ 601 *where.back() = vals.back(); 602 where.pop_back(); 603 vals.pop_back(); 604 } 605 }; 606 607 segtree st; 608 609 struct aho_corasick { 610 struct node { 611 map<int, int> nxt, go; 612 int p, pch; 613 int suf, ssuf; 614 vector<int> term, qs; 615 616 node() { 617 nxt.clear(); 618 go.clear(); 619 suf = ssuf = -1; 620 term.clear(); 621 p = -1, pch = -1; 622 qs.clear(); 623 } 624 }; 625 626 vector<node> nodes; 627 vector<vector<int>> g; 628 629 aho_corasick() { 630 nodes = vector<node>(1, node()); 631 } 632 633 void add(const string& s, int id) { 634 int v = 0; 635 forn(i, s.size()) { 636 int c = s[i] - 'a'; 637 if (!nodes[v].nxt.count(c)) { 638 nodes.push_back(node()); 639 nodes[v].nxt[c] = int(nodes.size()) - 1; 640 nodes.back().p = v; 641 nodes.back().pch = c; 642 } 643 v = nodes[v].nxt[c]; 644 } 645 nodes[v].term.push_back(id); 646 } 647 648 void feed(const string &s, int id){ 649 int v = 0; 650 forn(i, s.size()){ 651 int c = s[i] - 'a'; 652 v = go(v, c); 653 nodes[v].qs.push_back(id); 654 } 655 } 656 657 int go(int v, int c) { 658 if (nodes[v].go.count(c)) 659 return nodes[v].go[c]; 660 if (nodes[v].nxt.count(c)) 661 return nodes[v].go[c] = nodes[v].nxt[c]; 662 if (v == 0) 663 return nodes[v].go[c] = 0; 664 return nodes[v].go[c] = go(suf(v), c); 665 } 666 667 int suf(int v) { 668 if (nodes[v].suf != -1) 669 return nodes[v].suf; 670 if (v == 0 || nodes[v].p == 0) 671 return nodes[v].suf = 0; 672 return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch); 673 } 674 675 void build_tree() { 676 g.resize(nodes.size()); 677 forn(v, nodes.size()) { 678 int u = suf(v); 679 if (v != u) 680 g[u].push_back(v); 681 } 682 } 683 684 void dfs(int v){ 685 int cur = st.where.size(); 686 for (auto i : nodes[v].term){ 687 int lst = m; 688 for (auto it : upd[i]){ 689 st.upd(it.first, lst, it.second); 690 lst = it.first; 691 } 692 st.upd(0, lst, 0); 693 } 694 for (auto j : nodes[v].qs){ 695 ans[j] = max(ans[j], st.get(j)); 696 } 697 for (int u : g[v]){ 698 dfs(u); 699 } 700 int nw = st.where.size(); 701 forn(_, nw - cur){ 702 st.rollback(); 703 } 704 } 705 }; 706 707 aho_corasick ac; 708 709 int main() { 710 ios::sync_with_stdio(!cin.tie(0)); 711 cin >> n >> m; 712 upd.resize(n); 713 ans.resize(m, -1); 714 715 vector<int> tp2; 716 717 ac = aho_corasick(); 718 st = segtree(m); 719 720 forn(i, n){ 721 string s; 722 cin >> s; 723 ac.add(s, i); 724 } 725 forn(i, m){ 726 int t; 727 cin >> t; 728 if (t == 1){ 729 int j, x; 730 cin >> j >> x; 731 --j; 732 upd[j].push_back(make_pair(i, x)); 733 } 734 else{ 735 string q; 736 cin >> q; 737 ac.feed(q, i); 738 tp2.push_back(i); 739 } 740 } 741 forn(i, n){ 742 reverse(upd[i].begin(), upd[i].end()); 743 } 744 745 ac.build_tree(); 746 ac.dfs(0); 747 for (auto it : tp2) 748 cout << ans[it] << "\n"; 749 return 0; 750 } 751 ```