codeforces-scrape

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

1923.md (8518B)


      1 Source: https://codeforces.com/blog/entry/126339
      2 
      3 [1923A - Moving Chips](/contest/1923/problem/A "Educational Codeforces Round 162 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     a = list(map(int, input().split()))
     18     l, r = a.index(1), n - a[::-1].index(1) - 1
     19     c = a.count(1)
     20     print(r - l - c + 1)
     21 ```
     22 
     23 [1923B - Monsters Attack!](/contest/1923/problem/B "Educational Codeforces Round 162 (Rated for Div. 2)")
     24 
     25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (Neon)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35  
     36 using namespace std;
     37  
     38 int main() {
     39   int t;
     40   cin >> t;
     41   while (t--) {
     42     int n, k;
     43     cin >> n >> k;
     44     vector<int> a(n), x(n);
     45     for (auto& it : a) cin >> it;
     46     for (auto& it : x) cin >> it;
     47     vector<long long> s(n + 1);
     48     for (int i = 0; i < n; ++i) s[abs(x[i])] += a[i];
     49     bool ok = true;
     50     long long lft = 0;
     51     for (int i = 1; i <= n; ++i) {
     52       lft += k - s[i];
     53       ok &= (lft >= 0);
     54     }
     55     cout << (ok ? "YES" : "NO") << '\n';
     56   }
     57 }
     58 ```
     59 
     60 [1923C - Find B](/contest/1923/problem/C "Educational Codeforces Round 162 (Rated for Div. 2)")
     61 
     62 Idea: [Roms](/profile/Roms "Master Roms")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (Roms)**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72  
     73 using namespace std;
     74  
     75 const int N = 300043;
     76  
     77 int t;
     78 int n, m;
     79 int a[N];
     80 long long sum[N];
     81 int cnt1[N];
     82  
     83 int main() {
     84     ios_base::sync_with_stdio(false);
     85     
     86     cin >> t;
     87     for (int tc = 0; tc < t; ++tc) {
     88         cin >> n >> m;
     89         memset(sum, 0, sizeof(sum[0]) * (n + 5));
     90         memset(cnt1, 0, sizeof(cnt1[0]) * (n + 5));
     91         for (int i = 0; i < n; ++i) {
     92             cin >> a[i];
     93             sum[i + 1] = sum[i] + a[i];
     94             cnt1[i + 1] = cnt1[i] + (a[i] == 1);
     95         }
     96         
     97         for (int i = 0; i < m; ++i) {
     98             int l, r;
     99             cin >> l >> r;
    100             --l;
    101             int cur_cnt1 = cnt1[r] - cnt1[l];
    102             long long cur_sum = sum[r] - sum[l];
    103             
    104             if((r - l) + cur_cnt1 <= cur_sum && r - l > 1)
    105                 cout << "YES\n";
    106             else
    107                 cout << "NO\n";
    108         }
    109     }
    110     return 0;
    111 }
    112 ```
    113 
    114 [1923D - Slimes](/contest/1923/problem/D "Educational Codeforces Round 162 (Rated for Div. 2)")
    115 
    116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    117 
    118 **Tutorial**
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (Neon)**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126  
    127 using namespace std;
    128  
    129 int main() {
    130   int t;
    131   cin >> t;
    132   while (t--) {
    133     int n;
    134     cin >> n;
    135     vector<int> a(n);
    136     for (auto& x : a) cin >> x;
    137     vector<int> ans(n, n);
    138     for (int z = 0; z < 2; ++z) {
    139       vector<long long> s(n + 1);
    140       for (int i = 0; i < n; ++i) s[i + 1] = s[i] + a[i];
    141       vector<int> p(n, -1);
    142       for (int i = 1; i < n; ++i) {
    143         int j = (z ? n - i - 1 : i);
    144         int l = 1, r = i;
    145         while (l <= r) {
    146           int m = (l + r) / 2;
    147           if (s[i] - s[i - m] > a[i] && p[i - 1] >= i - m) {
    148             ans[j] = min(ans[j], m);
    149             r = m - 1;
    150           } else {
    151             l = m + 1;
    152           }
    153         }
    154         if (a[i - 1] > a[i]) ans[j] = 1;
    155         p[i] = (a[i] == a[i - 1] ? p[i - 1] : i - 1);
    156       }
    157       reverse(a.begin(), a.end());
    158     }
    159     for (int i = 0; i < n; ++i)
    160       cout << (ans[i] == n ? -1 : ans[i]) << ' ';
    161     cout << '\n';
    162   }
    163 }
    164 ```
    165 
    166 [1923E - Count Paths](/contest/1923/problem/E "Educational Codeforces Round 162 (Rated for Div. 2)")
    167 
    168 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    169 
    170 **Tutorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Solution (awoo)**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178  
    179 #define forn(i, n) for (int i = 0; i < int(n); i++)
    180  
    181 using namespace std;
    182  
    183 int n;
    184 vector<int> a;
    185 vector<vector<int>> g;
    186  
    187 long long ans;
    188 vector<map<int, int>> cnt;
    189  
    190 void dfs(int v, int p = -1){
    191     int bst = -1;
    192     for (int u : g[v]) if (u != p){
    193         dfs(u, v);
    194         if (bst == -1 || cnt[bst].size() < cnt[u].size())
    195             bst = u;
    196     }
    197     for (int u : g[v]) if (u != p && u != bst){
    198         for (auto it : cnt[u]){
    199             int x = it.first, y = it.second;
    200             if (x != a[v]) ans += cnt[bst][x] * 1ll * y;
    201             cnt[bst][x] += y;
    202         }
    203     }
    204     if (bst != -1) swap(cnt[bst], cnt[v]);
    205     ans += cnt[v][a[v]];
    206     cnt[v][a[v]] = 1;
    207 }
    208  
    209 int main() {
    210     cin.tie(0);
    211     ios::sync_with_stdio(false);
    212     int t;
    213     cin >> t;
    214     while (t--){
    215         int n;
    216         cin >> n;
    217         a.resize(n);
    218         forn(i, n) cin >> a[i];
    219         g.assign(n, {});
    220         forn(_, n - 1){
    221             int v, u;
    222             cin >> v >> u;
    223             --v, --u;
    224             g[v].push_back(u);
    225             g[u].push_back(v);
    226         }
    227         ans = 0;
    228         cnt.assign(n, {});
    229         dfs(0);
    230         cout << ans << '\n';
    231     }
    232     return 0;
    233 }
    234 ```
    235 
    236 [1923F - Shrink-Reverse](/contest/1923/problem/F "Educational Codeforces Round 162 (Rated for Div. 2)")
    237 
    238 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    239 
    240 **Tutorial**
    241 
    242 Tutorial is loading...
    243 
    244 **Solution (adedalic)**
    245 
    246 ```
    247 #include<bits/stdc++.h>
    248  
    249 using namespace std;
    250  
    251 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    252 #define sz(a) int((a).size())
    253 #define all(a) (a).begin(), (a).end()
    254  
    255 typedef long long li;
    256 typedef pair<int, int> pt;
    257  
    258 const int INF = int(1e9);
    259 const int MOD = int(1e9) + 7;
    260  
    261 int add(int a, int b) {
    262     a += b;
    263     if (a >= MOD)
    264         a -= MOD;
    265     return a;
    266 }
    267 int mul(int a, int b) {
    268     return int(a * 1ll * b % MOD);
    269 }
    270  
    271 namespace SuffixArray {
    272     string s;
    273     vector< array<int, 2> > classes;
    274     
    275     vector<int> build(const string &bs) {
    276         s = bs;
    277         s += '$';
    278         
    279         vector<int> c(all(s)), ord(sz(s));
    280         iota(all(ord), 0);
    281         classes.resize(sz(s));
    282  
    283         for (int len = 1; len < 2 * sz(s); len <<= 1) {
    284             int half = len >> 1;
    285             fore (i, 0, sz(s))
    286                 classes[i] = {c[i], c[(i + half) % sz(s)]};
    287             
    288             sort(all(ord), [&](int i, int j) {
    289                 return classes[i] < classes[j];
    290             });
    291             c[ord[0]] = 0;
    292             fore (i, 1, sz(ord))
    293                 c[ord[i]] = c[ord[i - 1]] + (classes[ord[i - 1]] != classes[ord[i]]);
    294         }
    295         
    296         c.pop_back();
    297         for (int &cc : c)
    298             cc--;
    299         return c;
    300     }
    301 };
    302  
    303 int n, k;
    304 string s;
    305  
    306 inline bool read() {
    307     if(!(cin >> n >> k))
    308         return false;
    309     cin >> s;
    310     return true;
    311 }
    312  
    313 string calcZero(string s) {
    314     int rem = k;
    315     int pos = 0;
    316     for (int i = sz(s) - 1; rem > 0 && i >= 0; i--) {
    317         if (s[i] == '1')
    318             continue;
    319         
    320         while (pos < sz(s) && s[pos] == '0')
    321             pos++;
    322         if (pos >= i)
    323             break;
    324         
    325         swap(s[pos], s[i]);
    326         rem--;
    327     }
    328     return s.substr(s.find('1'));
    329 }
    330  
    331 string calcOne(string s) {
    332     reverse(all(s));
    333     
    334     auto c = SuffixArray::build(s);
    335     int cntOnes = count(all(s), '1');
    336     
    337     array<int, 3> mn = { 2 * sz(s), INF, -1 };
    338         
    339     int u = 0, curOnes = 0;
    340     fore (i, 0, n) {
    341         while (u < sz(s) && (u - i < cntOnes || cntOnes - curOnes > k - 1)) {
    342             curOnes += s[u] == '1';
    343             u++;
    344         }
    345         if (u - i < cntOnes || cntOnes - curOnes > k - 1)
    346             break;
    347         
    348         array<int, 3> curAns = { u - i, c[i], i };
    349         mn = min(mn, curAns);
    350         
    351         curOnes -= s[i] == '1';
    352     }
    353     assert(mn[2] >= 0);
    354     
    355     string res = s.substr(mn[2], mn[0]);
    356     int toAdd = cntOnes - count(all(res), '1');
    357     for (int i = sz(res) - 1; toAdd > 0 && i >= 0; i--) {
    358         if (res[i] == '0') {
    359             res[i] = '1';
    360             toAdd--;
    361         }
    362     }
    363     return res;
    364 }
    365  
    366 inline void solve() {
    367     auto s1 = calcZero(s);
    368     auto s2 = calcOne(s);
    369  
    370     if (sz(s1) > sz(s2) || (sz(s1) == sz(s2) && s1 > s2))
    371         swap(s1, s2);
    372     
    373     int res = 0;
    374     for (char c : s1)
    375         res = add(mul(res, 2), c - '0');
    376     cout << res << endl;
    377 }
    378  
    379 int main() {
    380 #ifdef _DEBUG
    381     freopen("input.txt", "r", stdin);
    382     int tt = clock();
    383 #endif
    384     ios_base::sync_with_stdio(false);
    385     cin.tie(0), cout.tie(0);
    386     cout << fixed << setprecision(15);
    387     
    388     if(read()) {
    389         solve();
    390         
    391 #ifdef _DEBUG
    392         cerr << "TIME = " << clock() - tt << endl;
    393         tt = clock();
    394 #endif
    395     }
    396     return 0;
    397 }
    398 ```