codeforces-scrape

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

1476.md (15112B)


      1 Source: https://codeforces.com/blog/entry/87356
      2 
      3 [1476A - K-divisible Sum](/contest/1476/problem/A "Educational Codeforces Round 103 (Rated for Div. 2)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t; cin >> t;
     20   while(t--) {
     21     long long n, k;
     22     cin >> n >> k;
     23     
     24     long long cf = (n + k - 1) / k;
     25     k *= cf;
     26     
     27     cout << (k + n - 1) / n << endl;
     28   }
     29   return 0;
     30 }
     31 ```
     32 
     33 [1476B - Inflation](/contest/1476/problem/B "Educational Codeforces Round 103 (Rated for Div. 2)")
     34 
     35 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution (adedalic)**
     42 
     43 ```
     44 #include<bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 typedef long long li;
     49 
     50 const int INF = int(1e9);
     51 
     52 int main() {
     53   int t; cin >> t;
     54   while(t--) {
     55     int n, k;
     56     cin >> n >> k;
     57     vector<int> p(n);
     58     for (int i = 0; i < n; i++)
     59       cin >> p[i];
     60     
     61     li x = 0;
     62     li pSum = p[0];
     63     for (int i = 1; i < n; i++) {
     64       x = max(x, (100ll * p[i] - k * pSum + k - 1) / k);
     65       pSum += p[i];
     66     }
     67     cout << x << endl;
     68   }
     69   return 0;
     70 }
     71 ```
     72 
     73 [1476C - Longest Simple Cycle](/contest/1476/problem/C "Educational Codeforces Round 103 (Rated for Div. 2)")
     74 
     75 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution (adedalic)**
     82 
     83 ```
     84 #include<bits/stdc++.h>
     85 using namespace std;
     86 
     87 typedef long long li;
     88 
     89 int main() {
     90   int t;
     91   cin >> t;
     92 
     93   while (t--) {
     94     int n;
     95     cin >> n;
     96     vector<int> c(n), a(n), b(n);
     97     for (int i = 0; i < n; i++)
     98       cin >> c[i];
     99     for (int i = 0; i < n; i++)
    100       cin >> a[i];
    101     for (int i = 0; i < n; i++)
    102       cin >> b[i];
    103     
    104     li ans = 0;
    105     li lstLen = 0;
    106     for (int i = 1; i < n; i++) {
    107       li curLen = c[i] + 1ll + abs(a[i] - b[i]);
    108       if (a[i] != b[i])
    109         curLen = max(curLen, c[i] + 1ll + lstLen - abs(a[i] - b[i]));
    110       ans = max(ans, curLen);
    111       lstLen = curLen;  
    112     }
    113     cout << ans << endl;
    114   }
    115   return 0;
    116 };
    117 ```
    118 
    119 [1476D - Journey](/contest/1476/problem/D "Educational Codeforces Round 103 (Rated for Div. 2)")
    120 
    121 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution 1 (BledDest)**
    128 
    129 ```
    130 #include<bits/stdc++.h>
    131 
    132 using namespace std;
    133 
    134 const int INF = int(1e9);
    135 
    136 char buf[300043];
    137 
    138 int main()
    139 {
    140     int t;
    141     scanf("%d", &t);
    142     for(int _ = 0; _ < t; _++)
    143     {
    144         int n;
    145         scanf("%d", &n);
    146         scanf("%s", buf);
    147         string s = buf;
    148         vector<vector<int>> g(2 * n + 2);
    149         for(int i = 0; i < n; i++)
    150             if(s[i] == 'L')
    151             {
    152                 g[(i + 1) * 2].push_back(i * 2 + 1);
    153                 g[i * 2 + 1].push_back((i + 1) * 2);
    154             }
    155             else
    156             {
    157                 g[i * 2].push_back((i + 1) * 2 + 1);
    158                 g[(i + 1) * 2 + 1].push_back(i * 2);   
    159             }
    160         vector<int> comp(2 * n + 2, -1);
    161         vector<int> cnt;
    162         for(int i = 0; i < 2 * n + 2; i++)
    163         {
    164             if(comp[i] != -1) continue;
    165             int c = 1;
    166             int cc = cnt.size();
    167             queue<int> q;
    168             comp[i] = cc;
    169             q.push(i);
    170             while(!q.empty())
    171             {
    172                 int k = q.front();
    173                 q.pop();
    174                 for(auto y : g[k])
    175                 {
    176                     if(comp[y] == -1)
    177                     {
    178                         c++;
    179                         comp[y] = cc;
    180                         q.push(y);
    181                     }
    182                 }
    183             }
    184             cnt.push_back(c);
    185         }
    186         for(int i = 0; i <= n; i++)
    187             printf("%d%c", cnt[comp[i * 2]], " \n"[i == n]);
    188     }
    189 }
    190 ```
    191 
    192 **Solution 2 (BledDest)**
    193 
    194 ```
    195 t = int(input())
    196 
    197 for _ in range(t):
    198     n = int(input())
    199     s = input()
    200     dpl = [i for i in range(n + 1)]
    201     dpr = [i for i in range(n + 1)]
    202     for i in range(n + 1):
    203         if i == 0 or s[i - 1] == 'R':
    204             dpl[i] = i
    205         elif i == 1 or s[i - 2] == 'L':
    206             dpl[i] = i - 1
    207         else:
    208             dpl[i] = dpl[i - 2]
    209     for i in range(n, -1, -1):
    210         if i == n or s[i] == 'L':
    211             dpr[i] = i
    212         elif i == n - 1 or s[i + 1] == 'R':
    213             dpr[i] = i + 1
    214         else:
    215             dpr[i] = dpr[i + 2]
    216     ans = [(dpr[i] - dpl[i]) + 1 for i in range(n + 1)]
    217     print(*ans)
    218 ```
    219 
    220 [1476E - Pattern Matching](/contest/1476/problem/E "Educational Codeforces Round 103 (Rated for Div. 2)")
    221 
    222 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    223 
    224 **Tutorial**
    225 
    226 Tutorial is loading...
    227 
    228 **Solution 1 (awoo)**
    229 
    230 ```
    231 #include <bits/stdc++.h>
    232 
    233 #define forn(i, n) for (int i = 0; i < int(n); i++)
    234 
    235 using namespace std;
    236 
    237 struct pattern{
    238   string s;
    239   int i;
    240 };
    241 
    242 bool operator <(const pattern &a, const pattern &b){
    243   return a.s < b.s;
    244 }
    245 
    246 vector<vector<int>> g;
    247 vector<int> used, ord;
    248 bool cyc;
    249 
    250 void ts(int v){
    251   used[v] = 1;
    252   for (int u : g[v]){
    253     if (used[u] == 0)
    254       ts(u);
    255     else if (used[u] == 1)
    256       cyc = true;
    257     if (cyc)
    258       return;
    259   }
    260   used[v] = 2;
    261   ord.push_back(v);
    262 }
    263 
    264 int main() {
    265     cin.tie(0);
    266   ios_base::sync_with_stdio(false);
    267   int n, m, k;
    268   cin >> n >> m >> k;
    269   vector<pattern> p(n);
    270   g.assign(n, vector<int>());
    271   forn(i, n){
    272     cin >> p[i].s;
    273     p[i].i = i;
    274   }
    275   sort(p.begin(), p.end());
    276   pattern nw;
    277   nw.s = string(k, '_');
    278   forn(i, m){
    279     string cur;
    280     int mt;
    281     cin >> cur >> mt;
    282     --mt;
    283     bool ok = false;
    284     forn(mask, 1 << k){
    285       forn(j, k)
    286         nw.s[j] = ((mask >> j) & 1 ? cur[j] : '_');
    287       auto it = lower_bound(p.begin(), p.end(), nw);
    288       if (it != p.end() && it->s == nw.s){
    289         if (it->i != mt)
    290           g[mt].push_back(it->i);
    291         else
    292           ok = true;
    293       }
    294     }
    295     if (!ok){
    296       puts("NO");
    297       return 0;
    298     }
    299   }
    300   used.assign(n, 0);
    301   cyc = false;
    302   ord.clear();
    303   forn(i, n) if (!used[i]){
    304     ts(i);
    305     if (cyc){
    306       cout << "NO\n";
    307       return 0;
    308     }
    309   }
    310   reverse(ord.begin(), ord.end());
    311   cout << "YES\n";
    312   forn(i, n)
    313     cout << ord[i] + 1 << " ";
    314   cout << "\n";
    315   return 0;
    316 }
    317 ```
    318 
    319 **Solution 2 (awoo)**
    320 
    321 ```
    322 #include <bits/stdc++.h>
    323 
    324 #define forn(i, n) for (int i = 0; i < int(n); i++)
    325 
    326 using namespace std;
    327 
    328 struct pattern{
    329   string s;
    330   int i;
    331 };
    332 
    333 bool operator <(const pattern &a, const pattern &b){
    334   return a.s < b.s;
    335 }
    336 
    337 vector<vector<int>> g;
    338 vector<int> used, ord;
    339 bool cyc;
    340 
    341 void ts(int v){
    342   used[v] = 1;
    343   for (int u : g[v]){
    344     if (used[u] == 0)
    345       ts(u);
    346     else if (used[u] == 1)
    347       cyc = true;
    348     if (cyc)
    349       return;
    350   }
    351   used[v] = 2;
    352   ord.push_back(v);
    353 }
    354 
    355 struct node{
    356   int nxt[28];
    357   int term;
    358   node(){
    359     memset(nxt, -1, sizeof(nxt));
    360     term = -1;
    361   }
    362 };
    363 
    364 vector<node> trie;
    365 
    366 void add(const string &s, int i){
    367   int cur = 0;
    368   for (char c : s){
    369     int x = c - '_';
    370     if (trie[cur].nxt[x] == -1){
    371       trie[cur].nxt[x] = trie.size();
    372       trie.push_back(node());
    373     }
    374     cur = trie[cur].nxt[x];
    375   }
    376   trie[cur].term = i;
    377 }
    378 
    379 bool check(int i, int v, const string &s, int mt){
    380   if (i == int(s.size())){
    381     assert(trie[v].term != -1);
    382     if (trie[v].term != mt)
    383       g[mt].push_back(trie[v].term);
    384     else
    385       return true;
    386     return false;
    387   }
    388   bool res = false;
    389   if (trie[v].nxt[s[i] - '_'] != -1 && check(i + 1, trie[v].nxt[s[i] - '_'], s, mt))
    390     res = true;
    391   if (trie[v].nxt[0] != -1 && check(i + 1, trie[v].nxt[0], s, mt))
    392     res = true;
    393   return res;
    394 }
    395 
    396 int main() {
    397   cin.tie(0);
    398   ios_base::sync_with_stdio(false);
    399   trie = vector<node>(1);
    400   int n, m, k;
    401   cin >> n >> m >> k;
    402   g.assign(n, vector<int>());
    403   forn(i, n){
    404     string cur;
    405     cin >> cur;
    406     add(cur, i);
    407   }
    408   pattern nw;
    409   nw.s = string(k, '_');
    410   forn(i, m){
    411     string cur;
    412     int mt;
    413     cin >> cur >> mt;
    414     if (!check(0, 0, cur, mt - 1)){
    415       cout << "NO\n";
    416       return 0;
    417     }
    418   }
    419   used.assign(n, 0);
    420   cyc = false;
    421   ord.clear();
    422   forn(i, n) if (!used[i]){
    423     ts(i);
    424     if (cyc){
    425       cout << "NO\n";
    426       return 0;
    427     }
    428   }
    429   reverse(ord.begin(), ord.end());
    430   cout << "YES\n";
    431   forn(i, n)
    432     cout << ord[i] + 1 << " ";
    433   cout << "\n";
    434   return 0;
    435 }
    436 ```
    437 
    438 [1476F - Lanterns](/contest/1476/problem/F "Educational Codeforces Round 103 (Rated for Div. 2)")
    439 
    440 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    441 
    442 **Tutorial**
    443 
    444 Tutorial is loading...
    445 
    446 **Solution (BledDest)**
    447 
    448 ```
    449 #include<bits/stdc++.h>
    450 
    451 using namespace std;
    452 
    453 const int INF = int(1e9);
    454 
    455 struct segTree
    456 {
    457     int n;
    458     bool mx;
    459     vector<int> t;
    460 
    461     void fix(int v)
    462     {
    463         t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
    464     }
    465 
    466     void build(int v, int l, int r)
    467     {
    468         if(l == r - 1)
    469             t[v] = (mx ? -INF : INF);
    470         else
    471         {
    472             int m = (l + r) / 2;
    473             build(v * 2 + 1, l, m);
    474             build(v * 2 + 2, m, r);
    475             fix(v);
    476         }
    477     }
    478 
    479     void upd(int v, int l, int r, int pos, int val)
    480     {
    481         if(l == r - 1)
    482             t[v] = (mx ? max(t[v], val) : min(t[v], val));
    483         else
    484         {
    485             int m = (l + r) / 2;
    486             if(pos < m)
    487                 upd(v * 2 + 1, l, m, pos, val);
    488             else
    489                 upd(v * 2 + 2, m, r, pos, val);
    490             fix(v);
    491         }
    492     }
    493 
    494     int get(int v, int l, int r, int L, int R)
    495     {
    496         if(L >= R)
    497             return (mx ? -INF : INF);
    498         if(l == L && r == R)
    499             return t[v];
    500         int m = (l + r) / 2;
    501         int lf = get(v * 2 + 1, l, m, L, min(R, m));
    502         int rg = get(v * 2 + 2, m, r, max(m, L), R);
    503         return (mx ? max(lf, rg) : min(lf, rg));
    504     }
    505 
    506     void upd(int pos, int val)
    507     {
    508         upd(0, 0, n, pos, val);
    509     }
    510 
    511     int get(int L, int R)
    512     {
    513         return get(0, 0, n, L, R);
    514     }
    515 
    516     void build()
    517     {
    518         return build(0, 0, n);
    519     }
    520 
    521     segTree() {};
    522     segTree(int n, bool mx) : n(n), mx(mx)
    523     {
    524         t.resize(4 * n);
    525     }
    526 };
    527 
    528 int main()
    529 {
    530     int t;
    531     scanf("%d", &t);
    532     for(int _ = 0; _ < t; _++)
    533     {
    534         int n;
    535         scanf("%d", &n);
    536         vector<int> p(n);
    537         for(int i = 0; i < n; i++)
    538             scanf("%d", &p[i]);
    539         vector<int> dp(n + 1, -INF);
    540         vector<int> par(n + 1, -2);
    541         dp[0] = 0;
    542         par[0] = -1;
    543         vector<int> lf(n), rg(n);
    544         for(int i = 0; i < n; i++)
    545         {
    546             lf[i] = max(1, i - p[i] + 1);
    547             rg[i] = min(n, i + p[i] + 1);
    548         }
    549         segTree sn(n + 1, false);        
    550         segTree sx(n, true);
    551         sn.build();
    552         sx.build();
    553         for(int i = 0; i < n; i++)
    554             sx.upd(i, rg[i]);
    555         sn.upd(0, 0);
    556         for(int i = 1; i <= n; i++)
    557         {
    558             int j = i - 1;
    559             int k = lf[j] - 1;
    560             
    561             int m = sn.get(k, n + 1);                 
    562             if(m != INF)
    563             {
    564                 int nval = max(sx.get(m, i - 1), i - 1);
    565                 if(nval > dp[i])
    566                 {
    567                     dp[i] = nval;
    568                     par[i] = m;
    569                 }
    570             }
    571             if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
    572             {
    573                 dp[i] = max(dp[j], rg[j]);
    574                 par[i] = -1;
    575             }
    576             if(dp[j] > dp[i])
    577             {
    578                 dp[i] = dp[j];
    579                 par[i] = -1;
    580             }
    581             sn.upd(dp[i], i);                
    582         }
    583         if(dp[n] != n)
    584             puts("NO");
    585         else
    586         {
    587             puts("YES");
    588             string ans;
    589             int cur = n;
    590             while(cur != 0)
    591             {
    592                 if(par[cur] == -1)
    593                 {
    594                     cur--;
    595                     ans += "R";
    596                 }
    597                 else
    598                 {
    599                     int pcur = par[cur];
    600                     int diff = cur - pcur;
    601                     ans += "L";
    602                     for(int j = 0; j < diff - 1; j++)
    603                         ans += "R";
    604                     cur = pcur;    
    605                 }
    606             }
    607             reverse(ans.begin(), ans.end());
    608             puts(ans.c_str());
    609         }
    610     }
    611 }
    612 ```
    613 
    614 [1476G - Minimum Difference](/contest/1476/problem/G "Educational Codeforces Round 103 (Rated for Div. 2)")
    615 
    616 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    617 
    618 **Tutorial**
    619 
    620 Tutorial is loading...
    621 
    622 **Solution (Neon)**
    623 
    624 ```
    625 #include <bits/stdc++.h>
    626 
    627 using namespace std;
    628 
    629 #define x first
    630 #define y second
    631 #define sz(a) int((a).size())
    632 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    633 
    634 typedef pair<int, int> pt;
    635 
    636 const int N = 100 * 1000 + 13;
    637 const int P = 2000;
    638 
    639 struct query {
    640   int t, l, r, k, i;
    641 };
    642 
    643 int main() {
    644   int n, m;
    645   scanf("%d%d", &n, &m);
    646   vector<int> a(n);
    647   forn(i, n) scanf("%d", &a[i]);
    648   
    649   vector<query> q;
    650   vector<array<int, 3>> upd;
    651   
    652   forn(i, m) {
    653     int tp;
    654     scanf("%d", &tp);
    655     if (tp == 1) {
    656       int l, r, k;
    657       scanf("%d%d%d", &l, &r, &k);
    658       q.push_back({sz(upd), l - 1, r - 1, k, sz(q)});
    659     } else {
    660       int p, x;
    661       scanf("%d%d", &p, &x); --p;
    662       upd.push_back({p, a[p], x});
    663       a[p] = x;
    664     }
    665   }
    666   
    667   sort(q.begin(), q.end(), [](const query &a, const query &b) {
    668     if (a.t / P != b.t / P)
    669       return a.t < b.t;
    670     if (a.l / P != b.l / P)
    671       return a.l < b.l;
    672     if ((a.l / P) & 1)
    673       return a.r < b.r;
    674     return a.r > b.r; 
    675   });
    676   
    677   for (int i = sz(upd) - 1; i >= 0; --i)
    678     a[upd[i][0]] = upd[i][1];
    679   
    680   vector<int> cnt(N), ord(N);
    681   vector<pt> bounds(N, {N, 0});
    682   bounds[0] = {0, N - 1};
    683   int L = 0, R = -1, T = 0;
    684   
    685   auto add = [&](int x) {
    686     int c = cnt[x];
    687     ++ord[bounds[c].x];
    688     bounds[c + 1].y = bounds[c].x;
    689     if (bounds[c + 1].x == N)
    690       bounds[c + 1].x = bounds[c].x;
    691     if (bounds[c].x == bounds[c].y)
    692       bounds[c].x = N - 1;
    693     ++bounds[c].x;
    694     ++cnt[x];
    695   };
    696   
    697   auto rem = [&](int x) {
    698     int c = cnt[x];
    699     --ord[bounds[c].y];
    700     if (bounds[c - 1].x == N)
    701       bounds[c - 1].y = bounds[c].y;
    702     bounds[c - 1].x = bounds[c].y;
    703     if (bounds[c].x == bounds[c].y)
    704       bounds[c].x = N;
    705     --bounds[c].y;
    706     --cnt[x];
    707   };
    708   
    709   auto apply = [&](int i, int fl) {
    710     int p = upd[i][0];
    711     int x = upd[i][fl + 1];
    712     if (L <= p && p <= R) {
    713       rem(a[p]);
    714       add(x);
    715     }
    716     a[p] = x;
    717   };
    718   
    719   vector<int> ans(sz(q));
    720   
    721   for (auto qr : q) {
    722     int t = qr.t, l = qr.l, r = qr.r, k = qr.k;
    723     while (T < t) apply(T++, 1);
    724     while (T > t) apply(--T, 0);
    725     while (R < r) add(a[++R]);
    726     while (L > l) add(a[--L]);
    727     while (R > r) rem(a[R--]);
    728     while (L < l) rem(a[L++]);
    729     
    730     int res = N;
    731     for (int i = 0, j = 0, sum = 0; i < N && ord[i] > 0; i = bounds[ord[i]].y + 1) {
    732       while (j < N && ord[j] > 0 && sum < k) {
    733         sum += bounds[ord[j]].y - bounds[ord[j]].x + 1;
    734         j = bounds[ord[j]].y + 1;
    735       }
    736       if (sum >= k) res = min(res, ord[i] - ord[j - 1]);
    737       sum -= bounds[ord[i]].y - bounds[ord[i]].x + 1;
    738     }
    739     if (res == N) res = -1;
    740     ans[qr.i] = res;
    741   }
    742   
    743   for (int x : ans) printf("%d\n", x);
    744 }
    745 ```