codeforces-scrape

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

1913.md (12004B)


      1 Source: https://codeforces.com/blog/entry/123493
      2 
      3 [1913A - Rating Increase](/contest/1913/problem/A "Educational Codeforces Round 160 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [awoo](/profile/awoo "Master awoo")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     ab = input()
     16     for i in range(1, len(ab)):
     17         if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
     18             print(ab[:i], ab[i:])
     19             break
     20     else:
     21         print(-1)
     22 ```
     23 
     24 [1913B - Swap and Delete](/contest/1913/problem/B "Educational Codeforces Round 160 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (adedalic)**
     33 
     34 ```
     35 for _ in range(int(input())):
     36     s = input()
     37     cnt = [0, 0]
     38     for i in range(len(s)):
     39         cnt[int(s[i])] += 1
     40     for i in range(len(s) + 1):
     41         if (i == len(s) or cnt[1 - int(s[i])] == 0):
     42             print(len(s) - i)
     43             break
     44         cnt[1 - int(s[i])] -= 1
     45 ```
     46 
     47 [1913C - Game with Multiset](/contest/1913/problem/C "Educational Codeforces Round 160 (Rated for Div. 2)")
     48 
     49 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume")
     50 
     51 **Tutorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution (awoo)**
     56 
     57 ```
     58 from sys import stdin, stdout
     59 
     60 LOG = 30
     61 cnt = [0 for i in range(LOG)]
     62 ans = []
     63 for _ in range(int(stdin.readline())):
     64     t, v = map(int, stdin.readline().split())
     65     if t == 1:
     66         cnt[v] += 1
     67     else:
     68         nw = 0
     69         for i in range(LOG):
     70             r = (v % (2 << i)) // (1 << i)
     71             if r > nw + cnt[i]:
     72                 ans.append(0)
     73                 break
     74             v -= r
     75             nw = (nw + cnt[i] - r) // 2
     76         else:
     77             ans.append(nw >= (v >> 30))
     78 stdout.write('\n'.join(["YES" if x else "NO" for x in ans]))
     79 ```
     80 
     81 [1913D - Array Collapse](/contest/1913/problem/D "Educational Codeforces Round 160 (Rated for Div. 2)")
     82 
     83 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution (Roms)**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 
     94 using namespace std;
     95 
     96 const int MOD = 998244353;
     97 
     98 int normalize(long long x) {
     99     x %= MOD;
    100     if (x < 0) x += MOD;
    101     return x;
    102 }
    103 
    104 int main() {
    105     int t;
    106     cin >> t;
    107     for (int tc = 0; tc < t; ++tc) {
    108         int n;
    109         cin >> n;
    110         vector <int> a(n);
    111         vector <int> nextMin(n);
    112         vector <int> dpSum(n + 2);
    113         vector <int> dpNext(n);
    114         for (int i = 0; i < n; ++i)
    115             cin >> a[i];
    116         
    117         stack <int> stMin;
    118         nextMin[n - 1] = n;
    119         dpSum[n] = 1;
    120         for (int pos = n - 1; pos >= 0; --pos) {
    121             while(!stMin.empty() && a[stMin.top()] > a[pos])
    122                 stMin.pop();
    123             nextMin[pos] = stMin.empty() ? n : stMin.top();
    124             stMin.push(pos);
    125             
    126             int nxtPos = nextMin[pos];
    127             int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]);
    128             if (nxtPos != n) {
    129                 dpPos = normalize(dpPos + dpNext[nxtPos]);
    130                 dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]);
    131             }
    132             dpSum[pos] = normalize(dpPos + dpSum[pos + 1]);
    133             
    134             //cout << pos << ' ' << nxtPos << ' ' << dpPos << endl;
    135         }
    136         
    137         int res = 0;
    138         int mn = a[0];
    139         for(int i = 0; i < n; ++i) {
    140             mn = min(mn, a[i]);
    141             if (a[i] == mn) {
    142                 res = normalize(res + dpSum[i] - dpSum[i + 1]);
    143             }
    144         }
    145         cout << res << endl;
    146     }
    147     return 0;
    148 }
    149 ```
    150 
    151 [1913E - Matrix Problem](/contest/1913/problem/E "Educational Codeforces Round 160 (Rated for Div. 2)")
    152 
    153 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution (BledDest)**
    160 
    161 ```
    162 #include<bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 const int N = 111;
    167 
    168 struct edge
    169 {
    170     int y, c, w, f;
    171     edge() {};
    172     edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
    173 };
    174 
    175 vector<edge> e;
    176 vector<int> g[N];
    177 
    178 int rem(int x)
    179 {
    180     return e[x].c - e[x].f;
    181 }
    182 
    183 void add_edge(int x, int y, int c, int w)
    184 {
    185     g[x].push_back(e.size());
    186     e.push_back(edge(y, c, w, 0));
    187     g[y].push_back(e.size());
    188     e.push_back(edge(x, 0, -w, 0));
    189 }
    190 
    191 int n, m, s, t, v;
    192 
    193 pair<int, long long> MCMF()
    194 {
    195     int flow = 0;
    196     long long cost = 0;
    197     while(true)
    198     {
    199         vector<long long> d(v, (long long)(1e18));
    200         vector<int> p(v, -1);
    201         vector<int> pe(v, -1);
    202         queue<int> q;
    203         vector<bool> inq(v);
    204         q.push(s);
    205         inq[s] = true;
    206         d[s] = 0;
    207         while(!q.empty())
    208         {
    209             int k = q.front();
    210             q.pop();
    211             inq[k] = false;
    212             for(auto ei : g[k])
    213             {
    214                 if(rem(ei) == 0) continue;
    215                 int to = e[ei].y;
    216                 int w = e[ei].w;
    217                 if(d[to] > d[k] + w)
    218                 {
    219                     d[to] = d[k] + w;
    220                     p[to] = k;
    221                     pe[to] = ei;
    222                     if(!inq[to])
    223                     {
    224                         inq[to] = true;
    225                         q.push(to);
    226                     }
    227                 }
    228             }
    229         }
    230         if(p[t] == -1) break;
    231         flow++;
    232         cost += d[t];
    233         int cur = t;
    234         while(cur != s)
    235         {
    236             e[pe[cur]].f++;
    237             e[pe[cur] ^ 1].f--;
    238             cur = p[cur];
    239         }
    240     }
    241     return make_pair(flow, cost);
    242 }
    243 
    244 int get_sum(const vector<int>& v)
    245 {
    246     int sum = 0;
    247     for(auto x : v) sum += x;
    248     return sum;
    249 }
    250 
    251 int main()
    252 {
    253     cin >> n >> m;
    254     s = n + m;
    255     t = n + m + 1;
    256     v = n + m + 2;
    257     int sum_matrix = 0;
    258     vector<int> A(n), B(m);
    259     for(int i = 0; i < n; i++)
    260         for(int j = 0; j < m; j++)
    261         {
    262             int x;
    263             cin >> x;
    264             sum_matrix += x;
    265             if(x == 1)
    266                 add_edge(i, j + n, 1, 0);
    267             else
    268                 add_edge(i, j + n, 1, 1);
    269         }
    270     for(int i = 0; i < n; i++)
    271     {
    272         cin >> A[i];
    273         add_edge(s, i, A[i], 0);
    274     }
    275     for(int i = 0; i < m; i++) 
    276     {
    277         cin >> B[i];
    278         add_edge(i + n, t, B[i], 0);
    279     }
    280     
    281     auto res = MCMF();
    282     if(res.first != get_sum(A) || res.first != get_sum(B))
    283         cout << -1 << endl;
    284     else
    285         cout << sum_matrix - res.first + res.second * 2 << endl;
    286 }
    287 ```
    288 
    289 [1913F - Palindromic Problem](/contest/1913/problem/F "Educational Codeforces Round 160 (Rated for Div. 2)")
    290 
    291 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution (awoo)**
    298 
    299 ```
    300 #include <bits/stdc++.h>
    301 
    302 #define forn(i, n) for (int i = 0; i < int(n); i++)
    303 #define x first
    304 #define y second
    305 
    306 using namespace std;
    307 
    308 struct sparse_table {
    309     vector<vector<int>> st;
    310     vector<int> pw;
    311     
    312     sparse_table() {}
    313     
    314     sparse_table(const vector<int> &a) {
    315         int n = a.size();
    316         int logn = 32 - __builtin_clz(n);
    317         st.resize(logn, vector<int>(n));
    318         forn(i, n)
    319             st[0][i] = a[i];
    320         for (int j = 1; j < logn; ++j) forn(i, n) {
    321             st[j][i] = st[j - 1][i];
    322             if (i + (1 << (j - 1)) < n)
    323                 st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
    324         }
    325         pw.resize(n + 1);
    326         pw[0] = pw[1] = 0;
    327         for (int i = 2; i <= n; ++i)
    328             pw[i] = pw[i >> 1] + 1;
    329     }
    330     
    331     int get(int l, int r) {
    332         if (l >= r) return 1e9;
    333         int len = pw[r - l];
    334         return min(st[len][l], st[len][r - (1 << len)]);
    335     }
    336 };
    337 
    338 struct suffix_array {
    339     vector<int> c, pos;
    340     vector<pair<pair<int, int>, int>> p, nw;
    341     vector<int> cnt;
    342     int n;
    343     
    344     void radix_sort(int max_al) {
    345         cnt.assign(max_al, 0);
    346         forn(i, n) ++cnt[p[i].x.y];
    347         for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
    348         nw.resize(n);
    349         forn(i, n) nw[--cnt[p[i].x.y]] = p[i];
    350         cnt.assign(max_al, 0);
    351         forn(i, n) ++cnt[nw[i].x.x];
    352         for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
    353         for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i];
    354     }
    355     
    356     vector<int> lcp;
    357     sparse_table st;
    358     
    359     int get_lcp(int l, int r) {
    360         l = c[l], r = c[r];
    361         if (l > r) swap(l, r);
    362         return st.get(l, r);
    363     }
    364     
    365     suffix_array(const string &s) {
    366         n = s.size();
    367         c = vector<int>(s.begin(), s.end());
    368         int max_al = *max_element(c.begin(), c.end()) + 1;
    369         p.resize(n);
    370         for (int k = 1; k < n; k <<= 1) {
    371             for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1))
    372                 p[i] = make_pair(make_pair(c[i], c[j]), i);
    373             radix_sort(max_al);
    374             c[p[0].y] = 0;
    375             for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x);
    376             max_al = c[p.back().y] + 1;
    377         }
    378         lcp.resize(n);
    379         int l = 0;
    380         forn(i, n) {
    381             l = max(0, l - 1);
    382             if (c[i] == n - 1)
    383                 continue;
    384             while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l])
    385                 ++l;
    386             lcp[c[i]] = l;
    387         }
    388         pos.resize(n);
    389         forn(i, n)
    390             pos[i] = p[i].y;
    391         st = sparse_table(lcp);
    392     }
    393 };
    394 
    395 int main() {
    396     string s;
    397     int n;
    398     cin >> n;
    399     cin >> s;
    400     string t = s;
    401     reverse(t.begin(), t.end());
    402     auto sa = suffix_array(s + "#" + t + "$");
    403     vector<vector<int>> ev0(n), ev1(n);
    404     long long base = 0;
    405     vector<long long> dt(n + 2);
    406     vector<int> d1(n);
    407     forn(i, n){
    408         int len0 = sa.get_lcp(i, 2 * n - i + 1);
    409         base += len0;
    410         dt[i - len0] += 1;
    411         dt[i] -= 1;
    412         dt[i + 1] -= 1;
    413         dt[i + len0 + 1] += 1;
    414         if (i - len0 - 1 >= 0 && i + len0 < n){
    415             ev0[i - len0 - 1].push_back(i);
    416             ev0[i + len0].push_back(i);
    417         }
    418         int len1 = sa.get_lcp(i, 2 * n - i);
    419         d1[i] = len1;
    420         dt[i - len1 + 1] += 1;
    421         dt[i + 1] -= 2;
    422         dt[i + len1 + 1] += 1;
    423         base += len1;
    424         if (i - len1 >= 0 && i + len1 < n){
    425             ev1[i - len1].push_back(i);
    426             ev1[i + len1].push_back(i);
    427         }
    428     }
    429     vector<long long> dx(n + 1);
    430     long long curt = 0, val = 0;
    431     forn(i, n){
    432         curt += dt[i];
    433         val += curt;
    434         dx[i] = val;
    435     }
    436     long long ans = base;
    437     int pos = -1, nc = -1;
    438     bool gr = false;
    439     forn(i, n) forn(c, 26) if (c != s[i] - 'a'){
    440         long long cur = base;
    441         for (int j : ev0[i]){
    442             if (j <= i && c == s[2 * j - i - 1] - 'a')
    443                 cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2));
    444             else if (j > i && c == s[2 * j - i - 1] - 'a')
    445                 cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1));
    446         }
    447         for (int j : ev1[i]){
    448             if (c != s[2 * j - i] - 'a') continue;
    449             if (j < i)
    450                 cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1));
    451             else
    452                 cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1));
    453         }
    454         cur += d1[i];
    455         cur -= dx[i];
    456         bool upd = false;
    457         if (cur > ans){
    458             upd = true;
    459         }
    460         else if (cur == ans){
    461             if (c < s[i] - 'a'){
    462                 if (pos == -1 || gr)
    463                     upd = true;
    464             }
    465             else{
    466                 if (pos < i && gr)
    467                     upd = true;
    468             }
    469         }
    470         if (upd){
    471             ans = cur;
    472             pos = i;
    473             nc = c;
    474             gr = c > s[i] - 'a';
    475         }
    476     }
    477     cout << ans << endl;
    478     if (pos != -1) s[pos] = nc + 'a';
    479     cout << s << endl;
    480     return 0;
    481 }
    482 ```