codeforces-scrape

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

1893.md (13182B)


      1 Source: https://codeforces.com/blog/entry/122074
      2 
      3 I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers.
      4 
      5 [1894A - Secret Sport](/contest/1894/problem/A "Codeforces Round 908 (Div. 2)")
      6 
      7 **Hint 1**
      8 
      9 You can always bruteforce $X$ and $Y$, and check every pair of $(X, Y)$ separately, but there is a tRiCkY solution that involves zero implementation.
     10 
     11 **Hint 2**
     12 
     13 Have you ever watched a game of tennis, a game of volleyball, e.t.c?
     14 
     15 **Tutorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Solution**
     20 
     21 [231849364](/contest/1894/submission/231849364 "Submission 231849364 by sevlll777")
     22 
     23 ```
     24 #include <bits/stdc++.h>
     25  
     26 using namespace std;
     27  
     28 void solve() {
     29   int n;
     30   cin >> n;
     31   string s;
     32   cin >> s;
     33   cout << s.back() << '\n';
     34 }
     35  
     36 signed main() {
     37   ios::sync_with_stdio(false);
     38   cin.tie(nullptr);
     39   cout.tie(nullptr);
     40   int t;
     41   cin >> t;
     42   while (t--) {
     43     solve();
     44   }
     45 }
     46 ```
     47 
     48 **Rate the problem**
     49 
     50 * Didnt solve
     51 * Good problem
     52 * Average problem
     53 * Bad problem
     54 * tROlll pRoBlEm
     55 
     56 [1894B - Two Out of Three](/contest/1894/problem/B "Codeforces Round 908 (Div. 2)")
     57 
     58 **Hint 1**
     59 
     60 Everything is symmetrical, so you can fix beforehand any exact two conditions you are aimed to satisfy.
     61 
     62 **Hint 2**
     63 
     64 You need to not satisfy $3$rd condition, so it doesnt really make sense to color any elements that not used in satisfying conditions $1$ and $2$ in colors $b_i = 2, b_i = 3$. And to satisfy conditions $1$ and $2$ one element is enough.
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 [231849397](/contest/1894/submission/231849397 "Submission 231849397 by sevlll777")
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76  
     77 using namespace std;
     78 const int N = 100;
     79  
     80 void solve() {
     81   int n;
     82   cin >> n;
     83   vector<int> a(n);
     84   for (int i = 0; i < n; i++) {
     85     cin >> a[i];
     86   }
     87   vector<int> b(n, 1);
     88   vector<vector<int>> inds(N + 1);
     89   for (int i = 0; i < n; i++) {
     90     inds[a[i]].push_back(i);
     91   }
     92   int k = 2;
     93   for (int x = 1; x <= N; x++) {
     94     if ((int) inds[x].size() >= 2) {
     95       b[inds[x][0]] = k;
     96       k++;
     97       if (k > 3) {
     98         break;
     99       }
    100     }
    101   }
    102   if (k <= 3) {
    103     cout << "-1\n";
    104   } else {
    105     for (int i = 0; i < n; i++) {
    106       cout << b[i] << ' ';
    107     }
    108     cout << '\n';
    109   }
    110 }
    111  
    112 signed main() {
    113   ios::sync_with_stdio(false);
    114   cin.tie(nullptr);
    115   cout.tie(nullptr);
    116   int t;
    117   cin >> t;
    118   while (t--) {
    119     solve();
    120   }
    121 }
    122 ```
    123 
    124 **Rate the problem**
    125 
    126 * Didnt solve
    127 * Good problem
    128 * Average problem
    129 * Bad problem
    130 
    131 [1893A - Anonymous Informant](/contest/1893/problem/A "Codeforces Round 908 (Div. 1)")
    132 
    133 **Hint 1**
    134 
    135 How to rollback one operation? Is rollback uniquely determined?
    136 
    137 **Hint 1.1**
    138 
    139 Of course it is.
    140 
    141 **Hint 2**
    142 
    143 After performing operation $a_x = x$ always becomes a last element of array.
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 [231849420](/contest/1893/submission/231849420 "Submission 231849420 by sevlll777")
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155  
    156 using namespace std;
    157  
    158 void solve() {
    159   int n, k;
    160   cin >> n >> k;
    161   vector<int> a(n);
    162   for (int i = 0; i < n; i++) {
    163     cin >> a[i];
    164   }
    165   k = min(k, n);
    166   int last = n - 1;
    167   for (int _ = 0; _ < k; _++) {
    168     if (a[last] > n) {
    169       cout << "No\n";
    170       return;
    171     }
    172     last += n - a[last];
    173     if (last >= n) {
    174       last -= n;
    175     }
    176   }
    177   cout << "Yes\n";
    178 }
    179  
    180 signed main() {
    181   ios::sync_with_stdio(false);
    182   cin.tie(nullptr);
    183   cout.tie(nullptr);
    184   int t;
    185   cin >> t;
    186   while (t--) {
    187     solve();
    188   }
    189 }
    190 ```
    191 
    192 **Rate the problem**
    193 
    194 * Didnt solve
    195 * Good problem
    196 * Average problem
    197 * Bad problem
    198 
    199 [1893B - Neutral Tonality](/contest/1893/problem/B "Codeforces Round 908 (Div. 1)")
    200 
    201 **Hint 1**
    202 
    203 Lower bound for answer: $LIS(a)$
    204 
    205 **Hint 2**
    206 
    207 Upper bound for answer: $LIS(a)+1$, you can insert $b$'s in decreasing order anywhere. When you can't achieve $LIS(a)$?
    208 
    209 **Hint 3**
    210 
    211 Solve for $m = 1$
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution**
    218 
    219 [231849445](/contest/1893/submission/231849445 "Submission 231849445 by sevlll777")
    220 
    221 ```
    222 #include <bits/stdc++.h>
    223  
    224 #define pb push_back
    225 #define all(x) x.begin(), (x).end()
    226 #define rall(x) x.rbegin(), (x).rend()
    227 using namespace std;
    228  
    229 void solve() {
    230   int n, m;
    231   cin >> n >> m;
    232   vector<int> a(n), b(m), c(n + m);
    233   for (int i = 0; i < n; i++) {
    234     cin >> a[i];
    235   }
    236   for (int i = 0; i < m; i++) {
    237     cin >> b[i];
    238   }
    239   sort(rall(b));
    240   merge(all(a), all(b), c.begin(), greater<int>());
    241   for (int i = 0; i < n + m; i++) {
    242     cout << c[i] << ' ';
    243   }
    244   cout << '\n';
    245 }
    246  
    247 signed main() {
    248   ios::sync_with_stdio(false);
    249   cin.tie(nullptr);
    250   cout.tie(nullptr);
    251   int t;
    252   cin >> t;
    253   while (t--) {
    254     solve();
    255   }
    256 }
    257 ```
    258 
    259 **Rate the problem**
    260 
    261 * Didnt solve
    262 * Good problem
    263 * Average problem
    264 * Bad problem
    265 
    266 [1893C - Freedom of Choice](/contest/1893/problem/C "Codeforces Round 908 (Div. 1)")
    267 
    268 **Hint 1**
    269 
    270 It makes sense to try to solve case $m = 1$ first, to get general understanding of the problem, some observations will be usefull in full solution.
    271 
    272 **Hint 1.1**
    273 
    274 What size can a multiset $X$ have?
    275 
    276 **Hint 1.2**
    277 
    278 If $r - l \gt n$, the answer to the problem is $0$. Now we are left in the case of $r - l \leq n$. So we can iterate over all sizes from $l$ to $r$, for each of them find the minimum anti-beauty that can have a set of this size, and take the minimum of all this for the answer.
    279 
    280 **Hint 2**
    281 
    282 For bigger $m$ you need to find a fast enough way to count minimal anti-beauty with fixed size, everything else remains the same.
    283 
    284 **Tutorial**
    285 
    286 Tutorial is loading...
    287 
    288 **Solution**
    289 
    290 [231849477](/contest/1893/submission/231849477 "Submission 231849477 by sevlll777")
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294  
    295 #define pb push_back
    296 #define int long long
    297 #define all(x) x.begin(), (x).end()
    298 using namespace std;
    299  
    300 void solve() {
    301   int m;
    302   cin >> m;
    303   vector<int> n(m), l(m), r(m);
    304   vector<vector<int>> a(m);
    305   vector<vector<int>> c(m);
    306   vector<int> sumc(m);
    307   int suml = 0, sumr = 0, sumn = 0;
    308   for (int i = 0; i < m; i++) {
    309     cin >> n[i] >> l[i] >> r[i];
    310     sumn += n[i];
    311     suml += l[i];
    312     sumr += r[i];
    313     a[i].resize(n[i]);
    314     for (int j = 0; j < n[i]; j++) {
    315       cin >> a[i][j];
    316     }
    317     c[i].resize(n[i]);
    318     for (int j = 0; j < n[i]; j++) {
    319       cin >> c[i][j];
    320       sumc[i] += c[i][j];
    321     }
    322   }
    323   
    324   if (sumr - suml > sumn) {
    325     cout << "0\n";
    326     return;
    327   }
    328  
    329   map<int, int> sumr_a;
    330   map<int, vector<pair<int, int>>> indexes;
    331   for (int i = 0; i < m; i++) {
    332     for (int j = 0; j < n[i]; j++) {
    333       sumr_a[a[i][j]] += r[i];
    334       indexes[a[i][j]].pb({i, j});
    335     }
    336   }
    337  
    338   int ans = (int) 2e18;
    339   for (int len = suml; len <= sumr; len++) {
    340     int xsize = 0, must_len = 0;
    341     xsize += sumr - sumr_a[len];
    342     for (auto &[i, pos] : indexes[len]) {
    343       int cnt_not_len = sumc[i] - c[i][pos];
    344       if (cnt_not_len < l[i]) {
    345         xsize += l[i];
    346         must_len += l[i] - cnt_not_len;
    347       } else {
    348         xsize += min(cnt_not_len, r[i]);
    349       }
    350     }
    351     ans = min(ans, must_len + max(0LL, len - xsize));
    352   }
    353   cout << ans << '\n';
    354 }
    355  
    356 signed main() {
    357   ios::sync_with_stdio(false);
    358   cin.tie(nullptr);
    359   cout.tie(nullptr);
    360   int t;
    361   cin >> t;
    362   while (t--) {
    363     solve();
    364   }
    365 }
    366 ```
    367 
    368 **Rate the problem**
    369 
    370 * Didnt solve
    371 * Good problem
    372 * Average problem
    373 * Bad problem
    374 
    375 [1893D - Colorful Constructive](/contest/1893/problem/D "Codeforces Round 908 (Div. 1)")
    376 
    377 **Hints: Natural Way**
    378 
    379 **Hint 1**
    380 
    381 Solve the problem if $s_i = d_i$ for all $i$.
    382 
    383 **Hint 1.1**
    384 
    385 Simple greedy should work.
    386 
    387 **Hint 2**
    388 
    389 Solve the problem if $s_i = 2 \cdot d_i$ for all $i$.
    390 
    391 **Hint 3**
    392 
    393 Solve the problem if $d_i$ divides $s_i$ for all $i$.
    394 
    395 **Hint 4**
    396 
    397 You can treat remainder $(s_i \mod d_i)$ separately, as an individual shelf.
    398 
    399 **Hints: Believers Way**
    400 
    401 **Hint -1**
    402 
    403 What is the most obvious greedy you can do?
    404 
    405 **Hint -2**
    406 
    407 What is the second most obvious greedy you can do?
    408 
    409 **Hint -3**
    410 
    411 What is the third most obvious greedy you can do?
    412 
    413 **Hint -4**
    414 
    415 It's probably correct at this point, just proof by AC!
    416 
    417 **Tutorial**
    418 
    419 Tutorial is loading...
    420 
    421 **Solution**
    422 
    423 [231849510](/contest/1893/submission/231849510 "Submission 231849510 by sevlll777")
    424 
    425 ```
    426 #include <bits/stdc++.h>
    427  
    428 #define pb push_back
    429 #define all(x) x.begin(), (x).end()
    430 #define rall(x) x.rbegin(), (x).rend()
    431 using namespace std;
    432  
    433 void solve() {
    434   int n, m;
    435   cin >> n >> m;
    436   vector<int> a(n);
    437   for (int i = 0; i < n; i++) {
    438     cin >> a[i];
    439   }
    440   vector<int> s(m), d(m);
    441   for (int i = 0; i < m; i++) {
    442     cin >> s[i];
    443   }
    444   for (int i = 0; i < m; i++) {
    445     cin >> d[i];
    446   }
    447   vector<int> cnt(n + 1);
    448   for (int i = 0; i < n; i++) {
    449     cnt[a[i]]++;
    450   }
    451  
    452   set<pair<int, int>> cubes;
    453   for (int x = 1; x <= n; x++) {
    454     if (cnt[x] == 0) continue;
    455     cubes.insert({cnt[x], x});
    456   }
    457  
    458   vector<vector<int>> ans(m);
    459  
    460   for (int i = 0; i < m; i++) {
    461     ans[i].assign(s[i], 0);
    462     for (int j = 0; j < s[i]; j++) {
    463       if (j >= d[i]) {
    464         if (cnt[ans[i][j - d[i]]] > 0) {
    465           cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
    466         }
    467       }
    468       if (cubes.empty()) {
    469         cout << "-1\n";
    470         return;
    471       }
    472       ans[i][j] = (*cubes.rbegin()).second;
    473       cubes.erase(*cubes.rbegin());
    474       cnt[ans[i][j]]--;
    475     }
    476     for (int j = s[i]; j < s[i] + d[i]; j++) {
    477       if (cnt[ans[i][j - d[i]]] > 0) {
    478         cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
    479       }
    480     }
    481   }
    482  
    483   for (int i = 0; i < m; i++) {
    484     for (int j = 0; j < s[i]; j++) {
    485       cout << ans[i][j] << ' ';
    486     }
    487     cout << '\n';
    488   }
    489  
    490 }
    491  
    492  
    493 signed main() {
    494   ios::sync_with_stdio(false);
    495   cin.tie(nullptr);
    496   cout.tie(nullptr);
    497   int t;
    498   cin >> t;
    499   while (t--) {
    500     solve();
    501   }
    502 }
    503 ```
    504 
    505 **Rate the problem**
    506 
    507 * Didnt solve
    508 * Good problem
    509 * Average problem
    510 * Bad problem
    511 
    512 [1893E - Cacti Symphony](/contest/1893/problem/E "Codeforces Round 908 (Div. 1)")
    513 
    514 **Hint 1**
    515 
    516 Cacti is a trap, don't think about it for now, it will help later.
    517 
    518 **Hint 2**
    519 
    520 Well, you need to make some observations. Start with observations about determining edges weights, it seems reasonable because edge always have exactly $2$ adjacent vertices.
    521 
    522 **Hint 3**
    523 
    524 Edge is good <=> Exactly one of the adjacent vertexes have a same weight as an edge.
    525 
    526 **Hint 4**
    527 
    528 Direct edges, such that every edge goes from vertex with same weight as edge to another vertex. In this reality try to find easier equivalent condition for ``vertice is good``.
    529 
    530 **Hint 5**
    531 
    532 Vertex is good <=> InDegree of vertex is an odd integer.
    533 
    534 **Hint 6**
    535 
    536 Now you just have two separate problems: 1) Direct all edges, such that InDegree of each vertex is odd; 2) Color all vertexes in 3 colors such that any 2 adjacent vertexes have different color. Time to remember about cacti.
    537 
    538 **Tutorial**
    539 
    540 Tutorial is loading...
    541 
    542 **Solution**
    543 
    544 [231849553](/contest/1893/submission/231849553 "Submission 231849553 by sevlll777")
    545 
    546 ```
    547 #include <bits/stdc++.h>
    548  
    549 typedef long long ll;
    550 #define pb push_back
    551  
    552 using namespace std;
    553  
    554 const int M = 998244353;
    555 const int N = 500500;
    556 vector<pair<int, int>> g[N];
    557 set<int> bridgesV[N];
    558 bitset<N> used;
    559 int h[N], d[N];
    560 ll bridges = 0;
    561 ll solo = 0;
    562  
    563 int binpow(ll a, ll x) {
    564   ll ans = 1;
    565   while (x) {
    566     if (x % 2) {
    567       ans *= a;
    568       ans %= M;
    569     }
    570     a *= a;
    571     a %= M;
    572     x /= 2;
    573   }
    574   return (int) ans;
    575 }
    576  
    577 void dfs(int v, int p = -1) {
    578   if (p != -1) {
    579     d[v] = h[p] + 1;
    580     h[v] = h[p] + 1;
    581   }
    582   used[v] = true;
    583   for (auto &[u, w] : g[v]) {
    584     if (u == p) continue;
    585     if (!used[u]) {
    586       dfs(u, v);
    587       d[v] = min(d[v], d[u]);
    588       if (h[v] < d[u]) {
    589         bridgesV[v].insert(u);
    590         bridgesV[u].insert(v);
    591         bridges += w + 1;
    592         solo += w;
    593       }
    594     } else {
    595       d[v] = min(d[v], h[u]);
    596     }
    597   }
    598 }
    599  
    600 int calc_dp(ll n) {
    601   n %= (M - 1);
    602   if (n == 1) return 3;
    603   if (n == 2) return 0;
    604   int val = binpow(2, n);
    605   if (n % 2 == 1) {
    606     val += M - 2;
    607   } else {
    608     val += 2;
    609   }
    610   val %= M;
    611   return val;
    612 }
    613  
    614 signed main() {
    615   ios::sync_with_stdio(false);
    616   cin.tie(nullptr);
    617   cout.tie(nullptr);
    618   int n, m;
    619   cin >> n >> m;
    620   for (int i = 0; i < m; i++) {
    621     int a, b, w;
    622     cin >> a >> b >> w;
    623     a--;
    624     b--;
    625     g[a].pb({b, w});
    626     g[b].pb({a, w});
    627   }
    628   if (n % 2 != m % 2) {
    629     cout << "0\n";
    630     return 0;
    631   }
    632   dfs(0);
    633   used.reset();
    634  
    635   ll ans = 1;
    636   for (int v = 0; v < n; v++) {
    637     if (!used[v]) {
    638       ll cs = 0;
    639       vector<int> q = {v};
    640       used[v] = true;
    641       while (!q.empty()) {
    642         int u = q.back();
    643         q.pop_back();
    644         for (auto &[uu, w] : g[u]) {
    645           if (bridgesV[u].find(uu) != bridgesV[u].end()) continue;
    646           cs += w + 1;
    647           if (!used[uu]) {
    648             used[uu] = true;
    649             q.pb(uu);
    650           }
    651         }
    652       }
    653       cs /= 2;
    654       cs = max(cs, 1LL);
    655       ans *= calc_dp(cs);
    656       ans %= M;
    657     }
    658   }
    659   ans *= binpow(3, solo);
    660   ans %= M;
    661   int w = (2 * binpow(3, M - 2)) % M;
    662   ans *= binpow(w, bridges);
    663   ans %= M;
    664   int cycles = (m + 1) - n;
    665   ans *= binpow(2, cycles);
    666   ans %= M;
    667   cout << ans << '\n';
    668 }
    669 ```
    670 
    671 **Rate the problem**
    672 
    673 * Didnt solve
    674 * Good problem
    675 * Average problem
    676 * Bad problem