2144.md (14921B)
1 Source: https://codeforces.com/blog/entry/146474 2 3 [2144A - Cut the Array](/contest/2144/problem/A "Educational Codeforces Round 182 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 a = list(map(int, input().split())) 18 if sum(a) % 3 == 0: 19 print("1 2") 20 else: 21 print("0 0") 22 ``` 23 24 [2144B - Maximum Cost Permutation](/contest/2144/problem/B "Educational Codeforces Round 182 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (BledDest)** 33 34 ``` 35 #include<bits/stdc++.h> 36 37 using namespace std; 38 39 void solve() 40 { 41 int n; 42 cin >> n; 43 vector<int> p(n); 44 vector<int> pos0; 45 vector<int> used(n); 46 for(int i = 0; i < n; i++) 47 { 48 cin >> p[i]; 49 --p[i]; 50 if(p[i] == -1) 51 pos0.push_back(i); 52 else 53 used[p[i]] = 1; 54 } 55 if(pos0.size() == 1) 56 { 57 int unused = 0; 58 for(int i = 0; i < n; i++) if(used[i] == 0) unused = i; 59 p[pos0[0]] = unused; 60 } 61 int l = 0, r = n - 1; 62 while(l < n && p[l] == l) l++; 63 while(r >= 0 && p[r] == r) r--; 64 cout << max(0, r - l + 1) << "\n"; 65 } 66 67 int main() 68 { 69 ios_base::sync_with_stdio(0); 70 cin.tie(0); 71 int t; 72 cin >> t; 73 for(int i = 0; i < t; i++) 74 solve(); 75 } 76 ``` 77 78 [2144C - Non-Descending Arrays](/contest/2144/problem/C "Educational Codeforces Round 182 (Rated for Div. 2)") 79 80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution (Neon)** 87 88 ``` 89 #include <bits/stdc++.h> 90 91 using namespace std; 92 93 const int MOD = 998244353; 94 95 int main() { 96 int t; 97 cin >> t; 98 while (t--) { 99 int n; 100 cin >> n; 101 vector<int> a(n), b(n); 102 for (auto &x : a) cin >> x; 103 for (auto &x : b) cin >> x; 104 int ans = 1; 105 for (int i = 0; i < n; ++i) { 106 if (a[i] > b[i]) swap(a[i], b[i]); 107 if (!i || a[i] >= b[i - 1]) ans = (ans * 2LL) % MOD; 108 } 109 cout << ans << '\n'; 110 } 111 } 112 ``` 113 114 [2144D - Price Tags](/contest/2144/problem/D "Educational Codeforces Round 182 (Rated for Div. 2)") 115 116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution (adedalic)** 123 124 ``` 125 for _t in range(int(input())): 126 n, y = map(int, input().split()) 127 a = list(map(int, input().split())) 128 A = max(a) + 1 129 cntTags = [0] * A 130 for v in a: 131 cntTags[v] += 1 132 pSum = [0] * A 133 for i in range(1, A): 134 pSum[i] = pSum[i - 1] + cntTags[i] 135 136 ans = -(10**18) 137 if A == 2: 138 print(n) 139 continue 140 for x in range(2, A): 141 res = 0 142 for price in range(1, A): 143 l = x * (price - 1) 144 r = min(A - 1, x * price) 145 if l >= A: 146 break 147 cnt = pSum[r] - pSum[l] 148 res += cnt * price 149 res -= y * max(0, cnt - cntTags[price]) 150 ans = max(ans, res) 151 print(ans) 152 ``` 153 154 [2144E1 - Looking at Towers (easy version)](/contest/2144/problem/E1 "Educational Codeforces Round 182 (Rated for Div. 2)") 155 156 Idea: [Roms](/profile/Roms "Master Roms") 157 158 **Tutorial** 159 160 Tutorial is loading... 161 162 [2144E2 - Looking at Towers (difficult version)](/contest/2144/problem/E2 "Educational Codeforces Round 182 (Rated for Div. 2)") 163 164 Idea: [Roms](/profile/Roms "Master Roms") 165 166 **Tutorial** 167 168 Tutorial is loading... 169 170 **Solution (BledDest)** 171 172 ``` 173 #include<bits/stdc++.h> 174 175 using namespace std; 176 177 const int MOD = 998244353; 178 const int N = 1000043; 179 180 int add(int x, int y) 181 { 182 x += y; 183 while(x >= MOD) x -= MOD; 184 while(x < 0) x += MOD; 185 return x; 186 } 187 188 int mul(int x, int y) 189 { 190 return (x * 1ll * y) % MOD; 191 } 192 193 int binpow(int x, int y) 194 { 195 int z = 1; 196 while(y > 0) 197 { 198 if(y % 2 == 1) z = mul(z, x); 199 x = mul(x, x); 200 y /= 2; 201 } 202 return z; 203 } 204 205 vector<int> get(const vector<int>& a) 206 { 207 int cur = -1; 208 vector<int> res; 209 for(auto x : a) 210 if(x > cur) 211 { 212 res.push_back(x); 213 cur = x; 214 } 215 return res; 216 } 217 218 struct SegTree 219 { 220 vector<int> f; 221 vector<int> t; 222 int n; 223 224 int getVal(int v, int pos) 225 { 226 return mul(t[pos], binpow(2, f[v])); 227 } 228 229 void push(int v) 230 { 231 if(f[v] != 0) 232 { 233 f[2 * v + 1] += f[v]; 234 f[2 * v + 2] += f[v]; 235 f[v] = 0; 236 } 237 } 238 239 void resolve(int v, int pos) 240 { 241 if(f[v] != 0) 242 { 243 t[pos] = mul(t[pos], binpow(2, f[v])); 244 f[v] = 0; 245 } 246 } 247 248 int get(int v, int l, int r, int pos) 249 { 250 if(l == r - 1) 251 return getVal(v, pos); 252 else 253 { 254 push(v); 255 int m = (l + r) / 2; 256 if(pos < m) 257 return get(v * 2 + 1, l, m, pos); 258 else 259 return get(v * 2 + 2, m, r, pos); 260 } 261 } 262 263 int get(int pos) 264 { 265 return get(0, 0, n, pos); 266 } 267 268 void inc(int v, int l, int r, int pos, int val) 269 { 270 if(l == r - 1) 271 { 272 resolve(v, pos); 273 t[pos] = add(t[pos], val); 274 } 275 else 276 { 277 push(v); 278 int m = (l + r) / 2; 279 if(pos < m) 280 inc(v * 2 + 1, l, m, pos, val); 281 else 282 inc(v * 2 + 2, m, r, pos, val); 283 } 284 } 285 286 void inc(int pos, int val) 287 { 288 return inc(0, 0, n, pos, val); 289 } 290 291 void mulBy2(int v, int l, int r, int L, int R) 292 { 293 if(L >= R) return; 294 if(l == L && r == R) 295 f[v]++; 296 else 297 { 298 push(v); 299 int m = (l + r) / 2; 300 mulBy2(v * 2 + 1, l, m, L, min(R, m)); 301 mulBy2(v * 2 + 2, m, r, max(L, m), R); 302 } 303 } 304 305 void mulBy2(int l, int r) 306 { 307 mulBy2(0, 0, n, l, r); 308 } 309 310 SegTree(int n = 0) 311 { 312 this->n = n; 313 f.resize(4 * n); 314 t.resize(n); 315 } 316 }; 317 318 vector<int> calc(const vector<int>& a, const vector<int>& b) 319 { 320 int n = a.size(); 321 int m = b.size(); 322 SegTree tree(m + 1); 323 tree.inc(0, 1); 324 vector<int> res(n); 325 int maxVal = b.back(); 326 for(int i = 0; i < n; i++) 327 { 328 int x = a[i]; 329 if(x > maxVal) continue; 330 else 331 { 332 if (x == maxVal) res[i] = tree.get(m - 1); 333 int lf = lower_bound(b.begin(), b.end(), x) - b.begin(); 334 tree.mulBy2(lf + 1, m + 1); 335 if(b[lf] == x) 336 { 337 int cur = tree.get(lf); 338 tree.inc(lf + 1, cur); 339 } 340 } 341 } 342 return res; 343 } 344 345 void solve() 346 { 347 int n; 348 cin >> n; 349 vector<int> a(n); 350 for(int i = 0; i < n; i++) 351 cin >> a[i]; 352 auto left_view = get(a); 353 reverse(a.begin(), a.end()); 354 auto right_view = get(a); 355 reverse(a.begin(), a.end()); 356 357 auto dpL = calc(a, left_view); 358 reverse(a.begin(), a.end()); 359 auto dpR = calc(a, right_view); 360 reverse(a.begin(), a.end()); 361 reverse(dpR.begin(), dpR.end()); 362 363 int maxVal = *max_element(a.begin(), a.end()); 364 int ans = 0; 365 int sumLeft = 0; 366 for(int i = 0; i < n; i++) 367 { 368 if(a[i] > maxVal) continue; 369 else 370 { 371 if(a[i] == maxVal) ans = add(ans, mul(add(sumLeft, dpL[i]), dpR[i])); 372 sumLeft = mul(sumLeft, 2); 373 if(a[i] == maxVal) sumLeft = add(sumLeft, dpL[i]); 374 } 375 } 376 cout << ans << endl; 377 } 378 379 int main() 380 { 381 ios_base::sync_with_stdio(0); 382 cin.tie(0); 383 int t; 384 cin >> t; 385 for(int i = 0; i < t; i++) solve(); 386 } 387 ``` 388 389 [2144F - Bracket Groups](/contest/2144/problem/F "Educational Codeforces Round 182 (Rated for Div. 2)") 390 391 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 392 393 **Tutorial** 394 395 Tutorial is loading... 396 397 **Solution 1 (awoo)** 398 399 ``` 400 #include <bits/stdc++.h> 401 402 #define forn(i, n) for (int i = 0; i < int(n); i++) 403 404 using namespace std; 405 406 const string al = "()"; 407 408 struct aho_corasick { 409 static const int AL = 2; 410 411 struct node { 412 int nxt[AL], go[AL]; 413 int p, pch; 414 int suf, ssuf; 415 bool term; 416 417 node() { 418 memset(nxt, -1, sizeof(nxt)); 419 memset(go, -1, sizeof(go)); 420 suf = ssuf = -1; 421 term = false; 422 } 423 }; 424 425 vector<node> nodes; 426 vector<vector<int>> g; 427 428 aho_corasick() { 429 nodes.push_back(node()); 430 } 431 432 void add(const string& s) { 433 int v = 0; 434 forn(i, s.size()) { 435 int c = al.find(s[i]); 436 if (nodes[v].nxt[c] == -1) { 437 nodes.push_back(node()); 438 nodes[v].nxt[c] = nodes.size() - 1; 439 nodes.back().p = v; 440 nodes.back().pch = c; 441 } 442 v = nodes[v].nxt[c]; 443 } 444 nodes[v].term = true; 445 } 446 447 int go(int v, int c) { 448 if (nodes[v].go[c] != -1) 449 return nodes[v].go[c]; 450 if (nodes[v].nxt[c] != -1) 451 return nodes[v].go[c] = nodes[v].nxt[c]; 452 if (v == 0) 453 return nodes[v].go[c] = 0; 454 return nodes[v].go[c] = go(suf(v), c); 455 } 456 457 int suf(int v) { 458 if (nodes[v].suf != -1) 459 return nodes[v].suf; 460 if (v == 0 || nodes[v].p == 0) 461 return nodes[v].suf = 0; 462 return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch); 463 } 464 465 int ssuf(int v) { 466 if (nodes[v].ssuf != -1) 467 return nodes[v].ssuf; 468 if (v == 0 || nodes[v].p == 0) 469 return nodes[v].ssuf = 0; 470 int s = suf(v); 471 if (nodes[s].term) 472 return nodes[v].ssuf = s; 473 return nodes[v].ssuf = ssuf(s); 474 } 475 476 void build_tree() { 477 g.resize(nodes.size()); 478 forn(v, nodes.size()) { 479 int u = suf(v); 480 if (v != u) 481 g[u].push_back(v); 482 } 483 } 484 }; 485 486 int main() { 487 int n, k; 488 cin >> n >> k; 489 vector<string> s(n); 490 forn(i, n) cin >> s[i]; 491 forn(i, n) if (s[i] == "()"){ 492 cout << -1 << '\n'; 493 return 0; 494 } 495 aho_corasick ac; 496 forn(i, n) ac.add(s[i]); 497 vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.nodes.size(), vector<char>(k + 1))); 498 vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.nodes.size(), vector<pair<int, int>>(k + 1))); 499 dp[0][0][0] = true; 500 forn(i, k) forn(v, ac.nodes.size()) forn(bal, i + 1) if (dp[i][v][bal]){ 501 forn(c, 2){ 502 int nbal = bal + (c == 0 ? 1 : -1); 503 if (nbal < 0) continue; 504 int u = ac.go(v, c); 505 if (ac.nodes[u].term || ac.ssuf(u) != 0) continue; 506 dp[i + 1][u][nbal] = true; 507 p[i + 1][u][nbal] = {v, c}; 508 } 509 } 510 int sv = -1; 511 forn(v, ac.nodes.size()) if (dp[k][v][0]){ 512 sv = v; 513 break; 514 } 515 if (sv == -1){ 516 cout << 2 << '\n'; 517 vector<string> res(2); 518 forn(i, k / 2){ 519 res[0] += "()"; 520 res[1] += '('; 521 } 522 forn(i, k / 2){ 523 res[1] += ')'; 524 } 525 vector<vector<int>> ans(2); 526 forn(i, n){ 527 bool any = false; 528 forn(j, int(s[i].size()) - 1) 529 any |= s[i][j] == s[i][j + 1]; 530 ans[!any].push_back(i); 531 } 532 forn(i, 2){ 533 cout << res[i] << '\n'; 534 cout << ans[i].size() << '\n'; 535 for (int j : ans[i]) cout << j + 1 << " "; 536 cout << '\n'; 537 } 538 } 539 else{ 540 cout << 1 << '\n'; 541 string res = ""; 542 int bal = 0, v = sv; 543 for (int i = k; i > 0; --i){ 544 auto [u, c] = p[i][v][bal]; 545 v = u; 546 res += al[c]; 547 bal -= c == 0 ? 1 : -1; 548 } 549 reverse(res.begin(), res.end()); 550 cout << res << '\n'; 551 cout << n << '\n'; 552 forn(i, n) cout << i + 1 << " "; 553 cout << '\n'; 554 } 555 return 0; 556 } 557 ``` 558 559 **Solution 2 (awoo)** 560 561 ``` 562 #include <bits/stdc++.h> 563 564 #define forn(i, n) for (int i = 0; i < int(n); i++) 565 566 using namespace std; 567 568 const string al = "()"; 569 570 int main() { 571 int n, k; 572 cin >> n >> k; 573 vector<string> s(n); 574 forn(i, n) cin >> s[i]; 575 forn(i, n) if (s[i] == "()"){ 576 cout << -1 << '\n'; 577 return 0; 578 } 579 580 vector<string> ac(1, ""); 581 forn(i, n) forn(j, s[i].size()) 582 ac.push_back(s[i].substr(0, j + 1)); 583 sort(ac.begin(), ac.end()); 584 ac.resize(unique(ac.begin(), ac.end()) - ac.begin()); 585 586 vector<char> bad(ac.size()); 587 set<string> tot(s.begin(), s.end()); 588 vector<vector<int>> go(ac.size(), vector<int>(2)); 589 forn(i, ac.size()) forn(j, ac[i].size() + 1){ 590 bad[i] |= tot.count(ac[i].substr(j)); 591 forn(t, 2) if (go[i][t] == 0){ 592 string nw = ac[i].substr(j) + al[t]; 593 auto it = lower_bound(ac.begin(), ac.end(), nw); 594 if (it != ac.end() && *it == nw) 595 go[i][t] = it - ac.begin(); 596 } 597 } 598 599 vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.size(), vector<char>(k + 1))); 600 vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.size(), vector<pair<int, int>>(k + 1))); 601 dp[0][0][0] = true; 602 forn(i, k) forn(v, ac.size()) forn(bal, i + 1) if (dp[i][v][bal]){ 603 forn(c, 2){ 604 int nbal = bal + (c == 0 ? 1 : -1); 605 if (nbal < 0) continue; 606 int u = go[v][c]; 607 if (bad[u]) continue; 608 dp[i + 1][u][nbal] = true; 609 p[i + 1][u][nbal] = {v, c}; 610 } 611 } 612 int sv = -1; 613 forn(v, ac.size()) if (dp[k][v][0]){ 614 sv = v; 615 break; 616 } 617 if (sv == -1){ 618 cout << 2 << '\n'; 619 vector<string> res(2); 620 forn(i, k / 2){ 621 res[0] += "()"; 622 res[1] += '('; 623 } 624 forn(i, k / 2){ 625 res[1] += ')'; 626 } 627 vector<vector<int>> ans(2); 628 forn(i, n){ 629 bool any = false; 630 forn(j, int(s[i].size()) - 1) 631 any |= s[i][j] == s[i][j + 1]; 632 ans[!any].push_back(i); 633 } 634 forn(i, 2){ 635 cout << res[i] << '\n'; 636 cout << ans[i].size() << '\n'; 637 for (int j : ans[i]) cout << j + 1 << " "; 638 cout << '\n'; 639 } 640 } 641 else{ 642 cout << 1 << '\n'; 643 string res = ""; 644 int bal = 0, v = sv; 645 for (int i = k; i > 0; --i){ 646 auto [u, c] = p[i][v][bal]; 647 v = u; 648 res += al[c]; 649 bal -= c == 0 ? 1 : -1; 650 } 651 reverse(res.begin(), res.end()); 652 cout << res << '\n'; 653 cout << n << '\n'; 654 forn(i, n) cout << i + 1 << " "; 655 cout << '\n'; 656 } 657 return 0; 658 } 659 ```