codeforces-scrape

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

2144.md (14921B)


      1 Source: https://codeforces.com/blog/entry/146474
      2 
      3 [2144A - Cut the Array](/contest/2144/problem/A "Educational Codeforces Round 182 (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     if sum(a) % 3 == 0:
     19         print("1 2")
     20     else:
     21         print("0 0")
     22 ```
     23 
     24 [2144B - Maximum Cost Permutation](/contest/2144/problem/B "Educational Codeforces Round 182 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (BledDest)**
     33 
     34 ```
     35 #include<bits/stdc++.h>
     36  
     37 using namespace std;
     38  
     39 void solve()
     40 {
     41     int n;
     42     cin >> n;
     43     vector<int> p(n);
     44     vector<int> pos0;
     45     vector<int> used(n);
     46     for(int i = 0; i < n; i++)
     47     {
     48         cin >> p[i];
     49         --p[i];
     50         if(p[i] == -1)
     51             pos0.push_back(i);
     52         else
     53             used[p[i]] = 1;
     54     }
     55     if(pos0.size() == 1) 
     56     {
     57         int unused = 0;
     58         for(int i = 0; i < n; i++) if(used[i] == 0) unused = i;
     59         p[pos0[0]] = unused;
     60     }
     61     int l = 0, r = n - 1;
     62     while(l < n && p[l] == l) l++;
     63     while(r >= 0 && p[r] == r) r--;
     64     cout << max(0, r - l + 1) << "\n";
     65 }
     66  
     67 int main()
     68 {
     69     ios_base::sync_with_stdio(0);
     70     cin.tie(0);
     71     int t;
     72     cin >> t;
     73     for(int i = 0; i < t; i++)
     74         solve();
     75 }
     76 ```
     77 
     78 [2144C - Non-Descending Arrays](/contest/2144/problem/C "Educational Codeforces Round 182 (Rated for Div. 2)")
     79 
     80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution (Neon)**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90  
     91 using namespace std;
     92  
     93 const int MOD = 998244353;
     94  
     95 int main() {
     96   int t;
     97   cin >> t;
     98   while (t--) {
     99     int n;
    100     cin >> n;
    101     vector<int> a(n), b(n);
    102     for (auto &x : a) cin >> x;
    103     for (auto &x : b) cin >> x;
    104     int ans = 1;
    105     for (int i = 0; i < n; ++i) {
    106       if (a[i] > b[i]) swap(a[i], b[i]);
    107       if (!i || a[i] >= b[i - 1]) ans = (ans * 2LL) % MOD;
    108     }
    109     cout << ans << '\n';
    110   }
    111 }
    112 ```
    113 
    114 [2144D - Price Tags](/contest/2144/problem/D "Educational Codeforces Round 182 (Rated for Div. 2)")
    115 
    116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    117 
    118 **Tutorial**
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (adedalic)**
    123 
    124 ```
    125 for _t in range(int(input())):
    126     n, y = map(int, input().split())
    127     a = list(map(int, input().split()))
    128     A = max(a) + 1
    129     cntTags = [0] * A
    130     for v in a:
    131         cntTags[v] += 1
    132     pSum = [0] * A
    133     for i in range(1, A):
    134         pSum[i] = pSum[i - 1] + cntTags[i]
    135     
    136     ans = -(10**18)
    137     if A == 2:
    138         print(n)
    139         continue
    140     for x in range(2, A):
    141         res = 0
    142         for price in range(1, A):
    143             l = x * (price - 1)
    144             r = min(A - 1, x * price)
    145             if l >= A:
    146                 break
    147             cnt = pSum[r] - pSum[l]
    148             res += cnt * price
    149             res -= y * max(0, cnt - cntTags[price])
    150         ans = max(ans, res)
    151     print(ans)
    152 ```
    153 
    154 [2144E1 - Looking at Towers (easy version)](/contest/2144/problem/E1 "Educational Codeforces Round 182 (Rated for Div. 2)")
    155 
    156 Idea: [Roms](/profile/Roms "Master Roms")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 [2144E2 - Looking at Towers (difficult version)](/contest/2144/problem/E2 "Educational Codeforces Round 182 (Rated for Div. 2)")
    163 
    164 Idea: [Roms](/profile/Roms "Master Roms")
    165 
    166 **Tutorial**
    167 
    168 Tutorial is loading...
    169 
    170 **Solution (BledDest)**
    171 
    172 ```
    173 #include<bits/stdc++.h>
    174  
    175 using namespace std;
    176  
    177 const int MOD = 998244353;
    178 const int N = 1000043;
    179  
    180 int add(int x, int y)
    181 {
    182     x += y;
    183     while(x >= MOD) x -= MOD;
    184     while(x < 0) x += MOD;
    185     return x;
    186 }
    187  
    188 int mul(int x, int y)
    189 {
    190     return (x * 1ll * y) % MOD;
    191 }   
    192  
    193 int binpow(int x, int y)
    194 {
    195     int z = 1;
    196     while(y > 0)
    197     {
    198         if(y % 2 == 1) z = mul(z, x);
    199         x = mul(x, x);
    200         y /= 2;
    201     }
    202     return z;
    203 }
    204  
    205 vector<int> get(const vector<int>& a)
    206 {
    207     int cur = -1;
    208     vector<int> res;
    209     for(auto x : a)
    210         if(x > cur)
    211         {
    212             res.push_back(x);
    213             cur = x;
    214         }
    215     return res;
    216 }
    217  
    218 struct SegTree
    219 {
    220     vector<int> f;
    221     vector<int> t;
    222     int n;
    223  
    224     int getVal(int v, int pos)
    225     {
    226         return mul(t[pos], binpow(2, f[v]));
    227     }   
    228  
    229     void push(int v)
    230     {
    231         if(f[v] != 0)
    232         {
    233             f[2 * v + 1] += f[v];
    234             f[2 * v + 2] += f[v];
    235             f[v] = 0;
    236         }
    237     }
    238  
    239     void resolve(int v, int pos)
    240     {
    241         if(f[v] != 0)
    242         {
    243             t[pos] = mul(t[pos], binpow(2, f[v]));
    244             f[v] = 0;    
    245         }
    246     }
    247  
    248     int get(int v, int l, int r, int pos)
    249     {
    250         if(l == r - 1)
    251             return getVal(v, pos);
    252         else
    253         {
    254             push(v);
    255             int m = (l + r) / 2;
    256             if(pos < m)
    257                 return get(v * 2 + 1, l, m, pos);
    258             else
    259                 return get(v * 2 + 2, m, r, pos);
    260         }
    261     }
    262  
    263     int get(int pos)
    264     {
    265         return get(0, 0, n, pos);
    266     }
    267  
    268     void inc(int v, int l, int r, int pos, int val)
    269     {
    270         if(l == r - 1)
    271         {
    272             resolve(v, pos);
    273             t[pos] = add(t[pos], val);
    274         }
    275         else
    276         {
    277             push(v);
    278             int m = (l + r) / 2;
    279             if(pos < m)
    280                 inc(v * 2 + 1, l, m, pos, val);
    281             else
    282                 inc(v * 2 + 2, m, r, pos, val);
    283         }
    284     }
    285  
    286     void inc(int pos, int val)
    287     {
    288         return inc(0, 0, n, pos, val);
    289     }
    290  
    291     void mulBy2(int v, int l, int r, int L, int R)
    292     {
    293         if(L >= R) return;
    294         if(l == L && r == R)
    295             f[v]++;
    296         else
    297         {
    298             push(v);
    299             int m = (l + r) / 2;
    300             mulBy2(v * 2 + 1, l, m, L, min(R, m));
    301             mulBy2(v * 2 + 2, m, r, max(L, m), R);
    302         }
    303     }
    304  
    305     void mulBy2(int l, int r)
    306     {
    307         mulBy2(0, 0, n, l, r);   
    308     }
    309  
    310     SegTree(int n = 0)
    311     {
    312         this->n = n;
    313         f.resize(4 * n);
    314         t.resize(n);
    315     }
    316 };
    317  
    318 vector<int> calc(const vector<int>& a, const vector<int>& b)
    319 {
    320     int n = a.size();
    321     int m = b.size();
    322     SegTree tree(m + 1);
    323     tree.inc(0, 1);
    324     vector<int> res(n);
    325     int maxVal = b.back();
    326     for(int i = 0; i < n; i++)
    327     {
    328         int x = a[i];
    329         if(x > maxVal) continue;
    330         else
    331         {
    332             if (x == maxVal) res[i] = tree.get(m - 1);
    333             int lf = lower_bound(b.begin(), b.end(), x) - b.begin();
    334             tree.mulBy2(lf + 1, m + 1);
    335             if(b[lf] == x)
    336             {
    337                 int cur = tree.get(lf);
    338                 tree.inc(lf + 1, cur);
    339             }
    340         }
    341     }
    342     return res; 
    343 }   
    344  
    345 void solve()
    346 {
    347     int n;
    348     cin >> n;
    349     vector<int> a(n);
    350     for(int i = 0; i < n; i++)
    351         cin >> a[i];
    352     auto left_view = get(a);
    353     reverse(a.begin(), a.end());
    354     auto right_view = get(a);
    355     reverse(a.begin(), a.end());
    356  
    357     auto dpL = calc(a, left_view);
    358     reverse(a.begin(), a.end());
    359     auto dpR = calc(a, right_view);
    360     reverse(a.begin(), a.end());
    361     reverse(dpR.begin(), dpR.end());
    362  
    363     int maxVal = *max_element(a.begin(), a.end());
    364     int ans = 0;
    365     int sumLeft = 0;
    366     for(int i = 0; i < n; i++)
    367     {
    368         if(a[i] > maxVal) continue;
    369         else
    370         {   
    371             if(a[i] == maxVal) ans = add(ans, mul(add(sumLeft, dpL[i]), dpR[i]));
    372             sumLeft = mul(sumLeft, 2);
    373             if(a[i] == maxVal) sumLeft = add(sumLeft, dpL[i]);
    374         }
    375     }
    376     cout << ans << endl;
    377 }
    378  
    379 int main()
    380 {
    381     ios_base::sync_with_stdio(0);
    382     cin.tie(0);    
    383     int t;
    384     cin >> t;
    385     for(int i = 0; i < t; i++) solve();
    386 }
    387 ```
    388 
    389 [2144F - Bracket Groups](/contest/2144/problem/F "Educational Codeforces Round 182 (Rated for Div. 2)")
    390 
    391 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    392 
    393 **Tutorial**
    394 
    395 Tutorial is loading...
    396 
    397 **Solution 1 (awoo)**
    398 
    399 ```
    400 #include <bits/stdc++.h>
    401  
    402 #define forn(i, n) for (int i = 0; i < int(n); i++)
    403  
    404 using namespace std;
    405  
    406 const string al = "()";
    407  
    408 struct aho_corasick {
    409     static const int AL = 2;
    410  
    411     struct node {
    412         int nxt[AL], go[AL];
    413         int p, pch;
    414         int suf, ssuf;
    415         bool term;
    416         
    417         node() {
    418             memset(nxt, -1, sizeof(nxt));
    419             memset(go, -1, sizeof(go));
    420             suf = ssuf = -1;
    421             term = false;
    422         }
    423     };
    424  
    425     vector<node> nodes;
    426     vector<vector<int>> g;
    427     
    428     aho_corasick() {
    429         nodes.push_back(node());
    430     }
    431  
    432     void add(const string& s) {
    433         int v = 0;
    434         forn(i, s.size()) {
    435             int c = al.find(s[i]);
    436             if (nodes[v].nxt[c] == -1) {
    437                 nodes.push_back(node());
    438                 nodes[v].nxt[c] = nodes.size() - 1;
    439                 nodes.back().p = v;
    440                 nodes.back().pch = c;
    441             }
    442             v = nodes[v].nxt[c];
    443         }
    444         nodes[v].term = true;
    445     }
    446     
    447     int go(int v, int c) {
    448         if (nodes[v].go[c] != -1)
    449             return nodes[v].go[c];
    450         if (nodes[v].nxt[c] != -1)
    451             return nodes[v].go[c] = nodes[v].nxt[c];
    452         if (v == 0)
    453             return nodes[v].go[c] = 0;
    454         return nodes[v].go[c] = go(suf(v), c);
    455     }
    456     
    457     int suf(int v) {
    458         if (nodes[v].suf != -1)
    459             return nodes[v].suf;
    460         if (v == 0 || nodes[v].p == 0)
    461             return nodes[v].suf = 0;
    462         return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    463     }
    464     
    465     int ssuf(int v) {
    466         if (nodes[v].ssuf != -1)
    467             return nodes[v].ssuf;
    468         if (v == 0 || nodes[v].p == 0)
    469             return nodes[v].ssuf = 0;
    470         int s = suf(v);
    471         if (nodes[s].term)
    472             return nodes[v].ssuf = s;
    473         return nodes[v].ssuf = ssuf(s);
    474     }
    475     
    476     void build_tree() {
    477         g.resize(nodes.size());
    478         forn(v, nodes.size()) {
    479             int u = suf(v);
    480             if (v != u)
    481                 g[u].push_back(v);
    482         }
    483     }
    484 };
    485  
    486 int main() {
    487     int n, k;
    488     cin >> n >> k;
    489     vector<string> s(n);
    490     forn(i, n) cin >> s[i];
    491     forn(i, n) if (s[i] == "()"){
    492         cout << -1 << '\n';
    493         return 0;
    494     }
    495     aho_corasick ac;
    496     forn(i, n) ac.add(s[i]);
    497     vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.nodes.size(), vector<char>(k + 1)));
    498     vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.nodes.size(), vector<pair<int, int>>(k + 1)));
    499     dp[0][0][0] = true;
    500     forn(i, k) forn(v, ac.nodes.size()) forn(bal, i + 1) if (dp[i][v][bal]){
    501         forn(c, 2){
    502             int nbal = bal + (c == 0 ? 1 : -1);
    503             if (nbal < 0) continue;
    504             int u = ac.go(v, c);
    505             if (ac.nodes[u].term || ac.ssuf(u) != 0) continue;
    506             dp[i + 1][u][nbal] = true;
    507             p[i + 1][u][nbal] = {v, c};
    508         }
    509     }
    510     int sv = -1;
    511     forn(v, ac.nodes.size()) if (dp[k][v][0]){
    512         sv = v;
    513         break;
    514     }
    515     if (sv == -1){
    516         cout << 2 << '\n';
    517         vector<string> res(2);
    518         forn(i, k / 2){
    519             res[0] += "()";
    520             res[1] += '(';
    521         }
    522         forn(i, k / 2){
    523             res[1] += ')';
    524         }
    525         vector<vector<int>> ans(2);
    526         forn(i, n){
    527             bool any = false;
    528             forn(j, int(s[i].size()) - 1)
    529                 any |= s[i][j] == s[i][j + 1];
    530             ans[!any].push_back(i);
    531         }
    532         forn(i, 2){
    533             cout << res[i] << '\n';
    534             cout << ans[i].size() << '\n';
    535             for (int j : ans[i]) cout << j + 1 << " ";
    536             cout << '\n';
    537         }
    538     }
    539     else{
    540         cout << 1 << '\n';
    541         string res = "";
    542         int bal = 0, v = sv;
    543         for (int i = k; i > 0; --i){
    544             auto [u, c] = p[i][v][bal];
    545             v = u;
    546             res += al[c];
    547             bal -= c == 0 ? 1 : -1;
    548         }
    549         reverse(res.begin(), res.end());
    550         cout << res << '\n';
    551         cout << n << '\n';
    552         forn(i, n) cout << i + 1 << " ";
    553         cout << '\n';
    554     }
    555     return 0;
    556 }
    557 ```
    558 
    559 **Solution 2 (awoo)**
    560 
    561 ```
    562 #include <bits/stdc++.h>
    563  
    564 #define forn(i, n) for (int i = 0; i < int(n); i++)
    565  
    566 using namespace std;
    567  
    568 const string al = "()";
    569  
    570 int main() {
    571     int n, k;
    572     cin >> n >> k;
    573     vector<string> s(n);
    574     forn(i, n) cin >> s[i];
    575     forn(i, n) if (s[i] == "()"){
    576         cout << -1 << '\n';
    577         return 0;
    578     }
    579  
    580     vector<string> ac(1, "");
    581     forn(i, n) forn(j, s[i].size())
    582         ac.push_back(s[i].substr(0, j + 1));
    583     sort(ac.begin(), ac.end());
    584     ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
    585  
    586     vector<char> bad(ac.size());
    587     set<string> tot(s.begin(), s.end());
    588     vector<vector<int>> go(ac.size(), vector<int>(2));
    589     forn(i, ac.size()) forn(j, ac[i].size() + 1){
    590         bad[i] |= tot.count(ac[i].substr(j));
    591         forn(t, 2) if (go[i][t] == 0){
    592             string nw = ac[i].substr(j) + al[t];
    593             auto it = lower_bound(ac.begin(), ac.end(), nw);
    594             if (it != ac.end() && *it == nw)
    595                 go[i][t] = it - ac.begin();
    596         }
    597     }
    598  
    599     vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.size(), vector<char>(k + 1)));
    600     vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.size(), vector<pair<int, int>>(k + 1)));
    601     dp[0][0][0] = true;
    602     forn(i, k) forn(v, ac.size()) forn(bal, i + 1) if (dp[i][v][bal]){
    603         forn(c, 2){
    604             int nbal = bal + (c == 0 ? 1 : -1);
    605             if (nbal < 0) continue;
    606             int u = go[v][c];
    607             if (bad[u]) continue;
    608             dp[i + 1][u][nbal] = true;
    609             p[i + 1][u][nbal] = {v, c};
    610         }
    611     }
    612     int sv = -1;
    613     forn(v, ac.size()) if (dp[k][v][0]){
    614         sv = v;
    615         break;
    616     }
    617     if (sv == -1){
    618         cout << 2 << '\n';
    619         vector<string> res(2);
    620         forn(i, k / 2){
    621             res[0] += "()";
    622             res[1] += '(';
    623         }
    624         forn(i, k / 2){
    625             res[1] += ')';
    626         }
    627         vector<vector<int>> ans(2);
    628         forn(i, n){
    629             bool any = false;
    630             forn(j, int(s[i].size()) - 1)
    631                 any |= s[i][j] == s[i][j + 1];
    632             ans[!any].push_back(i);
    633         }
    634         forn(i, 2){
    635             cout << res[i] << '\n';
    636             cout << ans[i].size() << '\n';
    637             for (int j : ans[i]) cout << j + 1 << " ";
    638             cout << '\n';
    639         }
    640     }
    641     else{
    642         cout << 1 << '\n';
    643         string res = "";
    644         int bal = 0, v = sv;
    645         for (int i = k; i > 0; --i){
    646             auto [u, c] = p[i][v][bal];
    647             v = u;
    648             res += al[c];
    649             bal -= c == 0 ? 1 : -1;
    650         }
    651         reverse(res.begin(), res.end());
    652         cout << res << '\n';
    653         cout << n << '\n';
    654         forn(i, n) cout << i + 1 << " ";
    655         cout << '\n';
    656     }
    657     return 0;
    658 }
    659 ```