814.md (15853B)
1 Source: https://codeforces.com/blog/entry/52449 2 3 Greetings! 4 5 [Codeforces Round 418 (Div. 2)](/contest/814 "Codeforces Round 418 (Div. 2)") has just come to an end. This is my first round here, and hope you all enjoyed the contest! > < 6 7 Seems the statements still created a few issues :( Anyway hope you liked it, and the characters feature the *Monogatari* anime series. Let me state again that the statements has little to do with the actual plot — they're inspired by five theme songs actually — and I'm *not* spoiling anyone of the series! ^ ^ 8 9 Sympathy for those failing system tests on B... This problem was intended to experience a lot of hacks but somehow there are not so many. 10 11 Here are the detailed solutions to the problems. Feel free to write in the comments if there's anything incorrect or unclear. 12 13 Tutorial is loading... 14 15 **Solution 1** 16 17 ``` 18 #include <cstdio> 19 static const int MAXN = 102; 20 21 int n, k; 22 int a[MAXN], b[MAXN]; 23 24 int main() 25 { 26 scanf("%d%d", &n, &k); 27 int last_zero = -1; 28 for (int i = 0; i < n; ++i) { 29 scanf("%d", &a[i]); 30 if (a[i] == 0) last_zero = i; 31 } 32 for (int i = 0; i < k; ++i) scanf("%d", &b[i]); 33 34 if (k > 1) { 35 puts("Yes"); 36 } else { 37 a[last_zero] = b[0]; 38 bool valid = false; 39 for (int i = 1; i < n; ++i) 40 if (a[i] <= a[i - 1]) { valid = true; break; } 41 puts(valid ? "Yes" : "No"); 42 } 43 44 return 0; 45 } 46 ``` 47 48 **Solution 2** 49 50 ``` 51 #include <cstdio> 52 #include <algorithm> 53 static const int MAXN = 102; 54 55 int n, k; 56 int a[MAXN], b[MAXN]; 57 int p[MAXN], r[MAXN]; 58 59 inline bool check() 60 { 61 for (int i = 1; i < n; ++i) if (r[i] <= r[i - 1]) return true; 62 return false; 63 } 64 65 int main() 66 { 67 scanf("%d%d", &n, &k); 68 int last_zero = -1; 69 for (int i = 0; i < n; ++i) { 70 scanf("%d", &a[i]); 71 if (a[i] == 0) last_zero = i; 72 } 73 for (int i = 0; i < k; ++i) scanf("%d", &b[i]); 74 75 bool valid = false; 76 for (int i = 0; i < k; ++i) p[i] = i; 77 do { 78 for (int i = 0, ptr = 0; i < n; ++i) { 79 r[i] = (a[i] == 0) ? b[p[ptr++]] : a[i]; 80 } 81 if (check()) { valid = true; break; } 82 } while (std::next_permutation(p, p + k)); 83 puts(valid ? "Yes" : "No"); 84 85 return 0; 86 } 87 ``` 88 89 Tutorial is loading... 90 91 **Solution 1** 92 93 ``` 94 #include <cstdio> 95 #include <cstring> 96 static const int MAXN = 1e3 + 4; 97 98 int n; 99 int a[MAXN], b[MAXN]; 100 int pa[2][MAXN], pb[2][MAXN]; 101 102 inline void try_recover(int *a, int *p1, int *p2) 103 { 104 int dup_ct = 0; 105 int dup1 = -1, dup2 = -1, absent = -1; 106 for (int i = 0; i < n; ++i) 107 for (int j = i + 1; j < n; ++j) 108 if (a[i] == a[j]) dup1 = i, dup2 = j; 109 for (absent = 1; absent <= n; ++absent) { 110 bool occurred = false; 111 for (int i = 0; i < n; ++i) if (a[i] == absent) { occurred = true; break; } 112 if (!occurred) break; 113 } 114 115 memcpy(p1, a, n * sizeof(int)); 116 memcpy(p2, a, n * sizeof(int)); 117 p1[dup1] = absent; 118 p2[dup2] = absent; 119 } 120 121 int main() 122 { 123 scanf("%d", &n); 124 for (int i = 0; i < n; ++i) scanf("%d", &a[i]); 125 for (int i = 0; i < n; ++i) scanf("%d", &b[i]); 126 127 try_recover(a, pa[0], pa[1]); 128 try_recover(b, pb[0], pb[1]); 129 int *ans = NULL; 130 if (memcmp(pa[0], pb[0], n * sizeof(int)) == 0 || memcmp(pa[0], pb[1], n * sizeof(int)) == 0) 131 ans = pa[0]; 132 else ans = pa[1]; 133 134 for (int i = 0; i < n; ++i) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' '); 135 136 return 0; 137 } 138 ``` 139 140 **Solution 2 - Casework** 141 142 ``` 143 #include <cstdio> 144 #include <utility> 145 static const int MAXN = 1e3 + 4; 146 147 int n; 148 int a[MAXN], b[MAXN]; 149 150 std::pair<int, int> get_duplication(int *a) 151 { 152 static int occ[MAXN]; 153 for (int i = 1; i <= n; ++i) occ[i] = -1; 154 for (int i = 0; i < n; ++i) { 155 if (occ[a[i]] != -1) return std::make_pair(occ[a[i]], i); 156 else occ[a[i]] = i; 157 } 158 return std::make_pair(-1, -1); 159 } 160 161 inline void fix_permutation(int pos) 162 { 163 static bool occ[MAXN]; 164 for (int i = 1; i <= n; ++i) occ[i] = false; 165 for (int i = 0; i < n; ++i) if (i != pos) occ[a[i]] = true; 166 for (int i = 1; i <= n; ++i) if (!occ[i]) { a[pos] = i; return; } 167 } 168 169 int main() 170 { 171 scanf("%d", &n); 172 for (int i = 0; i < n; ++i) scanf("%d", &a[i]); 173 for (int i = 0; i < n; ++i) scanf("%d", &b[i]); 174 175 std::pair<int, int> dup_a, dup_b; 176 dup_a = get_duplication(a); 177 dup_b = get_duplication(b); 178 179 if (dup_a == dup_b) { 180 a[dup_a.first] = b[dup_b.first]; 181 } else if (dup_a.first == dup_b.first || dup_a.first == dup_b.second) { 182 a[dup_a.second] = b[dup_a.second]; 183 fix_permutation(dup_a.first); 184 } else if (dup_a.second == dup_b.first || dup_a.second == dup_b.second) { 185 a[dup_a.first] = b[dup_a.first]; 186 fix_permutation(dup_a.second); 187 } else { 188 a[dup_a.first] = b[dup_a.first]; 189 a[dup_a.second] = b[dup_a.second]; 190 } 191 192 for (int i = 0; i < n; ++i) printf("%d%c", a[i], i == n - 1 ? '\n' : ' '); 193 194 return 0; 195 } 196 ``` 197 198 Tutorial is loading... 199 200 **Solution** 201 202 ``` 203 #include <cstdio> 204 #include <algorithm> 205 static const int MAXN = 1502; 206 static const int ALPHABET = 26; 207 208 int n; 209 char s[MAXN]; 210 int ans[ALPHABET][MAXN] = {{ 0 }}; 211 int q, m_i; 212 char c_i; 213 214 int main() 215 { 216 scanf("%d", &n); getchar(); 217 for (int i = 0; i < n; ++i) s[i] = getchar() — 'a'; 218 219 for (char c = 0; c < ALPHABET; ++c) { 220 for (int i = 0; i < n; ++i) { 221 int replace_ct = 0; 222 for (int j = i; j < n; ++j) { 223 if (s[j] != c) ++replace_ct; 224 ans[c][replace_ct] = std::max(ans[c][replace_ct], j - i + 1); 225 } 226 } 227 for (int i = 1; i < MAXN; ++i) 228 ans[c][i] = std::max(ans[c][i], ans[c][i - 1]); 229 } 230 231 scanf("%d", &q); 232 for (int i = 0; i < q; ++i) { 233 scanf("%d %c", &m_i, &c_i); 234 printf("%d\n", ans[c_i - 'a'][m_i]); 235 } 236 237 return 0; 238 } 239 ``` 240 241 Tutorial is loading... 242 243 **Solution 1 - DP on trees** 244 245 ``` 246 #include <cstdio> 247 #include <cmath> 248 #include <algorithm> 249 #include <vector> 250 typedef long long int64; 251 static const int MAXN = 1004; 252 #ifndef M_PI 253 static const double M_PI = acos(-1.0); 254 #endif 255 256 int n; 257 int x[MAXN], y[MAXN], r[MAXN]; 258 int par[MAXN]; 259 std::vector<int> e[MAXN]; 260 261 // Whether one of C[u] and C[v] is contained in another 262 inline bool circle_contains(int u, int v) 263 { 264 return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v])); 265 } 266 267 int64 f[MAXN][2][2]; 268 269 void dfs_dp(int u) 270 { 271 int64 g[2][2] = {{ 0 }}; 272 for (int v : e[u]) { 273 dfs_dp(v); 274 for (int i = 0; i <= 1; ++i) 275 for (int j = 0; j <= 1; ++j) 276 g[i][j] += f[v][i][j]; 277 } 278 for (int i = 0; i <= 1; ++i) 279 for (int j = 0; j <= 1; ++j) { 280 f[u][i][j] = std::max( 281 // (1) <u> is assigned to the first group 282 g[i ^ 1][j] + (int64)r[u] * r[u] * (i == 0 ? +1 : -1), 283 // (2) <u> is assigned to the second group 284 g[i][j ^ 1] + (int64)r[u] * r[u] * (j == 0 ? +1 : -1) 285 ); 286 } 287 } 288 289 int main() 290 { 291 scanf("%d", &n); 292 for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]); 293 294 for (int i = 0; i < n; ++i) { 295 par[i] = -1; 296 for (int j = 0; j < n; ++j) 297 if (r[j] > r[i] && circle_contains(i, j)) { 298 if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j; 299 } 300 e[par[i]].push_back(i); 301 } 302 303 int64 ans = 0; 304 for (int i = 0; i < n; ++i) if (par[i] == -1) { 305 dfs_dp(i); 306 ans += f[i][0][0]; 307 } 308 printf("%.8lf\n", (double)ans * M_PI); 309 310 return 0; 311 } 312 ``` 313 314 **Solution 2 - Greedy** 315 316 ``` 317 #include <cstdio> 318 #include <cmath> 319 #include <algorithm> 320 #include <vector> 321 typedef long long int64; 322 static const int MAXN = 1004; 323 #ifndef M_PI 324 static const double M_PI = acos(-1.0); 325 #endif 326 327 int n; 328 int x[MAXN], y[MAXN], r[MAXN]; 329 int par[MAXN]; 330 std::vector<int> e[MAXN]; 331 332 bool level[MAXN]; 333 334 // Whether one of C[u] and C[v] is contained in another 335 inline bool circle_contains(int u, int v) 336 { 337 return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v])); 338 } 339 340 void dfs_colour(int u, bool c) 341 { 342 level[u] = c; 343 for (int v : e[u]) dfs_colour(v, c ^ 1); 344 } 345 346 int main() 347 { 348 scanf("%d", &n); 349 for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]); 350 351 for (int i = 0; i < n; ++i) { 352 par[i] = -1; 353 for (int j = 0; j < n; ++j) 354 if (r[j] > r[i] && circle_contains(i, j)) { 355 if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j; 356 } 357 e[par[i]].push_back(i); 358 } 359 360 for (int i = 0; i < n; ++i) if (par[i] == -1) dfs_colour(i, false); 361 int64 ans = 0; 362 for (int i = 0; i < n; ++i) 363 ans += (int64)r[i] * r[i] * (par[i] == -1 || (level[i] == true) ? +1 : -1); 364 printf("%.8lf\n", (double)ans * M_PI); 365 366 return 0; 367 } 368 ``` 369 370 One more thing — Staying up late is bad for health. 371 372 Tutorial is loading... 373 374 **Solution 1 - O(n^5)** 375 376 ``` 377 #include <cstdio> 378 #include <cstring> 379 typedef long long int64; 380 static const int MAXN = 52; 381 static const int MODULUS = 1e9 + 7; 382 #define _ % MODULUS 383 #define __ %= MODULUS 384 385 int n, d[MAXN]; 386 int64 f[2][MAXN][MAXN][MAXN][MAXN] = {{{{{ 0 }}}}}; 387 388 int main() 389 { 390 scanf("%d", &n); 391 for (int i = 0; i < n; ++i) scanf("%d", &d[i]); 392 393 int cur = 0, next = 1; 394 f[cur][d[0] == 2][d[0] == 3][d[1] == 2][d[1] == 3] = 1; 395 for (int i = 1; i < n - 1; ++i) { 396 memset(f[next], 0, sizeof f[next]); 397 for (int p1 = 0; p1 <= n; ++p1) 398 for (int p2 = 0; p1 + p2 <= n; ++p2) 399 for (int c1 = 0; c1 + p1 + p2 <= n; ++c1) 400 for (int c2 = 0; c1 + c2 + p1 + p2 <= n; ++c2) if (f[cur][p1][p2][c1][c2] > 0) { 401 int64 val = f[cur][p1][p2][c1][c2]; 402 // (1) Start a new level 403 if (p1 == 0 && p2 == 0) { 404 (f[cur][c1][c2][0][0] += val)__; 405 continue; 406 } 407 // (2) Stay on current level 408 // Which type of vertex in the last level? 409 for (int last_level = 0; last_level <= 1; ++last_level) { 410 int last_ways; 411 if (last_level == 0) { 412 last_ways = p1; 413 if (--p1 < 0) { ++p1; continue; } 414 } else { 415 last_ways = p2; 416 if (--p2 < 0) { ++p2; continue; } else ++p1; 417 } 418 // Which type of vertices in the current level? 419 if (d[i + 1] == 2) { 420 // a) Leave as it is 421 (f[next][p1][p2][c1 + 1][c2] += val * last_ways)__; 422 // b) 1-plug 423 if (c1 >= 1) 424 (f[next][p1][p2][c1 - 1][c2] += val * last_ways * c1)__; 425 // c) 2-plug 426 if (c2 >= 1) 427 (f[next][p1][p2][c1 + 1][c2 - 1] += val * last_ways * c2)__; 428 } else { 429 // a) Leave as it is 430 (f[next][p1][p2][c1][c2 + 1] += val * last_ways)__; 431 // b) 1-plug 432 if (c1 >= 1) 433 (f[next][p1][p2][c1][c2] += val * last_ways * c1)__; 434 // c) 2-plug 435 if (c2 >= 1) 436 (f[next][p1][p2][c1 + 2][c2 - 1] += val * last_ways * c2)__; 437 // d) 1-plug + 1-plug 438 if (c1 >= 2) 439 (f[next][p1][p2][c1 - 2][c2] += val * last_ways * c1 * (c1 - 1) / 2)__; 440 // e) 2-plug + 2-plug 441 if (c2 >= 2) 442 (f[next][p1][p2][c1 + 2][c2 - 2] += val * last_ways * c2 * (c2 - 1) / 2)__; 443 // f) 1-plug + 2-plug 444 if (c1 >= 1 && c2 >= 1) 445 (f[next][p1][p2][c1][c2 - 1] += val * last_ways * c1 * c2)__; 446 } 447 if (last_level == 0) ++p1; else ++p2, --p1; 448 } 449 } 450 cur ^= 1, next ^= 1; 451 } 452 453 printf("%lld\n", f[cur][0][0][0][0]); 454 return 0; 455 } 456 ``` 457 458 **Solution 2 - O(n^3) by KAN** 459 460 ``` 461 #include <bits/stdc++.h> 462 463 using namespace std; 464 465 using ll = long long; 466 using ld = long double; 467 using D = double; 468 using uint = unsigned int; 469 template<typename T> 470 using pair2 = pair<T, T>; 471 472 #ifdef WIN32 473 #define LLD "%I64d" 474 #else 475 #define LLD "%lld" 476 #endif 477 478 #define pb push_back 479 #define mp make_pair 480 #define all(x) (x).begin(),(x).end() 481 #define fi first 482 #define se second 483 484 const int maxn = 55; 485 const int MOD = 1000000007; 486 487 int ways[maxn][maxn][maxn]; 488 int answer[maxn][maxn]; 489 int n; 490 int d[maxn]; 491 int sumd[maxn]; 492 493 inline void add(int &a, ll b) 494 { 495 a = (a + b) % MOD; 496 } 497 498 int main() 499 { 500 scanf("%d", &n); 501 for (int i = 0; i < n; i++) scanf("%d", &d[i]); 502 503 ways[0][0][0] = 1; 504 for (int c0 = 0; c0 <= n; c0++) 505 { 506 for (int c2 = 0; c2 <= n; c2++) 507 { 508 for (int c1 = 0; c1 <= n; c1++) if (c1 + c2 > 0) 509 { 510 if (c2 > 0) 511 { 512 if (c0 > 1) add(ways[c0][c1][c2], (ll)ways[c0 - 2][c1][c2 - 1] * (c0 * (c0 - 1) / 2)); // 2-0, 2-0 513 if (c2 > 1 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 + 1][c2 - 2] * (c2 - 1) * c0); // 2-2, 2-0 514 if (c2 > 2) add(ways[c0][c1][c2], (ll)ways[c0][c1 + 2][c2 - 3] * ((c2 - 1) * (c2 - 2) / 2)); // 2-2, 2-2 515 if (c1 > 0 && c2 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1][c2 - 2] * c1 * (c2 - 1)); // 2-2, 2-1 516 if (c1 > 0 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 - 1][c2 - 1] * c1 * c0); // 2-1, 2-0 517 if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2 - 1] * (c1 * (c1 - 1) / 2)); // 2-1, 2-1 518 } else 519 { 520 if (c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 - 1][c2] * c0); // 1-0 521 if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2] * (c1 - 1)); // 1-1 522 } 523 } 524 } 525 } 526 527 for (int i = 0; i < n; i++) sumd[i + 1] = sumd[i] + d[i]; 528 answer[n][n - 1] = 1; 529 for (int l = n - 1; l > 0; l--) 530 { 531 for (int r = l; r < n; r++) 532 { 533 int cnt2 = sumd[r + 1] - sumd[l] - 2 * (r - l + 1); 534 int cnt1 = r - l + 1 - cnt2; 535 for (int nextlvl = 0; nextlvl <= 2 * cnt2 + cnt1 && nextlvl <= n; nextlvl++) 536 { 537 int curways = ways[nextlvl][cnt1][cnt2]; 538 if (r + nextlvl < n) 539 { 540 add(answer[l][r], (ll)answer[r + 1][r + nextlvl] * curways); 541 } 542 } 543 } 544 } 545 if (d[0] + 1 > n) cout << 0 << endl; 546 else cout << answer[1][d[0]] << endl; 547 return 0; 548 } 549 ``` 550 551 This is the round with the most solutions so far perhaps? There are at least 3 × 2 × 3 × 3 × 3 = 162 different ways to pass all problems in this round =D 552 553 > Pla-tinum happy though I'm supposed to be 554 > Pla-tinum sad is somehow how I get 555 556 Personally I'd like to express my gratitude to the community for creating this amazing first-time experience for me. Thank you, and see you next round. Probably it will be for Ha... Well, let's wait and see :) 557 558 Cheers \(^ ^)/