codeforces-scrape

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

979.md (13802B)


      1 Source: https://codeforces.com/blog/entry/59462
      2 
      3 Hi Codeforces!
      4 
      5 This is the editorial of [Codeforces Round 482 (Div. 2)](/contest/979 "Codeforces Round 482 (Div. 2)"). I hope you guys enjoy it.
      6 
      7 [979A - Pizza, Pizza, Pizza!!!](/contest/979/problem/A "Codeforces Round 482 (Div. 2)")
      8 
      9 **Solution**
     10 
     11 If *n* = 0, the answer is obviously 0.
     12 
     13 If *n* + 1 is even, we can make ![](https://espresso.codeforces.com/58ff79481c949c0496c14ec947bef009a4cea392.png) diametric cuts. Otherwise, the only way is to make *n* + 1 cuts.
     14 
     15 Time complexity: *O*(1).
     16 
     17 **Code**
     18 
     19 ```
     20 #include <stdio.h>
     21 using namespace std;
     22 
     23 long long n;
     24 
     25 int main()
     26 {
     27     scanf("%I64d", &n);
     28     n++;
     29     if (n == 1) printf("0"); else if (n % 2 == 0) printf("%I64d", n / 2); else printf("%I64d", n);
     30     return 0;
     31 }
     32 ```
     33 
     34 [979B - Treasure Hunt](/contest/979/problem/B "Codeforces Round 482 (Div. 2)")
     35 
     36 **Solution**
     37 
     38 We all knew that the substrings with length 1 appear at most in the string. So, to make a string as beautiful as possible, we will choose the letter that firstly appears at most in the string and replace all the other letters with the chosen letter.
     39 
     40 There is some cases. If *n* is less than or equal to the number of remaining letters, just add *n* to the beauty. If *n* is even after replacing all letters with the chosen, we can choose an arbitrary letter, replace it with some other letter, return it back and repeat the work till *n* reach 0. Otherwise, we will not replace all the other letters. Instead, we will replace the letters until there is 1 letter left (now *n* is even) then replace that one with another letter different from our chosen letter. After that, replace that letter with our chosen letter. Now *n* is even again, we repeat the work discussed above.
     41 
     42 In conclusion, let's call our string *s*, our chosen letter *a* and its number of occurrences in the string *f**a*, then our answer is *min*(*f**a* + *n*, |*s*|). Be careful with *n* = 1.
     43 
     44 Time complexity: ![](https://espresso.codeforces.com/2d71f72cab00a1537c14cf4a6692d1dff1fa49fe.png), where ![](https://espresso.codeforces.com/0907eeb5f0e1833e4e25abe634fb3fa14557996a.png) is the total length of the three strings.
     45 
     46 **Code**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int a[256], b[256], c[256], n, ma, mb, mc;
     54 string p, q, r;
     55 
     56 int main() {
     57       cin >> n >> p >> q >> r;
     58       for (char x: p) ma = max(ma, ++a[x]);
     59       for (char x: q) mb = max(mb, ++b[x]);
     60       for (char x: r) mc = max(mc, ++c[x]);
     61       if (n == 1 && ma == (int)p.length()) p.pop_back();
     62       if (n == 1 && mb == (int)q.length()) q.pop_back();
     63       if (n == 1 && mc == (int)r.length()) r.pop_back();
     64       ma = min(ma + n, (int)p.length());
     65       mb = min(mb + n, (int)q.length());
     66       mc = min(mc + n, (int)r.length());
     67       if (ma > mb && ma > mc) {
     68             puts("Kuro");
     69             return 0;
     70       }
     71       if (mb > ma && mb > mc) {
     72             puts("Shiro");
     73             return 0;
     74       }
     75       if (mc > ma && mc > mb) {
     76             puts("Katie");
     77             return 0;
     78       }
     79       puts("Draw");
     80       return 0;
     81 }
     82 ```
     83 
     84 [979C - Kuro and Walking Route](/contest/979/problem/C "Codeforces Round 482 (Div. 2)")
     85 
     86 **Solution**
     87 
     88 We can consider the city as a graph, in which every town is a vertex and every road connecting two towns is an edge. Since *m* < *n*, we can deduce that this graph is a tree. Now, instead of finding the number of pairs that Kuro can choose, we can find the number of pairs that Kuro cannot choose. In other words, we must find the number of pairs of vertices (*u*, *v*), in which the shortest path from *u* to *v* passes through *x* and then through *y*. But how can we do this?
     89 
     90 If we take vertex *y* as the root of the tree, we can see that every pair of vertices that Kuro cannot choose begins from any node within the subtree of node *x*, and finishes at any node but within the subtree of node *z*, which *z* is a direct child of *y* lying on the shortest path from *x* to *y*. In total, the number of pairs of vertices that we are looking for is equal of *n*·(*n* - 1) - *s*[*x*]·(*s*[*y*] - *s*[*z*]), which *s*[*i*] denotes the size of the subtree of node *i*. We can implement this using simple DFS.
     91 
     92 Time complexity: *O*(*n*).
     93 
     94 **Code**
     95 
     96 ```
     97 #include <iostream>
     98 #include <cstdio>
     99 #include <vector>
    100 using namespace std;
    101 
    102 const int MAXN = 3e5;
    103 
    104 int n, m, u, v, x, y, sub_size[MAXN + 5];
    105 bool vis[MAXN + 5], chk_sub[MAXN + 5];
    106 vector<int> adj[MAXN + 5];
    107 
    108 int DFS(int u)
    109 {
    110     vis[u] = true; sub_size[u] = 1;
    111     if (u == x)
    112         chk_sub[u] = true;
    113     else chk_sub[u] = false;
    114     for (int v: adj[u])
    115         if (!vis[v])
    116         {
    117             sub_size[u] += DFS(v);
    118             chk_sub[u] |= chk_sub[v];
    119         }
    120     return sub_size[u];
    121 }
    122 
    123 int main()
    124 {
    125     scanf("%d%d%d", &n, &x, &y);
    126     m = n - 1;
    127     while (m--)
    128     {
    129         scanf("%d%d", &u, &v);
    130         adj[u].push_back(v);
    131         adj[v].push_back(u);
    132     }
    133     DFS(y);
    134 
    135     long long fin;
    136     for (int v: adj[y])
    137         if (chk_sub[v])
    138         {
    139             fin = sub_size[y] - sub_size[v];
    140             break;
    141         }
    142 
    143     printf("%I64d", 1LL * n * (n - 1) - fin * sub_size[x]);
    144     return 0;
    145 }
    146 ```
    147 
    148 [979D - Kuro and GCD and XOR and SUM](/contest/979/problem/D "Codeforces Round 482 (Div. 2)")
    149 
    150 **Solution**
    151 
    152 We first look at the condition ![](https://espresso.codeforces.com/8448124bb2c378361a30edba7f806ea69e310f0a.png). This condition holds iff both *x**i* and *v* are divisible by *k**i*. Therefore, if ![](https://espresso.codeforces.com/46a6fca7e5068c1380c743ae9417e2cadf7a92c6.png), we return `-1` immediately, else we only consider numbers in *a* that are divisible by *k**i*.
    153 
    154 Finding the maximum XOR of *x**i* with *v* in the array *a* reminds us of a classic problem, where the data structure trie is used to descend from the higher bit positions to the lower bit positions. But since we only consider *v* such that ![](https://espresso.codeforces.com/691659440ddcb5cf92521af9c976d1c9f630b9b9.png) and *x**i* + *v* ≤ *s**i*, we build 105 tries, where the *i**th* trie holds information of numbers in *a* that are divisible by *i*, and we only descend to a branch in the trie if the branch is not empty and the minimum value in the branch is  ≤ *s**i* - *x**i*.
    155 
    156 Adding a number into *a* is trivial by now: we update every *u**th* trie where *u* divides the number we need to add into the array. Notice that we only add a number if the number doesn't exist in the array yet.
    157 
    158 Time complexity: *O*(*MAXlog*(*MAX*) + *qlog*(*MAX*)2).
    159 
    160 **Code**
    161 
    162 ```
    163 #include <iostream>
    164 #include <cstdio>
    165 #include <vector>
    166 using namespace std;
    167 
    168 const int MAX = 1E5 + 5;
    169 
    170 struct SNode
    171 {
    172     int mi;
    173     SNode *bit[2];
    174 
    175     SNode()
    176     {
    177         mi = MAX;
    178         bit[0] = bit[1] = nullptr;
    179     }
    180 } *rt[MAX];
    181 vector<int> di[MAX];
    182 int q, t, u, k, x, s;
    183 bool chk[MAX];
    184 
    185 void init()
    186 {
    187     for (int i = 1; i < MAX; i++)
    188     {
    189         for (int j = i; j < MAX; j += i)
    190             di[j].push_back(i);
    191         rt[i] = new SNode();
    192     }
    193 }
    194 
    195 void add(int k, int u)
    196 {
    197     SNode *cur = rt[k];
    198     cur->mi = min(cur->mi, u);
    199     for (int i = 18; i >= 0; i--)
    200     {
    201         if (cur->bit[u >> i & 1] == nullptr)
    202             cur->bit[u >> i & 1] = new SNode();
    203         cur = cur->bit[u >> i & 1];
    204         cur->mi = min(cur->mi, u);
    205     }
    206 }
    207 
    208 int que(int x, int k, int s)
    209 {
    210     SNode *cur = rt[k];
    211     if (x % k != 0 || cur->mi + x > s)
    212         return -1;
    213     int ret = 0;
    214     for (int i = 18; i >= 0; i--)
    215     {
    216         int bi = x >> i & 1;
    217         if (cur->bit[bi ^ 1] != nullptr && cur->bit[bi ^ 1]->mi + x <= s)
    218         {
    219             ret += ((bi ^ 1) << i);
    220             cur = cur->bit[bi ^ 1];
    221         }
    222         else
    223         {
    224             ret += (bi << i);
    225             cur = cur->bit[bi];
    226         }
    227     }
    228     return ret;
    229 }
    230 
    231 int main()
    232 {
    233     init();
    234     scanf("%d", &q);
    235     while (q--)
    236     {
    237         scanf("%d", &t);
    238         if (t == 1)
    239         {
    240             scanf("%d", &u);
    241             if (!chk[u])
    242             {
    243                 chk[u] = true;
    244                 for (int k : di[u])
    245                     add(k, u);
    246             }
    247         }
    248         else
    249         {
    250             scanf("%d%d%d", &x, &k, &s);
    251             printf("%d\n", que(x, k, s));
    252         }
    253     }
    254     return 0;
    255 }
    256 ```
    257 
    258 [979E - Kuro and Topological Parity](/contest/979/problem/E "Codeforces Round 482 (Div. 2)")
    259 
    260 **Solution**
    261 
    262 The problem asks us to find the number of different simple directed acyclic graphs with 1 → *n* forming its topological order to ensure the parity of the number of alternating paths to be equal to *p*. We will solve this problem using the dynamic programming approach.
    263 
    264 Let's define **even-white** as the number of different nodes *u* colored in white that has an even number of alternating paths that end in *u*. In the same fashion, let's define **odd-white** as the number of different nodes *u* colored in white that has an odd number of alternating paths that end in *u*, **even-black** — the number of different nodes *u* colored in black that has an even number of alternating paths that end in *u*, and **odd-black** — the number of different nodes *u* colored in black that has an odd number of alternating paths that end in *u*. Let's also define *dp*[*i*][*ew*][*ow*][*eb*] as the number of different graphs following the requirements that can be built using the first *i* nodes, with *ew* even-white nodes, *ow* odd-white nodes and *eb* even-black nodes (the number of odd-black nodes *ob* = *i* - *ew* - *ow* - *eb*). We will figure out how to calculate such value. For the sake of simplicity, let's consider the current node — the {*i*}*th* node to be a white node.
    265 
    266 We can notice a few things:
    267 
    268 * If none of the previous *i* - 1 nodes connects to the current node, the current node becomes an odd-white node (the only alternating path that ends the current node is the node itself).
    269 * How the previous white nodes connect to the current node does not matter. There are 2*ow* + *ew* - 1 ways to add edges between the previous white nodes and the current node.
    270 * How the previous even-black nodes connect to the current node does not matter, as it does not change the state of the current white node (i.e. odd-white to even-white or even-white to odd-white). There are 2*eb* ways to add edges between the previous even-black nodes and the current node.
    271 * If there are an odd number of previous odd-black nodes that have edges to the current node, the current node becomes an even-white node. There are ![](https://espresso.codeforces.com/27ad75554c8cab63abdbfbb88df1f8bb5d9a138e.png) ways to do this.
    272 * If there are an even number of previous odd-black nodes that have edges to the current node, the current node becomes an odd-white node. There are ![](https://espresso.codeforces.com/4f1f58175f354db7f391ca8465e67371f4e6e29d.png) ways to do this.
    273 
    274 In conclusion, we can figure out that:
    275 
    276 ![](https://espresso.codeforces.com/260f5f452b24ef1f5c5edc108a8d2cc442034fd9.png)
    277 
    278 It is worth mentioning that we can use the same analogy to process when the current node is black.
    279 
    280 In total, we process through *n*4 states, with an *O*(*n*) iteration for each stage, so the time complexity is *O*(*n*5). However, with precomputation of ![](https://espresso.codeforces.com/da2cef21bddee287b921eb7d36b33cc8ddc53758.png) and ![](https://espresso.codeforces.com/d21f5e7fc8c80a75ea8b0d261246aad39b254b9d.png) for every value of *ob*, we can optimize the time complexity to *O*(*n*4).
    281 
    282 Time complexity: *O*(*n*4).
    283 
    284 **Code**
    285 
    286 ```
    287 #include <iostream>
    288 using namespace std;
    289 
    290 const int N = 55, MOD = 1E9 + 7;
    291 
    292 int n, p, c[N];
    293 long long ans = 0, pw[N], fct[N], inv[N], od[N], ev[N], f[N][N][N][N];
    294 
    295 long long power(int u, int p)
    296 {
    297     if (p == 0)
    298         return 1;
    299     long long ret = power(u, p >> 1);
    300     (ret *= ret) %= MOD;
    301     if (p & 1)
    302         (ret *= u) %= MOD;
    303     return ret;
    304 }
    305 
    306 long long C(int n, int k)
    307 {
    308     return fct[n] * inv[k] % MOD * inv[n - k] % MOD;
    309 }
    310 
    311 void init()
    312 {
    313     f[0][0][0][0] = 1;
    314     pw[0] = 1;
    315     fct[0] = 1;
    316     for (int i = 1; i < N; i++)
    317     {
    318         pw[i] = pw[i - 1] * 2 % MOD;
    319         fct[i] = fct[i - 1] * i % MOD;
    320     }
    321     inv[N - 1] = power(fct[N - 1], MOD - 2);
    322     for (int i = N - 2; i >= 0; i--)
    323         inv[i] = inv[i + 1] * (i + 1) % MOD;
    324     for (int i = 0; i < N; i++)
    325     {
    326         for (int j = 0; j <= i; j += 2)
    327             (ev[i] += C(i, j)) %= MOD;
    328         for (int j = 1; j <= i; j += 2)
    329             (od[i] += C(i, j)) %= MOD;
    330     }
    331 }
    332 
    333 void find_ans(int ob, int eb, int ow, int ew, int col, long long &ret)
    334 {
    335     // current node is even-white
    336     if (col != 0 && ew != 0)
    337         (ret += f[ob][eb][ow][ew - 1] * pw[ow + ew - 1 + eb] % MOD * od[ob] % MOD) %= MOD;
    338 
    339     // current node is odd-white
    340     if (col != 0 && ow != 0)
    341         (ret += f[ob][eb][ow - 1][ew] * pw[ow - 1 + ew + eb] % MOD * ev[ob] % MOD) %= MOD;
    342 
    343     // current node is even-black
    344     if (col != 1 && eb != 0)
    345         (ret += f[ob][eb - 1][ow][ew] * pw[ob + eb - 1 + ew] % MOD * od[ow] % MOD) %= MOD;
    346 
    347     // current node is odd-black
    348     if (col != 1 && ob != 0)
    349         (ret += f[ob - 1][eb][ow][ew] * pw[ob - 1 + eb + ew] % MOD * ev[ow] % MOD) %= MOD;
    350 }
    351 
    352 int main()
    353 {
    354     init();
    355     scanf("%d%d", &n, &p);
    356     for (int i = 1; i <= n; i++)
    357         scanf("%d", c + i);
    358     for (int i = 1; i <= n; i++)
    359         for (int ob = 0; ob <= i; ob++)
    360             for (int eb = 0; ob + eb <= i; eb++)
    361                 for (int ow = 0; ob + eb + ow <= i; ow++)
    362                 {
    363                     int ew = i - ob - eb - ow;
    364                     find_ans(ob, eb, ow, ew, c[i], f[ob][eb][ow][ew]);
    365                     if (i == n && ((ob + ow) & 1) == p)
    366                         (ans += f[ob][eb][ow][ew]) %= MOD;
    367                 }
    368     printf("%lld", ans);
    369     return 0;
    370 }
    371 ```