codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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() &mdash; '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 \(^ ^)/