codeforces-scrape

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

2200.md (11167B)


      1 Source: https://codeforces.com/blog/entry/151625
      2 
      3 Thanks to everyone who participated in this round! I hope you enjoyed the contest.
      4 
      5 **Rate the contest!**
      6 
      7 * Horrible contest
      8 * Bad contest
      9 * Average contest
     10 * Good contest
     11 * Peak contest
     12 
     13 **Rate the difficulty!**
     14 
     15 * Extreme contest
     16 * Hard contest
     17 * Normal contest
     18 * Easy contest
     19 * Trivial contest
     20 
     21 #### [2200A - Eating Game](/contest/2200/problem/A "Codeforces Round 1084 (Div. 3)")
     22 
     23 **Rate the problem!**
     24 
     25 * Horrible problem
     26 * Bad problem
     27 * Average problem
     28 * Good problem
     29 * Peak problem
     30 * Did not solve
     31 
     32 **Tutorial**
     33 
     34 Tutorial is loading...
     35 
     36 **Code (C++)**
     37 
     38 ```
     39 #include <bits/stdc++.h>
     40 using namespace std;
     41 
     42 void solve() {
     43     int n;
     44     cin >> n;
     45     vector<int> a(n);
     46     for (auto &i: a) cin >> i;
     47     
     48     int mx = 0, ans = 0;
     49     for (int i : a) mx = max(i, mx);
     50     for (int i : a) ans += i == mx;
     51     cout << ans << '\n';
     52 }
     53 
     54 signed main() {
     55     int t = 1;
     56     cin >> t;
     57     while (t--) solve();
     58 }
     59 ```
     60 
     61 #### [2200B - Deletion Sort](/contest/2200/problem/B "Codeforces Round 1084 (Div. 3)")
     62 
     63 **Rate the problem!**
     64 
     65 * Horrible problem
     66 * Bad problem
     67 * Average problem
     68 * Good problem
     69 * Peak problem
     70 * Did not solve
     71 
     72 **Tutorial**
     73 
     74 Tutorial is loading...
     75 
     76 **Code (C++)**
     77 
     78 ```
     79 #include <bits/stdc++.h>
     80 using namespace std;
     81 
     82 void solve() {
     83     int n;
     84     cin >> n;
     85     vector<int> a(n);
     86     for (auto &i: a) cin >> i;
     87 
     88     if (is_sorted(a.begin(), a.end())) cout << n << '\n';
     89     else cout << "1\n";
     90 }
     91 
     92 signed main() {
     93     cin.tie(0)->sync_with_stdio(0);
     94     int t = 1;
     95     cin >> t;
     96     while (t--) solve();
     97 }
     98 ```
     99 
    100 #### [2200C - Specialty String](/contest/2200/problem/C "Codeforces Round 1084 (Div. 3)")
    101 
    102 **Rate the problem!**
    103 
    104 * Horrible problem
    105 * Bad problem
    106 * Average problem
    107 * Good problem
    108 * Peak problem
    109 * Did not solve
    110 
    111 **Hint**
    112 
    113 What if you delete characters instead of replacing them with $*$?
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Code 1 (C++)**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 using namespace std;
    124 
    125 void solve() {
    126     int n;
    127     string s;
    128     cin >> n >> s;
    129     for (int i = 0; 2*i < n; i++) {
    130         for (int j = 1; j < size(s); j++) {
    131             if (s[j] == s[j-1]) {
    132                 s.erase(j-1, 2);
    133             }
    134         }
    135     }
    136     cout << (s.empty() ? "YES\n" : "NO\n");
    137 }
    138 
    139 signed main() {
    140     int t = 1;
    141     cin >> t;
    142     while (t--) solve();
    143 }
    144 ```
    145 
    146 **Code 2 (C++)**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150 using namespace std;
    151 
    152 void solve() {
    153     int n;
    154     string s;
    155     cin >> n >> s;
    156     stack<int> st;
    157     for (char c : s) {
    158         if (st.size() && c == st.top()) st.pop();
    159         else st.push(c);
    160     }
    161     cout << (st.empty() ? "YES\n" : "NO\n");
    162 }
    163 
    164 signed main() {
    165     int t = 1;
    166     cin >> t;
    167     while (t--) solve();
    168 }
    169 ```
    170 
    171 #### [2200D - Portal](/contest/2200/problem/D "Codeforces Round 1084 (Div. 3)")
    172 
    173 **Rate the problem!**
    174 
    175 * Horrible problem
    176 * Bad problem
    177 * Average problem
    178 * Good problem
    179 * Peak problem
    180 * Did not solve
    181 
    182 **Hint 1**
    183 
    184 What invariants does $p$ have?
    185 
    186 **Hint 2**
    187 
    188 Consider the elements in between the portals and the elements outside of them.
    189 
    190 **Hint 3**
    191 
    192 What invariant does each of these two regions have?
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Code (C++)**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 using namespace std;
    203 
    204 void solve() {
    205     int n, x, y;
    206     cin >> n >> x >> y;
    207     x--, y--;
    208     vector<int> a, b;
    209     for (int i = 0; i < n; i++) {
    210         int j;
    211         cin >> j;
    212         if (i <= x || i > y) a.push_back(j);
    213         else b.push_back(j);
    214     }
    215 
    216     // solve
    217     if (!b.empty()) rotate(b.begin(), min_element(b.begin(), b.end()), b.end());
    218     int m = b.empty() ? -1 : b[0];
    219     auto it = a.begin();
    220     while (it != a.end() && *it < m) it++;
    221     a.insert(it, b.begin(), b.end());
    222     for (int i = 0; i < n; i++) {
    223         cout << a[i] << " \n"[i == n-1];
    224     }
    225 }
    226 
    227 signed main() {
    228     int t = 1;
    229     cin >> t;
    230     while (t--) solve();
    231 }
    232 ```
    233 
    234 #### [2200E - Divisive Battle](/contest/2200/problem/E "Codeforces Round 1084 (Div. 3)")
    235 
    236 **Rate the problem!**
    237 
    238 * Horrible problem
    239 * Bad problem
    240 * Average problem
    241 * Good problem
    242 * Peak problem
    243 * Did not solve
    244 
    245 **Hint 1**
    246 
    247 What elements can the operation not be used on?
    248 
    249 **Answer**
    250 
    251 $1$ and prime numbers.
    252 
    253 **Hint 2**
    254 
    255 What first moves ensure that Alice will win?
    256 
    257 **Answer**
    258 
    259 Making a small prime number appear in the array after a number with a larger prime factor.
    260 
    261 **Hint 3**
    262 
    263 If Alice can win, then she can ensure victory on her first move.
    264 
    265 **Tutorial**
    266 
    267 Tutorial is loading...
    268 
    269 **Code (C++)**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 using namespace std;
    274 
    275 #define all(x) begin(x), end(x)
    276 
    277 int primebase(int x) {
    278     set<int> s;
    279     for (int i = 2; i*i <= x; i++) {
    280         while (x % i == 0) {
    281             s.insert(i);
    282             x /= i;
    283         }
    284     }
    285     if (x > 1) s.insert(x);
    286     if (s.size() > 1) return -1;
    287     if (s.size() == 0) return 1;
    288     return *s.begin();
    289 }
    290 
    291 void solve() {
    292     int n;
    293     cin >> n;
    294     vector<int> a(n);
    295     for (auto &i: a) cin >> i;
    296     
    297     // solve
    298     vector<int> b(n);
    299     for (int i = 0; i < n; i++) b[i] = primebase(a[i]);
    300     if (is_sorted(all(a))) {
    301         cout << "Bob\n";
    302     } else if (*min_element(all(b)) == -1) {
    303         cout << "Alice\n";
    304     } else if (is_sorted(all(b))) {
    305         cout << "Bob\n";
    306     } else {
    307         cout << "Alice\n";
    308     }
    309 }
    310 
    311 signed main() {
    312     int t = 1;
    313     cin >> t;
    314     while (t--) solve();
    315 }
    316 ```
    317 
    318 #### [2200F - Mooclear Reactor 2](/contest/2200/problem/F "Codeforces Round 1084 (Div. 3)")
    319 
    320 **Rate the problem!**
    321 
    322 * Horrible problem
    323 * Bad problem
    324 * Average problem
    325 * Good problem
    326 * Peak problem
    327 * Did not solve
    328 
    329 **Hint 1**
    330 
    331 Try to solve the problem without shop particles.
    332 
    333 **Hint 1.1**
    334 
    335 Fix the number of energy-generating particles $k$. Which particles can Bessie use?
    336 
    337 **Answer**
    338 
    339 She can use all particles with $y\geq k-1$.
    340 
    341 **Hint 1.2**
    342 
    343 Of the particles she can use for some $k$, which should Bessie use?
    344 
    345 **Answer**
    346 
    347 The $k$ particles with the largest $x$ values.
    348 
    349 **Hint 1.3**
    350 
    351 Process $k$ in decreasing order.
    352 
    353 **Hint 2**
    354 
    355 If Bessie has to use a shop particle, which of her own particles should she replace with it?
    356 
    357 **Answer**
    358 
    359 The energy-generating particle with smallest $x$.
    360 
    361 **Tutorial**
    362 
    363 Tutorial is loading...
    364 
    365 **Code (C++)**
    366 
    367 ```
    368 #include <bits/stdc++.h>
    369 using namespace std;
    370 using ll = long long;
    371 
    372 template<class T> bool smin(T &a, const T b) { return b < a ? a = b, 1 : 0;}
    373 template<class T> bool smax(T &a, const T b) { return a < b ? a = b, 1 : 0;}
    374 
    375 void solve() {
    376     int n, q;
    377     cin >> n >> q;
    378     vector<array<int, 2>> a(n);
    379     for (auto &i : a) cin >> i[1] >> i[0];
    380 
    381     // solve
    382     sort(a.rbegin(), a.rend());
    383     int ptr = 0;
    384     multiset<int> s;
    385     ll mx = 0, cur = 0;
    386     vector<ll> pref(n+1);
    387     for (int k = n; k >= 0; k--) {
    388         while (ptr < n && a[ptr][0] >= k) {
    389             cur += a[ptr][1];
    390             s.insert(a[ptr][1]);
    391             ptr++;
    392         }
    393         while (s.size() > k + 1) {
    394             cur -= *s.begin();
    395             s.erase(s.begin());
    396         }
    397         smax(mx, cur);
    398         pref[k] = (s.size() <= k) ? cur : cur - *s.begin();
    399     }
    400     for (int k = 1; k <= n; k++) smax(pref[k], pref[k-1]);
    401 
    402     // queries
    403     while (q--) {
    404         int x, y;
    405         cin >> x >> y;
    406         cout << max(mx, pref[y] + x) << '\n';
    407     }
    408 }
    409 
    410 signed main() {
    411     int t = 1;
    412     cin >> t;
    413     while (t--) solve();
    414 }
    415 ```
    416 
    417 #### [2200G - Operation Permutation](/contest/2200/problem/G "Codeforces Round 1084 (Div. 3)")
    418 
    419 **Rate the problem!**
    420 
    421 * Horrible problem
    422 * Bad problem
    423 * Average problem
    424 * Good problem
    425 * Peak problem
    426 * Did not solve
    427 
    428 **Hint 1**
    429 
    430 Convert each `-` operation to `+` and `/` operation to `x`.
    431 
    432 **Hint 2**
    433 
    434 Fix the permutation. For each `+y` operation, by how much would the answer change if it was removed?
    435 
    436 **Answer**
    437 
    438 The answer would reduce by the product of $y$ and the `x` operations that come after it in the permutation.
    439 
    440 **Hint 3**
    441 
    442 How can you calculate the expected value of the product `x` operations that come after `+y` over all permutations?
    443 
    444 **Tutorial**
    445 
    446 Tutorial is loading...
    447 
    448 **Code (C++)**
    449 
    450 ```
    451 #include <bits/stdc++.h>
    452 using namespace std;
    453 using ll = long long;
    454 
    455 const int mod = 1e9+7;
    456 
    457 ll mpow(ll a, ll b) {
    458     ll r = 1;
    459     while (b) {
    460         if (b & 1) {
    461             r *= a;
    462             r %= mod;
    463         }
    464         b >>= 1;
    465         a *= a;
    466         a %= mod;
    467     }
    468     return r;
    469 }
    470 
    471 ll inv(ll a) {
    472     return mpow(a, mod-2);
    473 }
    474 
    475 const int maxn = 5000;
    476 ll facts[maxn+1] = {1};
    477 
    478 void precomp() {
    479     for (int i = 1; i <= maxn; i++) {
    480         facts[i] = facts[i-1] * i % mod;
    481     }
    482 }
    483 
    484 void solve() {
    485     int n;
    486     ll x;
    487     cin >> n >> x;
    488 
    489     vector<ll> mults;
    490     ll adds = 0;
    491     for (int i = 0; i < n; i++) {
    492         char c;
    493         ll v;
    494         cin >> c >> v;
    495         if (c == '-') adds += mod - v;
    496         else if (c == '+') adds += v;
    497         else if (c == '/') mults.push_back(inv(v));
    498         else mults.push_back(v);
    499     }
    500     adds %= mod;
    501 
    502     // solve
    503     int m = mults.size();
    504     vector<ll> dp(m+1);
    505     dp[0] = 1;
    506     for (auto &b : mults) {
    507         x *= b;
    508         x %= mod;
    509         for (int i = m; i >= 1; i--) {
    510             dp[i] += dp[i-1] * b;
    511             dp[i] %= mod;
    512         }
    513     }
    514 
    515     ll S = 0;
    516     for (int i = 0; i <= m; i++) {
    517         S += dp[i] * facts[i] % mod * facts[m-i] % mod * inv(facts[m]) % mod;
    518         S %= mod;
    519     }
    520     S *= inv(m+1);
    521     S %= mod;
    522 
    523     // answer
    524     ll ans = x + adds * S;
    525     ans %= mod;
    526     cout << ans << "\n";
    527 }
    528 
    529 signed main() {
    530     precomp();
    531     int t = 1;
    532     cin >> t;
    533     while (t--) solve();
    534 }
    535 ```
    536 
    537 **Bonus from Proof_by_QED**
    538 
    539 Solve for $n \leq 2\cdot 10^5$.
    540 
    541 #### [2200H - Six Seven](/contest/2200/problem/H "Codeforces Round 1084 (Div. 3)")
    542 
    543 **Rate the problem!**
    544 
    545 * Horrible problem
    546 * Bad problem
    547 * Average problem
    548 * Good problem
    549 * Peak problem
    550 * Did not solve
    551 
    552 **Hint 1**
    553 
    554 Find a recursive definition for *special* numbers.
    555 
    556 **Hint 2**
    557 
    558 When can $x \bmod{42}$ tell us if $x$ is special?
    559 
    560 **Answer**
    561 
    562 Whenever $42\nmid x$.
    563 
    564 **Hint 3**
    565 
    566 If $42\mid x$, how can we determine if $x$ is *special*?
    567 
    568 **Answer**
    569 
    570 $x$ will be *special* if and only if $\frac{x}{42}$ is *special*.
    571 
    572 **Hint 4**
    573 
    574 Iterate on the number of operations $\bmod{42}$.
    575 
    576 **Tutorial**
    577 
    578 Tutorial is loading...
    579 
    580 **Code (C++)**
    581 
    582 ```
    583 #include <bits/stdc++.h>
    584 using namespace std;
    585 
    586 using ll = long long;
    587 const ll inf = LLONG_MAX / 2;
    588 
    589 ll f(const vector<ll>& a) {
    590     if (a.empty()) return 0;
    591     if (a.back() == 1) return 5;
    592     int n = a.size();
    593     int mod6 = a[0] % 6;
    594     vector<ll> groups[7];
    595     for (ll x : a) {
    596         if (x % 6 != mod6) return inf;
    597         groups[(x - mod6) / 6 % 7].push_back(x);
    598     }
    599     ll ans = inf;
    600     for (int r = 0; r < 7; r++) {
    601         ll k = (42 - 6*r - mod6) % 42;
    602         vector<ll> next;
    603         for (ll x : groups[r]) next.push_back((x + k) / 42);
    604         ll rec = f(next);
    605         if (rec >= inf) continue;
    606         ans = min(ans, k + 42 * rec);
    607     }
    608     return ans;
    609 }
    610 
    611 void solve() {
    612     int n;
    613     cin >> n;
    614     vector<ll> a(n);
    615     for (auto &x : a) cin >> x;
    616     sort(a.begin(), a.end());
    617     ll res = f(a);
    618     if (res >= inf) cout << "-1\n";
    619     else cout << res << '\n';
    620 }
    621 signed main() {
    622     cin.tie(0)->sync_with_stdio(0);
    623     int t = 1;
    624     cin >> t;
    625     while (t--) solve();
    626 }
    627 ```