1499.md (12737B)
1 Source: https://codeforces.com/blog/entry/88812 2 3 [1499A - Domino on Windowsill](/contest/1499/problem/A "Educational Codeforces Round 106 (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 (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() } 17 val (w, b) = readLine()!!.split(' ').map { it.toInt() } 18 19 if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b) 20 println("YES") 21 else 22 println("NO") 23 } 24 } 25 ``` 26 27 [1499B - Binary Removals](/contest/1499/problem/B "Educational Codeforces Round 106 (Rated for Div. 2)") 28 29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (Neon)** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 42 int main() { 43 int t; 44 cin >> t; 45 while (t--) { 46 string s; 47 cin >> s; 48 int i = s.find("11"); 49 int j = s.rfind("00"); 50 cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl; 51 } 52 } 53 ``` 54 55 [1499C - Minimum Grid Path](/contest/1499/problem/C "Educational Codeforces Round 106 (Rated for Div. 2)") 56 57 Idea: [adedalic](/profile/adedalic "International Master adedalic") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution (adedalic)** 64 65 ``` 66 fun main() { 67 repeat(readLine()!!.toInt()) { 68 val n = readLine()!!.toInt() 69 val c = readLine()!!.split(' ').map { it.toInt() } 70 71 val mn = intArrayOf(1e9.toInt(), 1e9.toInt()) 72 val rem = longArrayOf(n.toLong(), n.toLong()) 73 var sum = 0L 74 var ans = 1e18.toLong() 75 for (i in c.indices) { 76 mn[i % 2] = minOf(mn[i % 2], c[i]) 77 rem[i % 2]-- 78 sum += c[i] 79 if (i > 0) { 80 val cur = sum + rem[0] * mn[0] + rem[1] * mn[1] 81 ans = minOf(ans, cur) 82 } 83 } 84 println(ans) 85 } 86 } 87 ``` 88 89 [1499D - The Number of Pairs](/contest/1499/problem/D "Educational Codeforces Round 106 (Rated for Div. 2)") 90 91 Idea: [Neon](/profile/Neon "Candidate Master Neon") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution (Neon)** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 const int N = 2e7 + 13; 105 106 int main() { 107 vector<int> mind(N, -1), val(N); 108 mind[1] = 1; 109 for (int i = 2; i < N; ++i) if (mind[i] == -1) 110 for (int j = i; j < N; j += i) if (mind[j] == -1) 111 mind[j] = i; 112 for (int i = 2; i < N; ++i) { 113 int j = i / mind[i]; 114 val[i] = val[j] + (mind[i] != mind[j]); 115 } 116 int t; 117 scanf("%d", &t); 118 while (t--) { 119 int c, d, x; 120 scanf("%d%d%d", &c, &d, &x); 121 int ans = 0; 122 for (int i = 1; i * i <= x; ++i) { 123 if (x % i != 0) continue; 124 int k1 = x / i + d; 125 if (k1 % c == 0) ans += 1 << val[k1 / c]; 126 if (i * i == x) continue; 127 int k2 = i + d; 128 if (k2 % c == 0) ans += 1 << val[k2 / c]; 129 } 130 printf("%d\n", ans); 131 } 132 } 133 ``` 134 135 [1499E - Chaotic Merge](/contest/1499/problem/E "Educational Codeforces Round 106 (Rated for Div. 2)") 136 137 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 138 139 **Tutorial** 140 141 Tutorial is loading... 142 143 **Solution 1 (awoo)** 144 145 ``` 146 #include <bits/stdc++.h> 147 148 #define forn(i, n) for (int i = 0; i < int(n); i++) 149 150 using namespace std; 151 152 const int MOD = 998244353; 153 154 int add(int a, int b){ 155 a += b; 156 if (a >= MOD) 157 a -= MOD; 158 if (a < 0) 159 a += MOD; 160 return a; 161 } 162 163 int main() { 164 string s, t; 165 cin >> s >> t; 166 int n = s.size(), m = t.size(); 167 vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 0))); 168 int ans = 0; 169 forn(i, n + 1) forn(j, m + 1){ 170 if (i < n) dp[i + 1][j][0] = add(dp[i + 1][j][0], 1); 171 if (j < m) dp[i][j + 1][1] = add(dp[i][j + 1][1], 1); 172 if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][0]); 173 if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][1]); 174 if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][0]); 175 if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][1]); 176 ans = add(ans, dp[i][j][0]); 177 ans = add(ans, dp[i][j][1]); 178 } 179 forn(i, n){ 180 int j = i; 181 while (j + 1 < n && s[j] != s[j + 1]) ++j; 182 int len = j - i + 1; 183 int val = (len * 1ll * (len + 1) / 2) % MOD * (m + 1) % MOD; 184 ans = add(ans, -val); 185 i = j; 186 } 187 forn(i, m){ 188 int j = i; 189 while (j + 1 < m && t[j] != t[j + 1]) ++j; 190 int len = j - i + 1; 191 int val = (len * 1ll * (len + 1) / 2) % MOD * (n + 1) % MOD; 192 ans = add(ans, -val); 193 i = j; 194 } 195 printf("%d\n", ans); 196 return 0; 197 } 198 ``` 199 200 **Solution 2 (awoo)** 201 202 ``` 203 #include <bits/stdc++.h> 204 205 #define forn(i, n) for (int i = 0; i < int(n); i++) 206 207 using namespace std; 208 209 const int MOD = 998244353; 210 211 int add(int a, int b){ 212 a += b; 213 if (a >= MOD) 214 a -= MOD; 215 if (a < 0) 216 a += MOD; 217 return a; 218 } 219 220 int main() { 221 string s, t; 222 cin >> s >> t; 223 int n = s.size(), m = t.size(); 224 vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 0)))); 225 int ans = 0; 226 forn(i, n + 1) forn(j, m + 1){ 227 if (i < n) dp[i + 1][j][0][1] = add(dp[i + 1][j][0][1], 1); 228 if (j < m) dp[i][j + 1][1][2] = add(dp[i][j + 1][1][2], 1); 229 forn(mask, 4){ 230 if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][0][mask]); 231 if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][1][mask]); 232 if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][0][mask]); 233 if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][1][mask]); 234 } 235 ans = add(ans, dp[i][j][0][3]); 236 ans = add(ans, dp[i][j][1][3]); 237 } 238 printf("%d\n", ans); 239 return 0; 240 } 241 ``` 242 243 [1499F - Diameter Cuts](/contest/1499/problem/F "Educational Codeforces Round 106 (Rated for Div. 2)") 244 245 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 246 247 **Tutorial** 248 249 Tutorial is loading... 250 251 **Solution (awoo)** 252 253 ``` 254 #include <bits/stdc++.h> 255 256 #define forn(i, n) for (int i = 0; i < int(n); i++) 257 258 using namespace std; 259 260 const int MOD = 998244353; 261 262 int add(int a, int b){ 263 a += b; 264 if (a >= MOD) 265 a -= MOD; 266 if (a < 0) 267 a += MOD; 268 return a; 269 } 270 271 int mul(int a, int b){ 272 return a * 1ll * b % MOD; 273 } 274 275 int k; 276 vector<vector<int>> g; 277 vector<vector<int>> dp; 278 279 int dfs(int v, int p = -1){ 280 dp[v][0] = 1; 281 int h = 0; 282 for (int u : g[v]) if (u != p){ 283 int nh = dfs(u, v); 284 vector<int> tmp(max(h, nh + 1) + 1); 285 forn(i, h + 1) forn(j, nh + 1){ 286 if (i + j + 1 <= k) 287 tmp[max(i, j + 1)] = add(tmp[max(i, j + 1)], mul(dp[v][i], dp[u][j])); 288 if (i <= k && j <= k) 289 tmp[i] = add(tmp[i], mul(dp[v][i], dp[u][j])); 290 } 291 h = max(h, nh + 1); 292 forn(i, h + 1){ 293 dp[v][i] = tmp[i]; 294 } 295 } 296 return h; 297 } 298 299 int main() { 300 int n; 301 scanf("%d%d", &n, &k); 302 g.resize(n); 303 dp.resize(n, vector<int>(n, 0)); 304 forn(i, n - 1){ 305 int v, u; 306 scanf("%d%d", &v, &u); 307 --v, --u; 308 g[v].push_back(u); 309 g[u].push_back(v); 310 } 311 dfs(0); 312 int ans = 0; 313 forn(i, k + 1) ans = add(ans, dp[0][i]); 314 printf("%d\n", ans); 315 return 0; 316 } 317 ``` 318 319 [1499G - Graph Coloring](/contest/1499/problem/G "Educational Codeforces Round 106 (Rated for Div. 2)") 320 321 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 322 323 **Tutorial** 324 325 Tutorial is loading... 326 327 **Solution (BledDest)** 328 329 ``` 330 #include <bits/stdc++.h> 331 332 using namespace std; 333 334 const int MOD = 998244353; 335 const int N = 1000043; 336 337 int add(int x, int y) 338 { 339 x += y; 340 while(x >= MOD) x -= MOD; 341 while(x < 0) x += MOD; 342 return x; 343 } 344 345 int sub(int x, int y) 346 { 347 return add(x, -y); 348 } 349 350 int mul(int x, int y) 351 { 352 return (x * 1ll * y) % MOD; 353 } 354 355 int binpow(int x, int y) 356 { 357 int z = 1; 358 while(y > 0) 359 { 360 if(y % 2 == 1) 361 z = mul(z, x); 362 x = mul(x, x); 363 y /= 2; 364 } 365 return z; 366 } 367 368 int global_hash = 0; 369 370 void reverse(deque<pair<int, int>>& d) 371 { 372 stack<pair<int, int>> s; 373 while(!d.empty()) 374 { 375 s.push(d.back()); 376 d.pop_back(); 377 } 378 while(!s.empty()) 379 { 380 d.push_front(s.top()); 381 s.pop(); 382 } 383 } 384 385 void safe_push_front(deque<pair<int, int>>& d, int c, int& res) 386 { 387 int z = d.front().first ^ 1; 388 res = add(res, mul(binpow(2, c), z)); 389 d.push_front(make_pair(z, c)); 390 } 391 392 void safe_push_back(deque<pair<int, int>>& d, int c, int& res) 393 { 394 int z = d.back().first ^ 1; 395 res = add(res, mul(binpow(2, c), z)); 396 d.push_back(make_pair(z, c)); 397 } 398 399 deque<pair<int, int>> ds[N]; 400 401 struct path 402 { 403 int s; 404 int t; 405 int d; 406 int c; 407 408 path() {}; 409 path(int s, int t, int d, int c) : s(s), t(t), d(d), c(c) {}; 410 411 void push_front(int i) 412 { 413 safe_push_front(ds[d], i, c); 414 } 415 416 void push_back(int i) 417 { 418 safe_push_back(ds[d], i, c); 419 } 420 421 void pop_front() 422 { 423 ds[d].pop_front(); 424 } 425 426 void pop_back() 427 { 428 ds[d].pop_back(); 429 } 430 431 int front() 432 { 433 return ds[d].front().second; 434 } 435 436 int back() 437 { 438 return ds[d].back().second; 439 } 440 441 void reverse() 442 { 443 ::reverse(ds[d]); 444 swap(s, t); 445 } 446 447 int size() 448 { 449 return ds[d].size(); 450 } 451 }; 452 453 path link_to_left(path x, path y) 454 { 455 path z = x; 456 while(y.size() > 0) 457 { 458 z.push_back(y.front()); 459 y.pop_front(); 460 } 461 z.t = y.t; 462 return z; 463 } 464 465 path link_to_right(path x, path y) 466 { 467 path z = y; 468 while(x.size() > 0) 469 { 470 z.push_front(x.back()); 471 x.pop_back(); 472 } 473 z.s = x.s; 474 return z; 475 } 476 477 int cur = 0; 478 479 path make(int x, int y, int i) 480 { 481 int cost = i; 482 ds[cur].push_back(make_pair(0, cost)); 483 return path(x, y, cur++, 0); 484 } 485 486 set<int> paths; 487 vector<int> paths_v[N]; 488 path ps[N]; 489 490 path merge(path x, path y, int v) 491 { 492 if(x.size() > y.size()) 493 swap(x, y); 494 if(y.s == v) 495 { 496 if(x.t != v) 497 x.reverse(); 498 return link_to_right(x, y); 499 } 500 else 501 { 502 if(x.s != v) 503 x.reverse(); 504 return link_to_left(y, x); 505 } 506 } 507 508 int cur2 = 0; 509 510 void modify(vector<int>& v, int x, int y) 511 { 512 for(int i = 0; i < v.size(); i++) 513 if(v[i] == x) 514 v[i] = y; 515 } 516 517 void reassign(path p, int x, int y) 518 { 519 modify(paths_v[p.s], x, y); 520 modify(paths_v[p.t], x, y); 521 } 522 523 void merge_paths(int x, int y, int v) 524 { 525 if(x == y) 526 { 527 528 } 529 else 530 { 531 global_hash = sub(global_hash, ps[x].c); 532 global_hash = sub(global_hash, ps[y].c); 533 ps[cur2++] = merge(ps[x], ps[y], v); 534 paths.erase(x); 535 paths.erase(y); 536 paths.insert(cur2 - 1); 537 reassign(ps[x], x, cur2 - 1); 538 reassign(ps[y], y, cur2 - 1); 539 global_hash = add(global_hash, ps[cur2 - 1].c); 540 } 541 } 542 543 void relax(int v) 544 { 545 while(paths_v[v].size() >= 2) 546 { 547 int x = paths_v[v].back(); 548 paths_v[v].pop_back(); 549 int y = paths_v[v].back(); 550 paths_v[v].pop_back(); 551 merge_paths(x, y, v); 552 } 553 } 554 555 void add_edge(int x, int y, int i) 556 { 557 //cerr << x << " " << y << " " << i << endl; 558 int c = cur2; 559 ps[cur2++] = make(x, y, i); 560 paths_v[x].push_back(c); 561 paths_v[y].push_back(c); 562 paths.insert(c); 563 relax(x); 564 relax(y); 565 } 566 567 void print_coloring() 568 { 569 vector<int> ans; 570 for(auto x : paths) 571 { 572 for(auto y : ds[ps[x].d]) 573 { 574 if(y.first == 1) 575 ans.push_back(y.second); 576 } 577 } 578 printf("%d", int(ans.size())); 579 for(auto x : ans) 580 printf(" %d", x); 581 puts(""); 582 fflush(stdout); 583 } 584 585 int e = 0; 586 587 void process_query() 588 { 589 int t; 590 scanf("%d", &t); 591 if(t == 1) 592 { 593 int x, y; 594 scanf("%d %d", &x, &y); 595 y += 200001; 596 add_edge(x, y, ++e); 597 printf("%d\n", global_hash); 598 fflush(stdout); 599 } 600 else 601 print_coloring(); 602 } 603 604 void print_info() 605 { 606 cerr << "Paths\n"; 607 for(auto x : paths) 608 cerr << x << " start: " << ps[x].s << " " << " end: " << ps[x].t << endl; 609 cerr << "Vertices\n"; 610 for(int i = 0; i < N; i++) 611 if(!paths_v[i].empty()) 612 { 613 cerr << i << ": "; 614 for(auto x : paths_v[i]) 615 cerr << x << " "; 616 cerr << endl; 617 } 618 619 } 620 621 int main() 622 { 623 int n1, n2, m; 624 scanf("%d %d %d", &n1, &n2, &m); 625 for(int i = 0; i < m; i++) 626 { 627 int x, y; 628 scanf("%d %d", &x, &y); 629 y += 200001; 630 add_edge(x, y, ++e); 631 } 632 int q; 633 scanf("%d", &q); 634 for(int i = 0; i < q; i++) 635 { 636 //print_info(); 637 process_query(); 638 } 639 } 640 ```