1380.md (16182B)
1 Source: https://codeforces.com/blog/entry/80054 2 3 [1380A - Three Indices](/contest/1380/problem/A "Educational Codeforces Round 91 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Ne0n25)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 const int N = 1000; 19 20 int n; 21 int a[N]; 22 23 void solve() { 24 cin >> n; 25 for (int i = 0; i < n; ++i) 26 cin >> a[i]; 27 for (int i = 1; i < n - 1; ++i) { 28 if (a[i] > a[i - 1] && a[i] > a[i + 1]) { 29 cout << "YES" << endl; 30 cout << i << ' ' << i + 1 << ' ' << i + 2 << endl; 31 return; 32 } 33 } 34 cout << "NO" << endl; 35 } 36 37 int main() { 38 int T; 39 cin >> T; 40 while (T--) 41 solve(); 42 } 43 ``` 44 45 [1380B - Universal Solution](/contest/1380/problem/B "Educational Codeforces Round 91 (Rated for Div. 2)") 46 47 Idea: [adedalic](/profile/adedalic "International Master adedalic") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution (adedalic)** 54 55 ``` 56 fun main() { 57 val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S') 58 repeat(readLine()!!.toInt()) { 59 val s = readLine()!! 60 val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key 61 println("${winBy[maxCnt]}".repeat(s.length)) 62 } 63 } 64 ``` 65 66 [1380C - Create The Teams](/contest/1380/problem/C "Educational Codeforces Round 91 (Rated for Div. 2)") 67 68 Idea: [Roms](/profile/Roms "Master Roms") 69 70 **Tutorial** 71 72 Tutorial is loading... 73 74 **Solution (Roms)** 75 76 ``` 77 for _ in range(int(input())): 78 n, x = map(int, input().split()) 79 a = sorted(list(map(int, input().split())), reverse=True) 80 res, cur = 0, 1 81 for s in a: 82 if s * cur >= x: 83 res += 1 84 cur = 0 85 cur += 1 86 print(res) 87 ``` 88 89 [1380D - Berserk And Fireball](/contest/1380/problem/D "Educational Codeforces Round 91 (Rated for Div. 2)") 90 91 Idea: [Roms](/profile/Roms "Master Roms") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution (Roms)** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 const int N = int(2e5) + 9; 105 106 int n, m; 107 long long x, k, y; 108 int a[N]; 109 int b[N]; 110 111 bool upd(int l, int r, long long &res) { 112 if (l > r) return true; 113 bool canDel = false; 114 int mx = *max_element(a + l, a + r + 1); 115 int len = r - l + 1; 116 if (l - 1 >= 0 && a[l - 1] > mx) canDel = true; 117 if (r + 1 < n && a[r + 1] > mx) canDel = true; 118 if (len < k && !canDel) return false; 119 120 int need = len % k; 121 res += need * y; 122 len -= need; 123 124 if (y * k >= x) { 125 res += len / k * x; 126 } else if(canDel) { 127 res += len * y; 128 } else { 129 res += (len - k) * y + x; 130 } 131 132 return true; 133 } 134 135 int main(){ 136 scanf("%d %d", &n, &m); 137 scanf("%lld %lld %lld", &x, &k, &y); 138 for (int i = 0; i < n; ++i) scanf("%d", a + i); 139 for (int i = 0; i < m; ++i) scanf("%d", b + i); 140 141 long long res = 0; 142 int lst = -1, posa = 0, posb = 0; 143 while (posb < m) { 144 while(posa < n && a[posa] != b[posb]) ++posa; 145 if (posa == n) { 146 puts("-1"); 147 return 0; 148 } 149 150 if (!upd(lst + 1, posa - 1, res)) { 151 puts("-1"); 152 return 0; 153 } 154 155 lst = posa; 156 ++posb; 157 } 158 159 if (!upd(lst + 1, n - 1, res)) { 160 puts("-1"); 161 return 0; 162 } 163 164 printf("%lld\n", res); 165 166 return 0; 167 } 168 ``` 169 170 [1380E - Merging Towers](/contest/1380/problem/E "Educational Codeforces Round 91 (Rated for Div. 2)") 171 172 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution 1 (BledDest)** 179 180 ``` 181 #include<bits/stdc++.h> 182 183 using namespace std; 184 185 const int N = 200043; 186 const int L = 20; 187 188 vector<int> g[2 * N]; 189 int p[2 * N]; 190 int up[2 * N][L]; 191 int idx[N]; 192 int psum[N]; 193 int cur[N]; 194 int tin[2 * N]; 195 int tout[2 * N]; 196 int T = 0; 197 198 void dfs(int x, int y) 199 { 200 tin[x] = T++; 201 p[x] = y; 202 up[x][0] = y; 203 for(int i = 1; i < L; i++) 204 up[x][i] = up[up[x][i - 1]][i - 1]; 205 for(auto z : g[x]) 206 dfs(z, x); 207 tout[x] = T++; 208 } 209 210 bool is_ancestor(int x, int y) 211 { 212 return tin[x] <= tin[y] && tout[x] >= tout[y]; 213 } 214 215 int lca(int x, int y) 216 { 217 if(is_ancestor(x, y)) 218 return x; 219 for(int i = L - 1; i >= 0; i--) 220 if(!is_ancestor(up[x][i], y)) 221 x = up[x][i]; 222 return p[x]; 223 } 224 225 int main() 226 { 227 int n, m; 228 scanf("%d %d", &n, &m); 229 for(int i = 0; i < n; i++) 230 { 231 scanf("%d", &idx[i]); 232 idx[i]--; 233 } 234 for(int i = 0; i < m; i++) 235 cur[i] = i; 236 for(int i = 0; i < m - 1; i++) 237 { 238 int x, y; 239 scanf("%d %d", &x, &y); 240 --x; 241 --y; 242 int nidx = m + i; 243 g[nidx].push_back(cur[x]); 244 g[nidx].push_back(cur[y]); 245 cur[x] = nidx; 246 } 247 int root = m * 2 - 2; 248 dfs(root, root); 249 for(int i = 0; i < n - 1; i++) 250 { 251 int t = lca(idx[i], idx[i + 1]); 252 if(t < m) 253 psum[0]++; 254 else 255 psum[t - m + 1]++; 256 } 257 for(int i = 0; i < m - 1; i++) 258 psum[i + 1] += psum[i]; 259 for(int i = 0; i < m; i++) 260 printf("%d\n", n - 1 - psum[i]); 261 } 262 ``` 263 264 **Solution 2 (pikmike)** 265 266 ``` 267 #include <bits/stdc++.h> 268 269 #define forn(i, n) for (int i = 0; i < int(n); i++) 270 271 using namespace std; 272 273 int n, m; 274 vector<int> p; 275 vector<vector<int>> val; 276 vector<int> who; 277 278 int getp(int a){ 279 return a == p[a] ? a : p[a] = getp(p[a]); 280 } 281 282 int main(){ 283 scanf("%d%d", &n, &m); 284 p.resize(m); 285 val.resize(m); 286 who.resize(n); 287 int ans = n - 1; 288 forn(i, m) 289 p[i] = i; 290 forn(i, n){ 291 int x; 292 scanf("%d", &x); 293 --x; 294 who[i] = x; 295 ans -= (i && who[i] == who[i - 1]); 296 val[who[i]].push_back(i); 297 } 298 printf("%d\n", ans); 299 forn(i, m - 1){ 300 int v, u; 301 scanf("%d%d", &v, &u); 302 v = getp(v - 1), u = getp(u - 1); 303 if (val[v].size() < val[u].size()) 304 swap(v, u); 305 for (int x : val[u]){ 306 if (x) ans -= who[x - 1] == v; 307 if (x < n - 1) ans -= who[x + 1] == v; 308 } 309 for (int x : val[u]){ 310 val[v].push_back(x); 311 who[x] = v; 312 } 313 p[u] = v; 314 printf("%d\n", ans); 315 } 316 return 0; 317 } 318 ``` 319 320 [1380F - Strange Addition](/contest/1380/problem/F "Educational Codeforces Round 91 (Rated for Div. 2)") 321 322 Idea: [Roms](/profile/Roms "Master Roms") 323 324 **Tutorial** 325 326 Tutorial is loading... 327 328 **Solution 1 (pikmike)** 329 330 ``` 331 #include <bits/stdc++.h> 332 333 using namespace std; 334 335 #define forn(i, n) for(int i = 0; i < int(n); i++) 336 337 const int MOD = 998244353; 338 const int N = 500 * 1000 + 13; 339 340 string s; 341 342 int add(int a, int b){ 343 a += b; 344 if (a >= MOD) 345 a -= MOD; 346 return a; 347 } 348 349 int mul(int a, int b){ 350 return a * 1ll * b % MOD; 351 } 352 353 struct node{ 354 int val[4], len; 355 }; 356 357 node merge(const node &a, const node &b, int l, int r){ 358 node c; 359 int na = a.len == 1 ? 0 : 1; 360 int nb = b.len == 1 ? 0 : 2; 361 c.len = a.len + b.len; 362 c.val[0] = mul(a.val[na], b.val[nb]); 363 c.val[1] = mul(a.val[na], b.val[3]); 364 c.val[2] = mul(a.val[3], b.val[nb]); 365 c.val[3] = mul(a.val[3], b.val[3]); 366 if (l == 1){ 367 na = a.len == 1 ? 2 : 0; 368 nb = b.len == 1 ? 1 : 0; 369 c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r))); 370 c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r))); 371 c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r))); 372 c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r))); 373 } 374 return c; 375 } 376 377 node t[4 * N]; 378 379 void build(int v, int l, int r){ 380 t[v].len = r - l; 381 if (l == r - 1){ 382 t[v].val[0] = 1; 383 t[v].val[3] = s[l] + 1; 384 return; 385 } 386 int m = (l + r) / 2; 387 build(v * 2, l, m); 388 build(v * 2 + 1, m, r); 389 t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]); 390 } 391 392 void upd(int v, int l, int r, int x, int val){ 393 if (l == r - 1){ 394 s[l] = val; 395 t[v].val[3] = s[l] + 1; 396 return; 397 } 398 int m = (l + r) / 2; 399 if (x < m) 400 upd(v * 2, l, m, x, val); 401 else 402 upd(v * 2 + 1, m, r, x, val); 403 t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]); 404 } 405 406 int main(){ 407 int n, m; 408 409 scanf("%d%d", &n, &m); 410 static char buf[N]; 411 scanf("%s", buf); 412 s = buf; 413 forn(i, n) s[i] -= '0'; 414 415 memset(t, 0, sizeof(t)); 416 build(1, 0, n); 417 418 forn(i, m){ 419 int x, v; 420 scanf("%d%d", &x, &v); 421 --x; 422 upd(1, 0, n, x, v); 423 printf("%d\n", t[1].val[3]); 424 } 425 } 426 ``` 427 428 **Solution 2 (Roms)** 429 430 ``` 431 #include <bits/stdc++.h> 432 433 using namespace std; 434 435 const int N = int(5e5) + 9; 436 const int MOD = 998244353; 437 438 int mul(int a, int b) { 439 return (a * 1LL * b) % MOD; 440 } 441 442 void add(int &a, int x) { 443 a += x; 444 a %= MOD; 445 } 446 447 int bp(int a, int n) { 448 int res = 1; 449 for (; n > 0; n >>= 1) { 450 if (n & 1) res = mul(res, a); 451 a = mul(a, a); 452 } 453 return res; 454 } 455 456 int inv(int a) { 457 int ia = bp(a, MOD - 2); 458 assert(mul(a, ia) == 1); 459 return ia; 460 } 461 462 int n, m; 463 string s; 464 int dp[N][10]; 465 int idp[N][10]; 466 set <pair<int, int> > lr; 467 int res = 1; 468 469 void updRes(int l, int r, int c) { 470 assert(l <= r); 471 if (c == 1) { 472 assert(!lr.count(make_pair(l, r))); 473 lr.insert(make_pair(l, r)); 474 res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']); 475 } else { 476 assert(lr.count(make_pair(l, r))); 477 lr.erase(make_pair(l, r)); 478 res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0'])); 479 } 480 } 481 482 void getLR(int &l, int &r, int pos) { 483 l = r = -1; 484 auto it = lr.lower_bound(make_pair(pos, n)); 485 if(it == lr.begin()) return; 486 --it; 487 if(!(it->first <= pos && pos <= it->second)) return; 488 l = it->first, r = it->second; 489 } 490 491 char buf[N]; 492 int main(){ 493 scanf("%d %d\n", &n, &m); 494 scanf("%s", buf); 495 s = string(buf); 496 for (int i = 0; i <= 9; ++i) { 497 dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]); 498 dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]); 499 } 500 for (int i = 2; i < N; ++i) 501 for (int j = 0; j <= 9; ++j) { 502 dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD; 503 //idp[i][j] = inv(dp[i][j]); 504 } 505 for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0); 506 for (int l = 0; l < n; ) { 507 int r = l; 508 while(r < n && s[r] == '1') ++r; 509 res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']); 510 if (l != r) lr.insert(make_pair(l, r - 1)); 511 l = r + 1; 512 } 513 514 for (int i = 0; i < m; ++i) { 515 int pos; 516 char x; 517 scanf("%d %c\n", &pos, &x); 518 --pos; 519 if (x == '1') { 520 if (s[pos] != '1'){ 521 int l1, r1, l2, r2; 522 getLR(l1, r1, pos - 1); 523 getLR(l2, r2, pos + 1); 524 525 int l = pos, r = pos; 526 if (l1 != -1) { 527 assert(r1 == pos - 1); 528 updRes(l1, r1, -1); 529 l = l1; 530 } else { 531 res = mul(res, inv(dp[0][s[pos] - '0'])); 532 } 533 534 if (l2 != -1) { 535 assert(l2 == pos + 1); 536 updRes(l2, r2, -1); 537 r = r2; 538 } else { 539 if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0'])); 540 } 541 542 s[pos] = x; 543 updRes(l, r, 1); 544 } 545 } else { 546 if (s[pos] != '1') { 547 if (pos - 1 >= 0 && s[pos - 1] == '1') { 548 int l, r; 549 getLR(l, r, pos - 1); 550 updRes(l, r, -1); 551 s[pos] = x; 552 updRes(l, r, 1); 553 } else { 554 res = mul(res, dp[0][x - '0']); 555 res = mul(res, inv(dp[0][s[pos] - '0'])); 556 s[pos] = x; 557 } 558 } else { 559 int l, r; 560 getLR(l, r, pos); 561 assert(l != -1 && r != -1); 562 563 updRes(l, r, -1); 564 s[pos] = x; 565 if (l == r) { 566 res = mul(res, dp[0][s[pos] - '0']); 567 if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']); 568 } else if (pos == l) { 569 res = mul(res, dp[0][s[pos] - '0']); 570 updRes(l + 1, r, 1); 571 } else if (pos == r) { 572 if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']); 573 updRes(l, r - 1, 1); 574 } else { 575 updRes(l, pos - 1, 1); 576 updRes(pos + 1, r, 1); 577 } 578 } 579 580 } 581 printf("%d\n", res); 582 } 583 } 584 ``` 585 586 [1380G - Circular Dungeon](/contest/1380/problem/G "Educational Codeforces Round 91 (Rated for Div. 2)") 587 588 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 589 590 **Tutorial** 591 592 At first, let's say that the expected value is equal to the average of total earnings over all positions and is equal to the sum of earnings over all positions divided by $n$. So we can trasition to minimizing the sum. 593 594 Let's learn how to solve the task for some fixed $k$. Fix some arrangement and rotate the rooms so that the last room contains a mimic. So now you have $cnt_1$ regular chests, then a single mimic, $cnt_2$ regular chests, single mimic, $\dots$, $cnt_k$ regular chests, single mimic. All $cnt_i \ge 0$ and $\sum \limits_{i=1}^{k} cnt_i = n - k$. 595 596 Take a look at some of these intervals of length $cnt_i$. The last chest in the interval is taken from $cnt_i$ starting positions, the second-to-last is taken $cnt_i - 1$ times and so on. 597 598 Now let's find the optimal way to choose $cnt_i$. Fix some values of $cnt_i$. Take a look at the smallest of these values and the largest of them. Let the values be $x$ and $y$. If they differ by at least $2$ ($x \le y - 2$), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one. 599 600 **Proof** 601 602 Consider two sequences of coefficients for both intervals: $[1, 2, \dots, x - 1, x]$ and $[1, 2, \dots, y - 1, y]$. 603 604 However, if you remove one chest, then they will be equal to $[1, 2, \dots, x - 1, x, x + 1]$ and $[1, 2, \dots, y - 1]$. 605 606 If you only consider the difference between the numbers of both sequences, then you can see that only coefficient $y$ got removed and coefficient $x + 1$ was added. So you can rearrange the chests in such a way that all chests are assigned to the same value and only the chest that was assigned to $y$ becomes assigned to $x+1$, thus decreasing the total value. 607 608 Now we have all $cnt_i$ set now. The only thing left is to assign chests optimally. Write down the union of all the coefficient sequences from all the intervals $\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$ and sort them in the non-decreasing order. It's easy to show that the chests should be sorted in the non-increasing order (really classical thing, you can try proving that by showing that any other arrangement can easily be improved once again). 609 610 That allows us to write a solution in $O(n^2)$. Sort all the chests in the beginning, after that for some $k$ multiply the value of the $i$-th chest by $\lfloor \frac{i}{k} \rfloor$ and sum up the results. 611 612 Finally, let's speed this up with prefix sums. Notice that the first $k$ values are multiplied by $0$, the second $k$ values — by $1$ and so on. If $n$ is not divisible by $k$, then the last block just has length smaller than $k$. Thus, we can calculate the answer for some $k$ in $O(\frac{n}{k})$. And that's equal to $O(\sum \limits_{k=1}^{n} \frac{n}{k})$ = $O(n \log n)$. 613 614 Overall complexity: $O(n \log n)$. 615 616 **Solution (pikmike)** 617 618 ``` 619 #include <bits/stdc++.h> 620 621 #define forn(i, n) for (int i = 0; i < int(n); i++) 622 623 using namespace std; 624 625 const int MOD = 998244353; 626 627 int add(int a, int b){ 628 a += b; 629 if (a >= MOD) 630 a -= MOD; 631 if (a < 0) 632 a += MOD; 633 return a; 634 } 635 636 int mul(int a, int b){ 637 return a * 1ll * b % MOD; 638 } 639 640 int binpow(int a, int b){ 641 int res = 1; 642 while (b){ 643 if (b & 1) 644 res = mul(res, a); 645 a = mul(a, a); 646 b >>= 1; 647 } 648 return res; 649 } 650 651 vector<int> pr; 652 653 int main() { 654 int n; 655 scanf("%d", &n); 656 vector<int> c(n); 657 forn(i, n) 658 scanf("%d", &c[i]); 659 sort(c.begin(), c.end(), greater<int>()); 660 pr.push_back(0); 661 forn(i, n) 662 pr.push_back(add(pr.back(), c[i])); 663 664 int invn = binpow(n, MOD - 2); 665 for (int k = 1; k <= n; ++k){ 666 int ans = 0; 667 for (int i = 0, j = 0; i < n; i += k, ++j) 668 ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i]))); 669 printf("%d ", mul(ans, invn)); 670 } 671 puts(""); 672 673 return 0; 674 } 675 ```