codeforces-scrape

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

1303.md (11492B)


      1 Source: https://codeforces.com/blog/entry/73872
      2 
      3 [1303A - Erasing Zeroes](/contest/1303/problem/A "Educational Codeforces Round 82 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 for t in range(int(input())):
     15     print(input().strip('0').count('0'))
     16 ```
     17 
     18 [1303B - National Project](/contest/1303/problem/B "Educational Codeforces Round 82 (Rated for Div. 2)")
     19 
     20 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution (adedalic)**
     27 
     28 ```
     29 fun main() {
     30     val t = readLine()!!.toInt()
     31     for (tc in 1..t) {
     32         val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
     33         
     34         val needG = (n + 1) / 2
     35         var totalG = needG / g * (b + g)
     36         totalG += if (needG % g == 0L) -b else needG % g
     37         println(maxOf(n, totalG))
     38     }
     39 }
     40 ```
     41 
     42 [1303C - Perfect Keyboard](/contest/1303/problem/C "Educational Codeforces Round 82 (Rated for Div. 2)")
     43 
     44 Idea: [Roms](/profile/Roms "Master Roms")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution (Ne0n25)**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54 
     55 using namespace std;
     56 
     57 #define sz(a) int((a).size())
     58 #define all(a) (a).begin(), (a).end()
     59 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     60 
     61 void solve() {
     62     string s;
     63     cin >> s;
     64 
     65     vector<bool> used(26);
     66     used[s[0] - 'a'] = true;
     67     string t(1, s[0]);
     68         
     69     int pos = 0;
     70     for (int i = 1; i < sz(s); i++) {
     71         if (used[s[i] - 'a']) {
     72             if (pos > 0 && t[pos - 1] == s[i]) {
     73                 pos--;
     74             } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
     75                 pos++;
     76             } else {
     77                 cout << "NO" << endl;
     78                 return;
     79             }
     80         } else {
     81             if (pos == 0) {
     82                 t = s[i] + t;
     83             } else if (pos == sz(t) - 1) {
     84                 t += s[i];
     85                 pos++;
     86             } else {
     87                 cout << "NO" << endl;
     88                 return;
     89             }
     90         }
     91         used[s[i] - 'a'] = true;
     92     }
     93         
     94     forn(i, 26) if (!used[i])
     95         t += char(i + 'a');
     96     cout << "YES" << endl << t << endl;
     97 }
     98 
     99 int main() {
    100     int tc;
    101     cin >> tc;
    102     
    103     forn(i, tc) solve();
    104 }
    105 ```
    106 
    107 [1303D - Fill The Bag](/contest/1303/problem/D "Educational Codeforces Round 82 (Rated for Div. 2)")
    108 
    109 Idea: [Roms](/profile/Roms "Master Roms")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution (Roms)**
    116 
    117 ```
    118 from math import log2
    119 
    120 for t in range(int(input())):
    121     n, m = map(int, input().split())
    122     c = [0] * 61
    123     s = 0
    124     for x in map(int, input().split()):
    125         c[int(log2(x))] += 1
    126         s += x
    127 
    128     if s < n:
    129         print(-1)
    130         continue
    131 
    132     i, res = 0, 0
    133     while i < 60:
    134         if (1<<i)&n != 0:
    135             if c[i] > 0:
    136                 c[i] -= 1
    137             else:
    138                 while i < 60 and c[i] == 0:
    139                     i += 1
    140                     res += 1
    141                 c[i] -= 1
    142                 continue
    143         c[i + 1] += c[i] // 2
    144         i += 1
    145 
    146     print(res)
    147 ```
    148 
    149 [1303E - Erase Subsequences](/contest/1303/problem/E "Educational Codeforces Round 82 (Rated for Div. 2)")
    150 
    151 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution (adedalic)**
    158 
    159 ```
    160 #include<bits/stdc++.h>
    161 
    162 using namespace std;
    163 
    164 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    165 #define sz(a) int((a).size())
    166 
    167 #define x first
    168 #define y second
    169 
    170 typedef long long li;
    171 typedef pair<int, int> pt;
    172 
    173 const int INF = int(1e9);
    174 const li INF64 = li(1e18);
    175 
    176 string s, t;
    177 
    178 inline bool read() {
    179     if(!(cin >> s >> t))
    180         return false;
    181     for(auto &c : s)
    182         c -= 'a';
    183     for(auto &c : t)
    184         c -= 'a';
    185     return true;
    186 }
    187 
    188 vector< vector<int> > nxt;
    189 
    190 bool calc(const string &a, const string &b) {
    191     vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
    192     dp[0][0] = 0;
    193     fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
    194         if(dp[i][j] > sz(s))
    195             continue;
    196         
    197         int len = dp[i][j];
    198         if(i < sz(a) && nxt[len][a[i]] < INF) {
    199             dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
    200         }
    201         if(j < sz(b) && nxt[len][b[j]] < INF) {
    202             dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
    203         }
    204     }
    205     return dp[sz(a)][sz(b)] < INF;
    206 }
    207 
    208 inline void solve() {
    209     nxt.assign(sz(s) + 1, vector<int>(26, INF));
    210     for(int i = sz(s) - 1; i >= 0; i--) {
    211         nxt[i] = nxt[i + 1];
    212         nxt[i][s[i]] = i;
    213     }
    214     
    215     for(int i = 0; i < sz(t); i++) {
    216         if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
    217             cout << "YES" << endl;
    218             return;
    219         }
    220     }
    221     cout << "NO" << endl;
    222 }
    223 
    224 int main() {
    225 #ifdef _DEBUG
    226     freopen("input.txt", "r", stdin);
    227     int tt = clock();
    228 #endif
    229     ios_base::sync_with_stdio(false);
    230     cin.tie(0), cout.tie(0);
    231     cout << fixed << setprecision(15);
    232     
    233     int tc; cin >> tc;
    234     
    235     while(tc--) {
    236         read();
    237         solve();
    238         
    239 #ifdef _DEBUG
    240         cerr << "TIME = " << clock() - tt << endl;
    241         tt = clock();
    242 #endif
    243     }
    244     return 0;
    245 }
    246 ```
    247 
    248 [1303F - Number of Components](/contest/1303/problem/F "Educational Codeforces Round 82 (Rated for Div. 2)")
    249 
    250 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    251 
    252 **Tutorial**
    253 
    254 Tutorial is loading...
    255 
    256 **Solution (Ne0n25)**
    257 
    258 ```
    259 #include <bits/stdc++.h>
    260 
    261 using namespace std;
    262 
    263 #define x first
    264 #define y second
    265 #define pb push_back
    266 #define mp make_pair
    267 #define sqr(a) ((a) * (a))
    268 #define sz(a) int((a).size())
    269 #define all(a) (a).begin(), (a).end()
    270 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    271 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
    272 #define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)
    273 
    274 typedef pair<int, int> pt;
    275 
    276 const int M = 310;
    277 const int N = 2000 * 1000 + 13;
    278 
    279 int n, m, q;
    280 int a[M][M];
    281 
    282 int dx[] = {-1, 0, 1, 0};
    283 int dy[] = {0, -1, 0, 1};
    284 
    285 bool in(int x, int y) {
    286     return 0 <= x && x < n && 0 <= y && y < m;
    287 }
    288 
    289 int p[M * M], rk[M * M];
    290 
    291 int getp(int v) {
    292     return p[v] == v ? v : p[v] = getp(p[v]);
    293 }
    294 
    295 bool unite(int a, int b) {
    296     a = getp(a); b = getp(b);
    297     if (a == b) return false;
    298     if (rk[a] < rk[b]) swap(a, b);
    299     p[b] = a;
    300     rk[a] += rk[b];
    301     return true;
    302 }
    303 
    304 int dif[N];
    305 vector<pt> add[N], del[N];
    306 
    307 void recalc(const vector<pt>& ev, int coeff)  {
    308     forn(i, n) forn(j, m) a[i][j] = 0;
    309     forn(i, n * m) p[i] = i, rk[i] = 1;
    310         
    311     for (auto it : ev) {
    312         int cur = 1;
    313         int x = it.x / m, y = it.x % m;
    314         a[x][y] = 1;
    315         
    316         forn(k, 4) {
    317             int nx = x + dx[k];
    318             int ny = y + dy[k];
    319             if (in(nx, ny) && a[nx][ny] == 1)
    320                 cur -= unite(nx * m + ny, x * m + y);
    321         }
    322         
    323         dif[it.y] += cur * coeff;
    324     }
    325 }
    326 
    327 int main() {
    328     scanf("%d%d%d", &n, &m, &q);
    329     int clrs = 1;
    330     forn(i, q) {
    331         int x, y, c;
    332         scanf("%d%d%d", &x, &y, &c);
    333         --x; --y;
    334         if (a[x][y] == c) continue;
    335         clrs = c + 1;
    336         add[c].pb(mp(x * m + y, i));
    337         del[a[x][y]].pb(mp(x * m + y, i));
    338         a[x][y] = c;
    339     }
    340     
    341     forn(x, n) forn(y, m)
    342         del[a[x][y]].pb(mp(x * m + y, q));
    343     
    344     forn(i, clrs) reverse(all(del[i]));
    345     
    346     forn(i, clrs) recalc(add[i], +1);
    347     forn(i, clrs) recalc(del[i], -1);
    348     
    349     int cur = 1;
    350     forn(i, q) {
    351         cur += dif[i];
    352         printf("%d\n", cur);
    353     }
    354 }
    355 ```
    356 
    357 [1303G - Sum of Prefix Sums](/contest/1303/problem/G "Educational Codeforces Round 82 (Rated for Div. 2)")
    358 
    359 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    360 
    361 **Tutorial**
    362 
    363 Tutorial is loading...
    364 
    365 **Solution (BledDest)**
    366 
    367 ```
    368 #include<bits/stdc++.h>
    369 
    370 using namespace std;
    371 
    372 const int N = 150043;
    373 
    374 typedef pair<long long, long long> func;
    375 
    376 func T[4 * N];
    377 bool usedT[4 * N];
    378 
    379 void clear(int v, int l, int r)
    380 {
    381     if(!usedT[v]) return;
    382     usedT[v] = false;
    383     T[v] = make_pair(0ll, 0ll);
    384     if(l < r - 1)
    385     {
    386         int m = (l + r) / 2;
    387         clear(v * 2 + 1, l, m);
    388         clear(v * 2 + 2, m, r);
    389     }
    390 }
    391 
    392 long long eval(func f, int x)
    393 {
    394     return f.first * x + f.second;
    395 }
    396 
    397 long long get(int v, int l, int r, int x)
    398 {
    399     long long ans = eval(T[v], x);
    400     if(l < r - 1)
    401     {
    402         int m = (l + r) / 2;
    403         if(m > x)
    404             ans = max(ans, get(v * 2 + 1, l, m, x));
    405         else
    406             ans = max(ans, get(v * 2 + 2, m, r, x));
    407     }
    408     return ans;
    409 }
    410 
    411 void upd(int v, int l, int r, func f)
    412 {
    413     usedT[v] = true;
    414     int m = (l + r) / 2;
    415     bool need_swap = eval(f, m) > eval(T[v], m);
    416     if(need_swap)
    417         swap(T[v], f);
    418     if(l == r - 1)
    419         return;
    420     if(eval(f, l) > eval(T[v], l))
    421         upd(v * 2 + 1, l, m, f);
    422     else
    423         upd(v * 2 + 2, m, r, f);
    424 }
    425 
    426 long long ans = 0;
    427 
    428 void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
    429 {
    430     int n = heads.size();
    431     for(int i = 0; i < n; i++)
    432     {
    433         for(auto x : heads[i])
    434             ans = max(ans, get(0, 0, N, x.first) + x.second);
    435         for(auto x : tails[i])
    436             upd(0, 0, N, x);
    437     }
    438     clear(0, 0, N);
    439 }
    440 
    441 int a[N];
    442 vector<int> g[N];
    443 int n;
    444 bool used[N];
    445 int siz[N];
    446 
    447 void dfs1(int x, int p = -1)
    448 {
    449     if(used[x]) return;
    450     siz[x] = 1;
    451     for(auto to : g[x])
    452     {                    
    453         if(!used[to] && to != p)
    454         {
    455             dfs1(to, x);
    456             siz[x] += siz[to];
    457         }
    458     }
    459 }
    460 
    461 pair<int, int> c;
    462 int S = 0;
    463 
    464 void find_centroid(int x, int p = -1)
    465 {
    466     if(used[x]) return;
    467     int mx = 0;
    468     for(auto to : g[x])
    469     {
    470         if(!used[to] && to != p)
    471         {
    472             find_centroid(to, x);
    473             mx = max(mx, siz[to]);
    474         }
    475     }
    476     if(p != -1)
    477         mx = max(mx, S - siz[x]);
    478     c = min(c, make_pair(mx, x));
    479 }
    480 
    481 void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
    482 {
    483     if(used[v])
    484         return;
    485     cnt++;
    486     curadd += a[v];
    487     cursum += curadd;
    488     sink.push_back(make_pair(cnt, cursum));
    489     for(auto to : g[v])
    490         if(to != p)
    491             dfs_heads(to, v, cnt, cursum, curadd, sink);
    492 }
    493 
    494 void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
    495 {
    496     if(used[v])
    497         return;
    498     cnt++;
    499     curadd += a[v];
    500     cursum += a[v] * 1ll * cnt;
    501     sink.push_back(make_pair(curadd, cursum));
    502     for(auto to : g[v])
    503         if(to != p)
    504             dfs_tails(to, v, cnt, cursum, curadd, sink);
    505 }
    506 
    507 void centroid(int v)
    508 {
    509     if(used[v]) return;
    510     dfs1(v);
    511     S = siz[v];
    512     c = make_pair(int(1e9), -1);
    513     find_centroid(v);
    514     int C = c.second;
    515     used[C] = 1;
    516     vector<vector<func> > heads, tails;
    517     for(auto to : g[C])
    518         if(!used[to])
    519         {
    520             heads.push_back(vector<func>());
    521             dfs_heads(to, C, 1, a[C], a[C], heads.back());
    522             tails.push_back(vector<func>());
    523             dfs_tails(to, C, 0, 0, 0, tails.back());
    524         }
    525     heads.push_back(vector<func>({{1, a[C]}}));
    526     tails.push_back(vector<func>({{0, 0}}));
    527     update_ans(heads, tails);
    528     reverse(heads.begin(), heads.end());
    529     reverse(tails.begin(), tails.end());
    530     update_ans(heads, tails);
    531     for(auto to : g[C])
    532         centroid(to);
    533 }
    534 
    535 int main()
    536 {
    537     scanf("%d", &n);
    538     for(int i = 0; i < n - 1; i++)
    539     {
    540         int x, y;
    541         scanf("%d %d", &x, &y);
    542         --x;
    543         --y;
    544         g[x].push_back(y);
    545         g[y].push_back(x);    
    546     }
    547     for(int i = 0; i < n; i++)
    548         scanf("%d", &a[i]);
    549     centroid(0);
    550     printf("%lld\n", ans);
    551 }
    552 ```