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