1240.md (14864B)
1 Source: https://codeforces.com/blog/entry/70358 2 3 [1223A - CME](/contest/1223/problem/A "Technocup 2020 - Elimination Round 1") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for t in range(int(input())): 15 n = int(input()) 16 print(2 if n == 2 else (n & 1)) 17 ``` 18 19 [1223B - Strings Equalization](/contest/1223/problem/B "Technocup 2020 - Elimination Round 1") 20 21 Idea: [Roms](/profile/Roms "Master Roms") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Roms)** 28 29 ``` 30 for t in range(int(input())): 31 print('NO' if len(set(input()) & set(input())) == 0 else 'YES') 32 ``` 33 34 [1223C - Save the Nature](/contest/1223/problem/C "Technocup 2020 - Elimination Round 1") 35 36 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 37 38 **Tutorial** 39 40 Tutorial is loading... 41 42 **Solution (adedalic)** 43 44 ``` 45 fun calc(p: IntArray, len: Int, x: Int, a: Int, y: Int, b: Int): Long { 46 var ans = 0L 47 var (cX, cY, cXY) = listOf(0, 0, 0) 48 for (i in 1..len) { 49 if (i % a == 0 && i % b == 0) cXY++ 50 else if (i % a == 0) cX++ 51 else if (i % b == 0) cY++ 52 } 53 for (i in 0 until cXY) 54 ans += p[i] * (x + y) 55 for (i in 0 until cX) 56 ans += p[cXY + i] * x 57 for (i in 0 until cY) 58 ans += p[cXY + cX + i] * y; 59 return ans 60 } 61 62 fun main() { 63 val q = readLine()!!.toInt() 64 for (ct in 1..q) { 65 val n = readLine()!!.toInt() 66 val p = readLine()!!.split(' ').map { it.toInt() / 100 } 67 .sortedDescending().toIntArray() 68 var (x, a) = readLine()!!.split(' ').map { it.toInt() } 69 var (y, b) = readLine()!!.split(' ').map { it.toInt() } 70 val k = readLine()!!.toLong() 71 72 if (x < y) { 73 x = y.also { y = x } 74 a = b.also { b = a } 75 } 76 77 var lf = 0; var rg = n + 1 78 while (rg - lf > 1) { 79 val mid = (lf + rg) / 2 80 if (calc(p, mid, x, a, y, b) >= k) 81 rg = mid 82 else 83 lf = mid 84 } 85 86 if (rg > n) rg = -1 87 println(rg) 88 } 89 } 90 ``` 91 92 [1223D - Sequence Sorting](/contest/1223/problem/D "Technocup 2020 - Elimination Round 1") 93 94 Idea: [Roms](/profile/Roms "Master Roms") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution (Roms)** 101 102 ``` 103 #include <bits/stdc++.h> 104 105 using namespace std; 106 107 const int N = int(3e5) + 99; 108 const int INF = int(1e9) + 99; 109 110 int t, n; 111 int a[N]; 112 int l[N], r[N]; 113 int dp[N]; 114 115 int main() { 116 scanf("%d", &t); 117 for(int tc = 0; tc < t; ++tc){ 118 scanf("%d", &n); 119 for(int i = 0; i < n; ++i){ 120 l[i] = INF; 121 r[i] = -INF; 122 dp[i] = 0; 123 } 124 125 vector <int> v; 126 for(int i = 0; i < n; ++i){ 127 scanf("%d", a + i); 128 --a[i]; 129 v.push_back(a[i]); 130 l[a[i]] = min(l[a[i]], i); 131 r[a[i]] = max(r[a[i]], i); 132 } 133 134 sort(v.begin(), v.end()); 135 v.erase(unique(v.begin(), v.end()), v.end()); 136 137 int res = n; 138 for(int i = v.size() - 1; i >= 0; --i){ 139 if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1; 140 else dp[i] = 1 + dp[i + 1]; 141 res = min(res, int(v.size())- dp[i]); 142 } 143 144 printf("%d\n", res); 145 } 146 147 return 0; 148 } 149 ``` 150 151 [1223E - Paint the Tree](/contest/1223/problem/E "Technocup 2020 - Elimination Round 1") 152 153 Idea: [Neon](/profile/Neon "Candidate Master Neon") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution (Ne0n25)** 160 161 ``` 162 #include <bits/stdc++.h> 163 164 using namespace std; 165 166 #define x first 167 #define y second 168 #define mp make_pair 169 #define pb push_back 170 #define sz(a) int((a).size()) 171 #define all(a) (a).begin(), (a).end() 172 #define forn(i, n) for (int i = 0; i < int(n); ++i) 173 174 const int N = 500 * 1000 + 13; 175 176 int n, k; 177 vector<pair<int, int>> g[N]; 178 long long dp[N][2]; 179 180 void calc(int v, int p = -1) { 181 long long cur = 0; 182 vector<long long> adds; 183 184 for (auto it : g[v]) { 185 int to = it.x; 186 int w = it.y; 187 if (to == p) 188 continue; 189 calc(to, v); 190 191 cur += dp[to][0]; 192 adds.pb(dp[to][1] + w - dp[to][0]); 193 } 194 195 sort(all(adds), greater<long long>()); 196 forn(i, min(sz(adds), k)) if (adds[i] > 0) 197 cur += adds[i]; 198 199 dp[v][0] = dp[v][1] = cur; 200 if (k <= sz(adds) && adds[k - 1] > 0) 201 dp[v][1] -= adds[k - 1]; 202 } 203 204 long long solve() { 205 scanf("%d%d", &n, &k); 206 forn(i, n) g[i].clear(); 207 forn(i, n - 1) { 208 int x, y, w; 209 scanf("%d%d%d", &x, &y, &w); 210 --x; --y; 211 g[x].pb(mp(y, w)); 212 g[y].pb(mp(x, w)); 213 } 214 215 calc(0); 216 217 return dp[0][0]; 218 } 219 220 int main() { 221 int q; 222 scanf("%d", &q); 223 forn(i, q) printf("%lld\n", solve()); 224 } 225 ``` 226 227 [1223F - Stack Exterminable Arrays](/contest/1223/problem/F "Technocup 2020 - Elimination Round 1") 228 229 Idea: [Roms](/profile/Roms "Master Roms") 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution (Roms)** 236 237 ``` 238 #include <bits/stdc++.h> 239 240 using namespace std; 241 242 const int N = int(3e5) + 99; 243 244 int t, n; 245 int a[N]; 246 int nxt[N]; 247 int dp[N]; 248 map<int, int> nxtX[N]; 249 250 int main() { 251 scanf("%d", &t); 252 for(int tc = 0; tc < t; ++tc){ 253 scanf("%d", &n); 254 for(int i = 0; i < n; ++i) 255 scanf("%d", a + i); 256 for(int i = 0; i < n + 2; ++i){ 257 nxt[i] = -1; 258 nxtX[i].clear(); 259 dp[i] = 0; 260 } 261 262 for(int i = n - 1; i >= 0; --i){ 263 if(nxtX[i + 1].count(a[i])){ 264 int pos = nxtX[i + 1][a[i]]; 265 assert(pos < n && a[pos] == a[i]); 266 nxt[i] = pos; 267 swap(nxtX[i], nxtX[pos + 1]); 268 if(pos < n - 1) 269 nxtX[i][a[pos + 1]] = pos + 1; 270 } 271 nxtX[i][a[i]] = i; 272 } 273 274 long long res = 0; 275 for(int i = n - 1; i >= 0; --i){ 276 if(nxt[i] == -1) continue; 277 dp[i] = 1 + dp[nxt[i] + 1]; 278 res += dp[i]; 279 } 280 281 printf("%lld\n", res); 282 } 283 return 0; 284 } 285 ``` 286 287 [1223G - Wooden Raft](/contest/1223/problem/G "Technocup 2020 - Elimination Round 1") 288 289 Idea: [adedalic](/profile/adedalic "International Master adedalic") 290 291 **Tutorial** 292 293 Tutorial is loading... 294 295 **Solution (adedalic)** 296 297 ``` 298 #include<bits/stdc++.h> 299 using namespace std; 300 301 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 302 #define sz(a) (int)(a).size() 303 #define all(a) (a).begin(), (a).end() 304 305 #define x first 306 #define y second 307 308 typedef long long li; 309 typedef pair<int, int> pt; 310 311 const int INF = int(1e9); 312 const li INF64 = li(1e18); 313 314 int n; 315 vector<int> a; 316 317 inline bool read() { 318 if(!(cin >> n)) 319 return false; 320 a.resize(n); 321 fore(i, 0, n) 322 cin >> a[i]; 323 return true; 324 } 325 326 template<class A> 327 pair<A, A> upd(const pair<A, A> &mx, const A &val) { 328 return {max(mx.x, val), max(mx.y, min(mx.x, val))}; 329 } 330 331 vector<int> cnt, sum; 332 vector<int> prv; 333 334 li getSum(int l, int r) { 335 return sum[r] - sum[l]; 336 } 337 338 li ans, rx, ry; 339 void updAns(li x, li y) { 340 if (x < 2 || y < 2) 341 return; 342 if (ans >= x * y) 343 return; 344 ans = x * y; 345 rx = x, ry = y; 346 } 347 348 inline void solve() { 349 cnt.assign(*max_element(all(a)) + 1, 0); 350 fore(i, 0, n) 351 cnt[a[i]]++; 352 sum.assign(sz(cnt) + 1, 0); 353 fore(i, 0, sz(cnt)) 354 sum[i + 1] = sum[i] + cnt[i]; 355 prv.assign(sz(cnt), -1); 356 fore(i, 0, sz(prv)) { 357 if(i > 0) 358 prv[i] = prv[i - 1]; 359 if(cnt[i] > 0) 360 prv[i] = i; 361 } 362 363 ans = 0; 364 fore(y, 2, sz(cnt)) { 365 li cntY = 0; 366 for(int i = 0; y * i < sz(cnt); i++) 367 cntY += i * 1ll * getSum(i * y, min((i + 1) * y, sz(cnt))); 368 369 pair<pt, pt> mx = {{-1, -1}, {-1, -1}}; 370 int lf = (sz(cnt) - 1) / y * y, rg = sz(cnt); 371 while(lf >= 0) { 372 int cntMore = (mx.x.x >= 0) + (mx.y.x >= 0); 373 int val1 = prv[rg - 1]; 374 if (val1 >= lf) { 375 mx = upd(mx, pt{val1 % y, val1}); 376 if (cnt[val1] == 1) 377 val1 = prv[val1 - 1]; 378 if (val1 >= lf) 379 mx = upd(mx, pt{val1 % y, val1}); 380 } 381 382 if (mx.x.x >= 0) { 383 li x = (lf + mx.x.x) / 2; 384 li cur = cntY - lf / y; 385 updAns(min(cur, x), y); 386 } 387 if (mx.y.x >= 0) { 388 li x = lf + mx.y.x; 389 li cur = cntY - 2 * (lf / y); 390 updAns(min(cur, x), y); 391 392 if(cntMore + (mx.x.y < rg) >= 2) { 393 x = lf + mx.x.x; 394 cur--; 395 updAns(min(cur, x), y); 396 } 397 } 398 399 rg = lf; 400 lf -= y; 401 } 402 } 403 cout << ans << endl; 404 cerr << rx << " " << ry << endl; 405 } 406 407 int main() { 408 #ifdef _DEBUG 409 freopen("input.txt", "r", stdin); 410 int tt = clock(); 411 #endif 412 ios_base::sync_with_stdio(0); 413 cin.tie(0), cout.tie(0); 414 cerr << fixed << setprecision(15); 415 416 if(read()) { 417 solve(); 418 419 #ifdef _DEBUG 420 cerr << "TIME = " << clock() - tt << endl; 421 tt = clock(); 422 #endif 423 } 424 return 0; 425 } 426 ``` 427 428 [1240F - Football](/contest/1240/problem/F "Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1)") 429 430 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 431 432 **Tutorial** 433 434 Tutorial is loading... 435 436 **Solution (arsijo)** 437 438 ``` 439 #include <bits/stdc++.h> 440 using namespace std; 441 typedef long long ll; 442 const int MAX_N = 101; 443 const int MAX_M = 1001; 444 445 int n, m, k; 446 447 vector<pair<int, int> > v[MAX_N]; 448 int w[MAX_N]; 449 int a[MAX_M], b[MAX_M], c[MAX_M], color[MAX_M]; 450 451 set<pair<int, int> > s[MAX_N], s2; 452 int deg[MAX_N][MAX_M]; 453 inline pair<int, int> get_s2(int i){ 454 return {s[i].begin()->first - s[i].rbegin()->first, i}; 455 } 456 inline void change_edge_color(int edge, int d){ 457 int pos1 = a[edge]; 458 int pos2 = b[edge]; 459 assert(s[pos1].find({deg[pos1][color[edge]], color[edge]}) != s[pos1].end()); 460 s[pos1].erase({deg[pos1][color[edge]], color[edge]}); 461 s[pos2].erase({deg[pos2][color[edge]], color[edge]}); 462 deg[pos1][color[edge]] += d; 463 deg[pos2][color[edge]] += d; 464 s[pos1].insert({deg[pos1][color[edge]], color[edge]}); 465 s[pos2].insert({deg[pos2][color[edge]], color[edge]}); 466 } 467 inline void change_color(int edge, int col){ 468 if (edge == 0 || edge > m || color[edge] == col) 469 return; 470 int pos1 = a[edge]; 471 int pos2 = b[edge]; 472 s2.erase(get_s2(pos1)); 473 s2.erase(get_s2(pos2)); 474 change_edge_color(edge, -1); 475 color[edge] = col; 476 change_edge_color(edge, 1); 477 s2.insert(get_s2(pos1)); 478 s2.insert(get_s2(pos2)); 479 } 480 481 vector<pair<int, int> > v2[MAX_N]; 482 int deg2[MAX_N]; 483 vector<int> vertices; 484 int used[MAX_N]; 485 void dfs2(int pos){ 486 used[pos] = 2; 487 for (auto e : v2[pos]){ 488 if (used[e.first] != 2){ 489 dfs2(e.first); 490 } 491 } 492 vertices.push_back(pos); 493 } 494 int _col[2]; 495 set<int> used3; 496 int i; 497 vector<int> euler; 498 void dfs3(int pos, int prev = -1, int pr2 = 0){ 499 while(!v2[pos].empty()){ 500 int ind = v2[pos].back().second; 501 int to = v2[pos].back().first; 502 v2[pos].pop_back(); 503 if (used3.find(ind) != used3.end()){ 504 continue; 505 } 506 used3.insert(ind); 507 dfs3(to, ind, pos); 508 } 509 if (prev != -1){ 510 euler.push_back(prev); 511 } 512 } 513 514 void stabilize_two_colors(const vector<int> &e, int col1, int col2){ 515 assert(!e.empty()); 516 v2[0].clear(); 517 for (auto edge : e){ 518 v2[a[edge]].clear(); 519 v2[b[edge]].clear(); 520 deg2[a[edge]] = 0; 521 deg2[b[edge]] = 0; 522 used[a[edge]] = 0; 523 used[b[edge]] = 0; 524 } 525 for (auto edge : e){ 526 v2[a[edge]].push_back({b[edge], edge}); 527 v2[b[edge]].push_back({a[edge], edge}); 528 } 529 vertices.clear(); 530 int u = m; 531 for (auto edge : e){ 532 if (used[a[edge]] != 2){ 533 int k = (int) vertices.size(); 534 dfs2(a[edge]); 535 bool find = false; 536 for (int i = k; i < (int) vertices.size(); i++){ 537 int v = vertices[i]; 538 if (v2[v].size() % 2 == 1){ 539 find = true; 540 ++u; 541 v2[v].push_back({0, u}); 542 v2[0].push_back({v, u}); 543 } 544 } 545 if (!find){ 546 int v = vertices[k]; 547 for (int j = 0; j < 2; j++){ 548 ++u; 549 v2[v].push_back({0, u}); 550 v2[0].push_back({v, u}); 551 } 552 } 553 } 554 } 555 used3.clear(); 556 euler.clear(); 557 dfs3(0); 558 for (int a : euler){ 559 change_color(a, col1); 560 swap(col1, col2); 561 } 562 } 563 564 void stabilize(const vector<int> &e){ 565 s2.clear(); 566 for (int i = 1; i <= n; i++){ 567 s[i].clear(); 568 for (int j = 1; j <= k; j++){ 569 deg[i][j] = 0; 570 } 571 } 572 for (int edge : e){ 573 deg[a[edge]][color[edge]]++; 574 deg[b[edge]][color[edge]]++; 575 } 576 for (int i = 1; i <= n; i++){ 577 for (int j = 1; j <= k; j++){ 578 s[i].insert({deg[i][j], j}); 579 } 580 s2.insert(get_s2(i)); 581 } 582 while(-s2.begin()->first > 2){ 583 584 int ind = s2.begin()->second; 585 int col1 = s[ind].begin()->second; 586 int col2 = s[ind].rbegin()->second; 587 vector<int> e2; 588 for (int edge : e){ 589 if (color[edge] == col1 || color[edge] == col2){ 590 e2.push_back(edge); 591 } 592 } 593 stabilize_two_colors(e2, col1, col2); 594 } 595 } 596 597 void make_random(vector<int> e){ 598 random_shuffle(e.begin(), e.end()); 599 for (int i = 0; i < (int) e.size(); i++){ 600 color[e[i]] = i % k + 1; 601 } 602 stabilize(e); 603 } 604 605 int change[MAX_N]; 606 607 void build(vector<int> e){ 608 if ((int) e.size() <= n * k){ 609 make_random(e); 610 return; 611 } 612 random_shuffle(e.begin(), e.end()); 613 vector<int> e1, e2; 614 int s = (int) e.size() / 2; 615 for (int i = 0; i < (int) e.size(); i++){ 616 if (i < s){ 617 e1.push_back(e[i]); 618 }else{ 619 e2.push_back(e[i]); 620 } 621 } 622 build(e1); 623 build(e2); 624 vector<pair<int, int> > v1(k), v2(k); 625 for (int i = 1; i <= k; i++){ 626 v1[i - 1].first = v2[i - 1].first = 0; 627 v1[i - 1].second = v2[i - 1].second = i; 628 } 629 for (int edge : e1){ 630 v1[color[edge] - 1].first++; 631 } 632 for (int edge : e2){ 633 v2[color[edge] - 1].first++; 634 } 635 sort(v1.rbegin(), v1.rend()); 636 sort(v2.begin(), v2.end()); 637 for (int i = 0; i < k; i++){ 638 change[v1[i].second] = i + 1; 639 } 640 for (int edge : e1){ 641 color[edge] = change[color[edge]]; 642 } 643 for (int i = 0; i < k; i++){ 644 change[v2[i].second] = i + 1; 645 } 646 for (int edge : e2){ 647 color[edge] = change[color[edge]]; 648 } 649 stabilize(e); 650 } 651 652 int main() { 653 ios_base::sync_with_stdio(0); 654 cin.tie(0); 655 cout.tie(0); 656 srand(time(NULL)); 657 #ifdef LOCAL 658 freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin); 659 #endif 660 661 cin >> n >> m >> k; 662 663 for (int i = 1; i <= n; i++){ 664 cin >> w[i]; 665 } 666 667 ll sum = 0; 668 vector<int> e; 669 for (int i = 1; i <= m; i++){ 670 cin >> a[i] >> b[i]; 671 sum += w[a[i]] + w[b[i]]; 672 e.push_back(i); 673 } 674 675 build(e); 676 677 for (int i = 1; i <= m; i++){ 678 assert(color[i]); 679 cout << color[i] << endl; 680 } 681 682 } 683 ```