codeforces-scrape

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

2132.md (17794B)


      1 Source: https://codeforces.com/blog/entry/145692
      2 
      3 We hope you enjoyed the contest! Thank you for participating! This is our second official round on Codeforces, so we would be happy to hear your feedback in the comments and in the mini-survey below.
      4 
      5 **How did you like the contest?**
      6 
      7 * Excellent:
      8 * Good:
      9 * Average:
     10 * Bad:
     11 * Terrible:
     12 
     13 **Which problems did you like (you can choose multiple)?**
     14 
     15 * A:
     16 * B:
     17 * C1:
     18 * C2:
     19 * D:
     20 * E:
     21 * F:
     22 * G:
     23 
     24 **Which problems did you not like (you can choose multiple)?**
     25 
     26 * A:
     27 * B:
     28 * C1:
     29 * C2:
     30 * D:
     31 * E:
     32 * F:
     33 * G:
     34 
     35 [2132A - Homework](/contest/2132/problem/A "Codeforces Round 1043 (Div. 3)")
     36 
     37 Idea: [Wileyne](/profile/Wileyne "Expert Wileyne"); developer: [Wileyne](/profile/Wileyne "Expert Wileyne")
     38 
     39 **Editorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47  
     48 using namespace std;
     49  
     50 void solve() {
     51     string a, b, c;
     52     int n, m;
     53     cin >> n >> a;
     54     cin >> m >> b >> c;
     55     string add_left = "";
     56     for (int i = 0; i < m; ++i) {
     57         if (c[i] == 'V') {
     58             add_left += b[i];
     59         } else {
     60             a += b[i];
     61         }
     62     }
     63     reverse(add_left.begin(), add_left.end());
     64     cout << add_left + a << '\n';
     65 }
     66 
     67 int main() {
     68     int t;
     69     cin >> t;
     70     while (t--)
     71         solve();
     72     return 0;
     73 }
     74 ```
     75 
     76 [2132B - The Secret Number](/contest/2132/problem/B "Codeforces Round 1043 (Div. 3)")
     77 
     78 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus")
     79 
     80 **Hint**
     81 
     82 If Vadim appends $k$ zeros to the number $x$, what will be the ratio between $n$ and $x$?
     83 
     84 **Answer**
     85 
     86 $n = x \cdot (10^k + 1)$
     87 
     88 **Editorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96  
     97 using namespace std;
     98  
     99 int main() {
    100     int t;
    101     cin >> t;
    102     
    103     while (t--) {
    104         long long r;
    105         cin >> r;
    106         
    107         long long d = 11;
    108         vector <long long> ans;
    109         while (r >= d) {
    110             if (r % d == 0)
    111                 ans.push_back(r / d);
    112             d = (d - 1) * 10 + 1;
    113         }
    114         
    115         cout << (int)ans.size() << '\n';
    116         for (int i = (int)ans.size() - 1; i >= 0; --i)
    117             cout << ans[i] << ' ';
    118         cout << '\n';
    119     }
    120     
    121     return 0;
    122 }
    123 ```
    124 
    125 [2132C1 - The Cunning Seller (easy version)](/contest/2132/problem/C1 "Codeforces Round 1043 (Div. 3)")
    126 
    127 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor")
    128 
    129 **Hint 1**
    130 
    131 Does it make sense to use the same type of deal more than 2 times?
    132 
    133 **Hint 2**
    134 
    135 The solution with the minimum number of deals is unique.
    136 
    137 **Hint 3**
    138 
    139 Ternary numeral system.
    140 
    141 **Editorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149  
    150 using namespace std;
    151  
    152 int main() {
    153     vector <long long> cost;
    154     long long c = 3;
    155     long long cnt = 1;
    156     for (int i = 0; i < 21; ++i) {
    157         cost.push_back(c);
    158         c = 3 * c + cnt;
    159         cnt *= 3;
    160     }
    161 
    162     int t;
    163     cin >> t;
    164     while (t--) {
    165         long long n;
    166         cin >> n;
    167         long long min_k = 0;
    168         long long min_cost = 0;
    169         int sz = 0;
    170         while (n) {
    171             min_k += n % 3;
    172             min_cost += (n % 3) * cost[sz];
    173             n /= 3;
    174             sz++;
    175         }
    176         cout << min_cost << '\n';
    177     }
    178     
    179     return 0;
    180 }
    181 ```
    182 
    183 [2132C2 - The Cunning Seller (hard version)](/contest/2132/problem/C2 "Codeforces Round 1043 (Div. 3)")
    184 
    185 Idea: [Boodoochai](/profile/Boodoochai "Expert Boodoochai"); developer: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor")
    186 
    187 **Hint 1**
    188 
    189 What is more profitable: 3 deals for $3^x$ watermelons each, or 1 deal for $3^{x+1}$ watermelons?
    190 
    191 **Hint 2**
    192 
    193 Recall the solution to problem C1.
    194 
    195 **Editorial**
    196 
    197 Tutorial is loading...
    198 
    199 **Solution**
    200 
    201 ```
    202 #include <bits/stdc++.h>
    203  
    204 using namespace std;
    205  
    206 int main() {
    207     vector <long long> cost;
    208     long long c = 3;
    209     long long cnt = 1;
    210     for (int i = 0; i < 21; ++i) {
    211         cost.push_back(c);
    212         c = 3 * c + cnt;
    213         cnt *= 3;
    214     }
    215 
    216     int t;
    217     cin >> t;
    218     while (t--) {
    219         long long n, k;
    220         cin >> n >> k;
    221         vector <long long> tr;
    222         long long min_k = 0;
    223         while (n) {
    224             tr.push_back(n % 3);
    225             min_k += n % 3;
    226             n /= 3;
    227         }
    228         if (min_k > k) {
    229             cout << -1 << '\n';
    230             continue;
    231         }
    232         k -= min_k;
    233         k /= 2;
    234         for (int i = (int)tr.size() - 1; i >= 1; --i) {
    235             if (tr[i] <= k) {
    236                 tr[i - 1] += 3 * tr[i];
    237                 k -= tr[i];
    238                 tr[i] = 0;
    239             } else {
    240                 tr[i - 1] += k * 3;
    241                 tr[i] -= k;
    242                 break;
    243             }
    244         }
    245         ll an = 0;
    246         for (int i = (int)tr.size() - 1; i >= 0; --i)
    247             an += cost[i] * tr[i];
    248         cout << an << '\n';
    249     }
    250     
    251     return 0;
    252 }
    253 ```
    254 
    255 [2132D - From 1 to Infinity](/contest/2132/problem/D "Codeforces Round 1043 (Div. 3)")
    256 
    257 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus")
    258 
    259 **Hint 1**
    260 
    261 Find out which number the $k$-th digit belongs to in the infinite sequence. Let this number be $n$. Instead of analyzing the sequence, we can calculate the sum of the sums of the digits of all integers from $0$ to $n - 1$ and add to this the sum of the required digits of the number $n$.
    262 
    263 **Hint 2**
    264 
    265 Mentally add leading zeros to all numbers from $0$ to $n - 1$ so that their lengths become the same. The sum of the sums of the digits will not change, but it will be more convenient to determine the formulas in this case.
    266 
    267 **Editorial**
    268 
    269 Tutorial is loading...
    270 
    271 **Solution**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275  
    276 using namespace std;
    277  
    278 int main() {
    279     int t;
    280     cin >> t;
    281     
    282     while (t--) {
    283         long long k;
    284         cin >> k;
    285         long long cur = 9, len = 1;
    286         while (k - cur * len > 0) {
    287             k -= cur * len;
    288             cur *= 10;
    289             len++;
    290         }
    291         string s = to_string(cur / 9 + (k - 1) / len);
    292         long long ans = 0;
    293         for (int i = 0; i < (k - 1) % len + 1; i++)
    294             ans += s[i] - '0';
    295         long long pr_s = 0;
    296         for (int i = 0; i < s.length(); i++) {
    297             int curd = s[i] - '0';
    298             if (curd)
    299                 ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9;
    300             cur /= 10, len--;
    301             pr_s += curd;
    302         }
    303         cout << ans << '\n';
    304     }
    305     
    306     return 0;
    307 }
    308 ```
    309 
    310 [2132E - Arithmetics Competition](/contest/2132/problem/E "Codeforces Round 1043 (Div. 3)")
    311 
    312 Idea: [EzikBro](/profile/EzikBro "Master EzikBro"); developer: [EzikBro](/profile/EzikBro "Master EzikBro")
    313 
    314 **Hint 1**
    315 
    316 If we know how many specific cards Vadim should take, and how many should take Kostya (for example when $x + y = z$). How can we then obtain the maximum possible sum?
    317 
    318 **Hint 2**
    319 
    320 We need to quickly compute the sum of the $x$ maximum elements in array $a$ and the sum of the $y$ maximum elements in array $b$. What should we do to be able to compute this for arbitrary $x$ and $y$ in $O(1)$?
    321 
    322 **Hint 3**
    323 
    324 How can we solve this problem if $x = n$ and $y = m$ — that is, each person can choose any number of cards, as long as their total is $z$?
    325 
    326 **Hint 4**
    327 
    328 If $x = n$ and $y = m$, then the optimal set of $z$ cards consists of $x'$ maximum cards from Vadim and $y'$ maximum cards from Kostya (where $x' + y' = z$). How should we adjust this optimal answer if the optimal number for Vadim or Kostya exceeds their limits (that is, if $x \lt x'$ or $y \lt y'$)?
    329 
    330 **Editorial**
    331 
    332 Tutorial is loading...
    333 
    334 **Solution 1**
    335 
    336 ```
    337 #include <bits/stdc++.h>
    338 
    339 using namespace std;
    340 
    341 void solve() {
    342     int n, m, q;
    343     cin >> n >> m >> q;
    344     vector <int> a(n), b(m);
    345     for (int i = 0; i < n; i++)
    346         cin >> a[i];
    347     for (int i = 0; i < m; i++)
    348         cin >> b[i];
    349     sort(a.rbegin(), a.rend());
    350     sort(b.rbegin(), b.rend());
    351 
    352     vector <long long> pa(n + 1), pb(m + 1);
    353     for (int i = 0; i < n; i++)
    354         pa[i + 1] = pa[i] + a[i];
    355     for (int i = 0; i < m; i++)
    356         pb[i + 1] = pb[i] + b[i];
    357 
    358     vector <pair <int, int>> ans(n + m + 1);
    359     int l = 0, r = 0;
    360     for (int i = 1; i < ans.size(); i++) {
    361         if (l < n && r < m) {
    362             if (a[l] < b[r])
    363                 r++;
    364             else
    365                 l++;
    366         }
    367         else if (l == n)
    368             r++;
    369         else if (r == m)
    370             l++;
    371         ans[i] = { l, r };
    372     }
    373 
    374     for (int i = 0; i < q; i++) {
    375         int x, y, z;
    376         cin >> x >> y >> z;
    377         l = ans[z].first, r = ans[z].second;
    378         if (l > x)
    379             cout << pa[x] + pb[z - x] << '\n';
    380         else if (r > y)
    381             cout << pa[z - y] + pb[y] << '\n';
    382         else
    383             cout << pa[l] + pb[r] << '\n';
    384     }
    385 }
    386 
    387 int main() {
    388     int t;
    389     cin >> t;
    390     while (t--)
    391         solve();
    392     return 0;
    393 }
    394 ```
    395 
    396 **Solution 2**
    397 
    398 ```
    399 #include <bits/stdc++.h>
    400 
    401 using namespace std;
    402 
    403 void solve() {
    404     int n, m, q;
    405     cin >> n >> m >> q;
    406     vector <int> a(n), b(m);
    407     for (int i = 0; i < n; i++)
    408         cin >> a[i];
    409     for (int i = 0; i < m; i++)
    410         cin >> b[i];
    411     sort(a.rbegin(), a.rend());
    412     sort(b.rbegin(), b.rend());
    413  
    414     vector <long long> pa(n + 1), pb(m + 1);
    415     for (int i = 0; i < n; i++)
    416         pa[i + 1] = pa[i] + a[i];
    417     for (int i = 0; i < m; i++)
    418         pb[i + 1] = pb[i] + b[i];
    419  
    420     for (int i = 0; i < q; i++) {
    421         int x, y, z;
    422         cin >> x >> y >> z;
    423  
    424         int l = max(0, z - y);
    425         int r = min(z, x);
    426         while (l + 2 < r) {
    427             int m1 = (l + l + r) / 3;
    428             int m2 = (l + r + r) / 3;
    429             if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) {
    430                 r = m2;
    431             } else {
    432                 l = m1;
    433             }
    434         }
    435  
    436         long long s = 0;
    437         for (int i = l; i <= r; i++)
    438             s = max(s, pa[i] + pb[z - i]);
    439  
    440         cout << s << '\n';
    441     }
    442 }
    443  
    444 int main() {
    445     int t;
    446     cin >> t;
    447     while (t--)
    448         solve();
    449     return 0;
    450 }
    451 ```
    452 
    453 [2132F - Rada and the Chamomile Valley](/contest/2132/problem/F "Codeforces Round 1043 (Div. 3)")
    454 
    455 Idea: [Friendiks](/profile/Friendiks "Master Friendiks"), [Wileyne](/profile/Wileyne "Expert Wileyne"); developers: [Friendiks](/profile/Friendiks "Master Friendiks"), [Wileyne](/profile/Wileyne "Expert Wileyne")
    456 
    457 **Hint 1**
    458 
    459 Recall or learn what bridges are and understand how this is related to the lanes that lie on all paths from $1$ to $n$.
    460 
    461 **Hint 2**
    462 
    463 How to find all the bridges that lie on every path from $1$ to $n$?
    464 
    465 **Hint 3**
    466 
    467 Solve the problem for the case where $n = q$ and $c_i = i$.
    468 
    469 **Hint 4**
    470 
    471 How to find the nearest vertex from a given set of vertices $S$ for each vertex?
    472 
    473 **Editorial**
    474 
    475 Tutorial is loading...
    476 
    477 **Solution**
    478 
    479 ```
    480 #include <bits/stdc++.h>
    481  
    482 using namespace std;
    483  
    484 vector <vector <int>> g;
    485 vector <bool> used;
    486 vector <int> d, h;
    487 vector <pair <int, int>> edges;
    488 vector <int> cut, path;
    489 int mark = 1;
    490 
    491 void dfs(int v, int p, int n) {
    492     used[v] = true;
    493     d[v] = h[v] = (p == -1 ? 0 : d[p] + 1);
    494     if (v == n) mark = 0;
    495     for (auto e : g[v]) {
    496         int to = edges[e].first + edges[e].second - v;
    497         if (to == p) continue;
    498         if (used[to])
    499             h[v] = min(h[v], d[to]);
    500         else {
    501             path[e] ^= mark;
    502             dfs(to, v, n);
    503             path[e] ^= mark;
    504             h[v] = min(h[v], h[to]);
    505             if (h[to] > d[v]) cut[e] = 1;
    506         }
    507     }
    508 }
    509 
    510 int main() {
    511     int t;
    512     cin >> t;
    513     while (t--) {
    514         int n, m;
    515         cin >> n >> m;
    516         
    517         g.assign(n + 1, {});
    518         used.assign(n + 1, false);
    519         d.assign(n + 1, 0);
    520         h.assign(n + 1, 0);
    521         edges = {};
    522         cut.assign(m, false);
    523         path.assign(m, false);
    524         mark = 1;
    525         for (int i = 0; i < m; ++i) {
    526             int a, b;
    527             cin >> a >> b;
    528             edges.push_back({a, b});
    529             g[a].push_back(i);
    530             g[b].push_back(i);
    531         }
    532         
    533         dfs(1, -1, n);
    534         
    535         vector <int> ans(n + 1, n + m);
    536         vector <int> dist(n + 1, n + m);
    537         queue <int> q;
    538         for (int i = 0; i < m; ++i) {
    539             if (cut[i] && path[i]) {
    540                 ans[edges[i].first] = min(ans[edges[i].first], i + 1);
    541                 ans[edges[i].second] = min(ans[edges[i].second], i + 1);
    542                 if (dist[edges[i].first]) {
    543                     dist[edges[i].first] = 0;
    544                     q.push(edges[i].first);
    545                 }
    546                 if (dist[edges[i].second]) {
    547                     dist[edges[i].second] = 0;
    548                     q.push(edges[i].second);
    549                 }
    550             }
    551         }
    552         
    553         while (!q.empty()) {
    554             int v = q.front();
    555             q.pop();
    556             for (auto e : g[v]) {
    557                 int to = edges[e].first + edges[e].second - v;
    558                 if (dist[to] > dist[v] + 1) {
    559                     dist[to] = dist[v] + 1;
    560                     ans[to] = ans[v];
    561                     q.push(to);
    562                 }
    563                 else if (dist[to] == dist[v] + 1)
    564                     ans[to] = min(ans[to], ans[v]);
    565             }
    566         }
    567         
    568         int Q;
    569         cin >> Q;
    570         while (Q--) {
    571             int v;
    572             cin >> v;
    573             if (ans[v] == n + m) cout << -1;
    574             else cout << ans[v];
    575             if (t || Q) cout << '\n';
    576         }
    577     }
    578     
    579     return 0;
    580 }
    581 ```
    582 
    583 [2132G - Famous Choreographer](/contest/2132/problem/G "Codeforces Round 1043 (Div. 3)")
    584 
    585 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developers: [fstilus](/profile/fstilus "Expert fstilus"), [pskobx](/profile/pskobx "Master pskobx")
    586 
    587 **Hint 1**
    588 
    589 There is no point in adding new symbols both above and below the original table simultaneously. Similarly, there is no point in adding symbols both to the left and to the right of the table at the same time.
    590 
    591 **Hint 2**
    592 
    593 The center of the optimal answer table lies within the original one.
    594 
    595 **Hint 3**
    596 
    597 We do not need to construct the answer; it is sufficient to check that an answer exists for the current center. Think about how to do this.
    598 
    599 **Hint 4**
    600 
    601 An answer exists for the current center if the subtable, which is the intersection of the original table and the one rotated around the center by $180^{\circ}$, becomes identical to the original when rotated by $180^{\circ}$. This subtable must contain at least one of the corners of the original table.
    602 
    603 **Hint 5**
    604 
    605 The checking of centers can be replaced by the checking of subtables that contain at least one of the corners of the original table.
    606 
    607 **Hint 6**
    608 
    609 To check the subtables to see if they become identical to the original when rotated by $180^{\circ}$, we can use hashing.
    610 
    611 **Editorial**
    612 
    613 Tutorial is loading...
    614 
    615 **Solution**
    616 
    617 ```
    618 #include <bits/stdc++.h>
    619  
    620 using namespace std;
    621  
    622 const int MOD = 998244353;
    623 const int P[2] = { 107, 61 };
    624 int BP[2];
    625 
    626 long long bin_pow(long long a, int n) {
    627     long long ret = 1;
    628     while (n) {
    629         if (n & 1) ret = (ret * a) % MOD;
    630         a = (a * a) % MOD;
    631         n >>= 1;
    632     }
    633     return ret;
    634 }
    635 
    636 inline int add(int a, int b) {
    637     int res = a + b;
    638     if (res >= MOD) return res - MOD;
    639     return res;
    640 }
    641 
    642 inline int sub(int a, int b) {
    643     int res = a - b;
    644     if (res < 0) return res + MOD;
    645     return res;
    646 }
    647 
    648 inline int mult(int a, int b) {
    649     long long res = (long long)a * b;
    650     if (res >= MOD) return res % MOD;
    651     return res;
    652 }
    653 
    654 int main() {
    655     int t;
    656     cin >> t;
    657     
    658     BP[0] = bin_pow(P[0], MOD - 2);
    659     BP[1] = bin_pow(P[1], MOD - 2);
    660     vector <int> pows[2];
    661     vector <int> bpows[2];
    662     for (int j = 0; j < 2; j++) {
    663         pows[j].resize(1e6, 1);
    664         bpows[j].resize(1e6, 1);
    665         for (int i = 1; i < 1e6; i++) {
    666             pows[j][i] = mult(pows[j][i - 1], P[j]);
    667             bpows[j][i] = mult(bpows[j][i - 1], BP[j]);
    668         }
    669     }
    670     
    671     while (t--) {
    672         int n, m;
    673         cin >> n >> m;
    674         
    675         vector <string> f(n);
    676         for (int i = 0; i < n; i++)
    677             cin >> f[i];
    678         
    679         vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0));
    680         vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0));
    681         for (int i = 1; i <= n; i++) {
    682             for (int j = 1; j <= m; j++) {
    683                 int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1]));
    684                 hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur);
    685             }
    686         }
    687         for (int i = n; i >= 1; i--) {
    688             for (int j = m; j >= 1; j--) {
    689                 int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j]));
    690                 bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur);
    691             }
    692         }
    693         
    694         auto isp = [&](int x1, int y1, int x2, int y2) {
    695             int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]);
    696             int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]);
    697             hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1]));
    698             bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2]));
    699             return hsh == bhsh;
    700         };
    701         
    702         int mn = n * m * 4;
    703         for (int i = 1; i <= n; i++) {
    704             for (int j = 1; j <= m; j++) {
    705                 if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j));
    706                 if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1));
    707                 if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j));
    708                 if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1));
    709             }
    710         }
    711         
    712         cout << mn - m * n << '\n';
    713     }
    714     
    715     return 0;
    716 }
    717 ```