codeforces-scrape

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

1858.md (7988B)


      1 Source: https://codeforces.com/blog/entry/119398
      2 
      3 We hope you liked our problems!
      4 
      5 [1858A - Buttons](/contest/1858/problem/A "Codeforces Round 893 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     a, b, c = map(int, input().split())
     17     if c % 2 == 0:
     18         if a > b:
     19             print("First")
     20         else:
     21             print("Second")
     22     else:
     23         if b > a:
     24             print("Second")
     25         else:
     26             print("First")
     27 ```
     28 
     29 [1858B - The Walkway](/contest/1858/problem/B "Codeforces Round 893 (Div. 2)")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Code**
     36 
     37 ```
     38 #include <bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 int solve(int d, vector<int> x)
     43 {
     44     int ans = 0;
     45     for (int i = 1; i < x.size(); i++)
     46     {
     47         ans += (x[i] - x[i - 1] - 1) / d;
     48     }
     49     ans += int(x.size()) - 2;
     50     return ans;
     51 }
     52 
     53 void solve()
     54 {
     55     #define tests
     56 
     57     int n, m, d;
     58     cin >> n >> m >> d;
     59     vector<int> r(m);
     60     for (int i = 0; i < m; i++) cin >> r[i];
     61     r.insert(r.begin(), 1 - d);
     62     r.push_back(n + 1);
     63 
     64     int ans = 2e9;
     65     vector<int> res;
     66     for (int i = 1; i <= m; i++)
     67     {
     68         int A = r[i] - r[i - 1] - 1;
     69         int B = r[i + 1] - r[i] - 1;
     70         int C = r[i + 1] - r[i - 1] - 1;
     71         int D = C / d - (A / d + B / d);
     72         if (D < ans)
     73         {
     74             ans = D;
     75             res.clear();
     76         }
     77         if (D == ans)
     78         {
     79             res.push_back(r[i]);
     80         }
     81     }
     82     cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;
     83 }
     84 
     85 int main()
     86 {
     87     int t = 1;
     88     #ifdef tests
     89     cin >> t;
     90     #endif
     91     while (t--)
     92     {
     93         solve();
     94     }
     95 }
     96 ```
     97 
     98 [1858C - Yet Another Permutation Problem](/contest/1858/problem/C "Codeforces Round 893 (Div. 2)")
     99 
    100 **Tutorial**
    101 
    102 Tutorial is loading...
    103 
    104 **Code**
    105 
    106 ```
    107 #include<iostream>
    108 #include<vector>
    109 
    110 using namespace std;
    111 
    112 int main() {
    113     int t;
    114     cin >> t;
    115     while (t--) {
    116         int n;
    117         cin >> n;
    118         vector<int> a(n);
    119         int cur = 0;
    120         for (int i = 1; i <= n; i += 2) {
    121             for (int j = i; j <= n; j *= 2) {
    122                 a[cur++] = j;
    123             }
    124         }
    125         for (int i = 0; i<n; ++i) {
    126             cout << a[i] << " ";
    127         }
    128         cout << '\n';
    129     }
    130     return 0;
    131 }
    132 ```
    133 
    134 [1858D - Trees and Segments](/contest/1858/problem/D "Codeforces Round 893 (Div. 2)")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Code**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 
    145 #define int long long
    146 
    147 using namespace std;
    148 using ll = long long;
    149 
    150 void solve();
    151 
    152 template<typename ...Args>
    153 void println(Args... args) {
    154     apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
    155     cout << '\n';
    156 }
    157 
    158 int32_t main() {
    159     cin.tie(nullptr);
    160     ios_base::sync_with_stdio(false);
    161     int t = 1;
    162     cin >> t;
    163     for (int tc = 0; tc < t; ++tc) {
    164         solve();
    165     }
    166     return 0;
    167 }
    168 
    169 void solve() {
    170     int n, k;
    171     cin >> n >> k;
    172     string s;
    173     cin >> s;
    174     vector<int> max0by1(n + 1, -1e9);
    175     vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));
    176     vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));
    177     for (int l = 0; l < n; ++l) {
    178         int cnt1 = 0;
    179         for (int r = l + 1; r <= n; ++r) {
    180             cnt1 += s[r - 1] == '1';
    181             max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);
    182             max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);
    183         }
    184     }
    185     for (int r = 0; r <= n; ++r) {
    186         for (int cnt = 0; cnt <= n; ++cnt) {
    187             if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);
    188             if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);
    189         }
    190     }
    191     for (int l = n; l >= 0; --l) {
    192         for (int cnt = 0; cnt <= n; ++cnt) {
    193             if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);
    194             if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);
    195         }
    196     }
    197     vector<int> ans(n + 1, -1e9);
    198     for (int l = 0; l < n; ++l) {
    199         int cnt0 = 0;
    200         for (int r = l; r <= n; ++r) {
    201             if (r > l) cnt0 += s[r - 1] == '0';
    202             if (cnt0 > k) break;
    203             max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);
    204             max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);
    205         }
    206     }
    207     for (int i = 0; i <= n; ++i) {
    208         for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
    209     }
    210     for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    211     cout << '\n';
    212 }
    213 ```
    214 
    215 [1858E2 - Rollbacks (Hard Version)](/contest/1858/problem/E2 "Codeforces Round 893 (Div. 2)")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Code**
    222 
    223 ```
    224 #include <iostream>
    225 #include <vector>
    226 #include <numeric>
    227 #include <set>
    228 
    229 using namespace std;
    230 
    231 const int maxn = 1e6 + 1;
    232 
    233 int f[maxn];
    234 
    235 int get(int i) {
    236     int ans = 0;
    237     while (i >= 0) {
    238         ans += f[i];
    239         i = (i & (i + 1)) - 1;
    240     }
    241     return ans;
    242 }
    243 
    244 void upd(int i, int x) {
    245     while (i < maxn) {
    246         f[i] += x;
    247         i = i | (i + 1);
    248     }
    249 }
    250 
    251 int a[maxn];
    252 int rev[maxn];
    253 set<int> ids[maxn];
    254 
    255 int32_t main() {
    256     ios_base::sync_with_stdio(false);
    257     cin.tie(0);
    258     cout.tie(0);
    259     fill(rev, rev + maxn, -1);
    260     fill(a, a + maxn, -1);
    261     int q;
    262     cin >> q;
    263     int ptr = -1;
    264     vector<pair<pair<int, int>, int>> changes;
    265     while (q--) {
    266         char t;
    267         cin >> t;
    268         if (t == '?') {
    269             cout << get(ptr) << endl;
    270         } else if (t == '+') {
    271             int x;
    272             cin >> x;
    273             int mem = a[ptr + 1];
    274             if (a[ptr + 1] != -1) {
    275                 if (ids[a[ptr + 1]].size()) {
    276                     upd(*ids[a[ptr + 1]].begin(), -1);
    277                     ids[a[ptr + 1]].erase(ptr + 1);
    278                 }
    279                 if (ids[a[ptr + 1]].size()) {
    280                     upd(*ids[a[ptr + 1]].begin(), 1);
    281                 }
    282             }
    283             a[ptr + 1] = x;
    284             if (a[ptr + 1] != -1) {
    285                 if (ids[a[ptr + 1]].size()) {
    286                     upd(*ids[a[ptr + 1]].begin(), -1);
    287                 }
    288                 ids[x].insert(ptr + 1);
    289                 if (ids[a[ptr + 1]].size()) {
    290                     upd(*ids[a[ptr + 1]].begin(), 1);
    291                 }
    292             }
    293             ++ptr;
    294             changes.push_back({ { 1, mem }, -1 });
    295         } else if (t == '-') {
    296             int k;
    297             cin >> k;
    298             ptr -= k;
    299             changes.push_back({ { -1, k }, -1 });
    300         } else {
    301             if (changes.back().first.first == 1) {
    302                 if (a[ptr] != -1) {
    303                     if (ids[a[ptr]].size()) {
    304                         upd(*ids[a[ptr]].begin(), -1);
    305                         ids[a[ptr]].erase(ptr);
    306                     }
    307                     if (ids[a[ptr]].size()) {
    308                         upd(*ids[a[ptr]].begin(), 1);
    309                     }
    310                 }
    311                 a[ptr] = changes.back().first.second;
    312                 --ptr;
    313                 if (a[ptr + 1] != -1) {
    314                     if (ids[a[ptr + 1]].size()) {
    315                         upd(*ids[a[ptr + 1]].begin(), -1);
    316                     }
    317                     ids[a[ptr + 1]].insert(ptr + 1);
    318                     if (ids[a[ptr + 1]].size()) {
    319                         upd(*ids[a[ptr + 1]].begin(), 1);
    320                     }
    321                 }
    322             } else {
    323                 ptr += changes.back().first.second;
    324             }
    325             changes.pop_back();
    326         }
    327     }
    328 }
    329 ```
    330 
    331 **Note:** At about 20 minutes into the round one of our testers ([SomethingNew](/profile/SomethingNew "Grandmaster SomethingNew")) came up with a linear solution for problem E2, and [jiangly](/profile/jiangly "Legendary Grandmaster jiangly") implemented the same solution shortly after the contest! For further details, see [219001999](/contest/1858/submission/219001999 "Submission 219001999 by jiangly"). The main idea (as [jiangly](/profile/jiangly "Legendary Grandmaster jiangly") pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.