codeforces-scrape

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

2283.md (11648B)


      1 Source: https://codeforces.com/blog/entry/158495
      2 
      3 [2283A - Numbers on the Board](/contest/2283/problem/A "Educational Codeforces Round 196 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 t = int(input())
     13 for i in range(t):
     14     l, r = map(int, input().split())
     15     if r < 0 or l > 0:
     16         print(r - l)
     17     else:
     18         m = min(r, -l)
     19         print(max(0, r - l - 2 * m - 1))
     20 ```
     21 
     22 [2283B - Rhythmic String](/contest/2283/problem/B "Educational Codeforces Round 196 (Rated for Div. 2)")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution**
     29 
     30 ```
     31 #include<bits/stdc++.h>
     32 
     33 using namespace std;
     34 
     35 void solve()
     36 {
     37     int n;
     38     cin >> n;
     39     vector<int> a(n);
     40     for(int i = 0; i < n; i++)
     41         cin >> a[i];
     42     int ans = 1;
     43     for(int i = 0; i < n; i++)
     44     {
     45         int cur = 0;
     46         for(int j = 0; j < n; j++)
     47             if(a[j] % a[i] == 0)
     48                 cur++;
     49         ans = max(ans, cur);
     50     }
     51     cout << n - ans << endl;
     52 }
     53 
     54 int main()
     55 {
     56     ios_base::sync_with_stdio(0);
     57     cin.tie(0);
     58     int t;
     59     cin >> t;
     60     for(int i = 0; i < t; i++)
     61         solve();    
     62 }
     63 ```
     64 
     65 [2283C - Big XOR](/contest/2283/problem/C "Educational Codeforces Round 196 (Rated for Div. 2)")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution**
     72 
     73 ```
     74 #include<bits/stdc++.h>
     75 
     76 using namespace std;
     77 
     78 void solve()
     79 {
     80     int n;
     81     cin >> n;
     82     int k = 0;
     83     for(int i = 1; i <= n; i++) k |= i;
     84     int m = 0;
     85     vector<int> ans(n, 0);
     86     for(int i = 1; i <= n; i++) m ^= i;
     87     int d = 0;
     88     cout << k << endl;
     89     while((k >> d) & 1) d++;
     90     cout << d << endl;
     91     for(int i = d; i >= 1; i--)
     92         if(((m >> i) & 1) == 0)
     93         {
     94             int x = (1 << (i - 1));
     95             cout << x << endl;
     96             ans[x - 1] = 1;
     97             m ^= x;
     98             m ^= (x << 1);
     99         }
    100     for(int i = 0; i < n; i++)
    101         cout << ans[i] << " ";
    102     cout << endl;
    103 }
    104 
    105 int main()
    106 {
    107     ios_base::sync_with_stdio(0);
    108     cin.tie(0);
    109     int t;
    110     cin >> t;
    111     for(int i = 0; i < t; i++)
    112         solve();    
    113 }
    114 ```
    115 
    116 [2283D - Black, Gray and White](/contest/2283/problem/D "Educational Codeforces Round 196 (Rated for Div. 2)")
    117 
    118 **Tutorial**
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (awoo)**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126 
    127 using namespace std;
    128 
    129 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    130 
    131 int main() {
    132 #ifdef _DEBUG
    133     freopen("input.txt", "r", stdin);
    134 #endif
    135     cin.tie(0);
    136     ios::sync_with_stdio(false);
    137     
    138     int tc;
    139     cin >> tc;
    140     while (tc--){
    141         int n;
    142         cin >> n;
    143         vector<vector<int>> g(n);
    144         forn(i, n - 1){
    145             int v, u;
    146             cin >> v >> u;
    147             --v, --u;
    148             g[v].push_back(u);
    149             g[u].push_back(v);
    150         }
    151         if (n % 2 == 0){
    152             cout << n + 1 << '\n';
    153             continue;
    154         }
    155         int ans = n;
    156         for (int k : {n + 1, n + 2}){
    157             int u = k == n + 1 ? n / 2 : 0;
    158             vector<int> clr(n, -1);
    159             queue<int> q;
    160             clr[u] = 0;
    161             int c = 1;
    162             forn(i, n) if (clr[i] == -1){
    163                 q.push(i);
    164                 clr[i] = c;
    165                 while (!q.empty()){
    166                     int v = q.front();
    167                     q.pop();
    168                     for (int u : g[v]) if (clr[u] == -1){
    169                         clr[u] = c;
    170                         q.push(u);
    171                     }
    172                 }
    173                 ++c;
    174             }
    175             bool any = false;
    176             for (int i = 1; i <= n; ++i) if (k - i <= n && k - i != i)
    177                 any |= clr[i - 1] != clr[k - i - 1];
    178             if (any)
    179                 ans = k;
    180         }
    181         cout << ans << '\n';
    182     }
    183 }
    184 ```
    185 
    186 [2283E - Partition of a Binary String](/contest/2283/problem/E "Educational Codeforces Round 196 (Rated for Div. 2)")
    187 
    188 **Tutorial**
    189 
    190 Tutorial is loading...
    191 
    192 **Solution**
    193 
    194 ```
    195 #include<bits/stdc++.h>
    196 
    197 using namespace std;
    198 
    199 const int N = 5043;
    200 const int MOD = 998244353;
    201 int bell[N];
    202 int C[N][N];
    203 int dp[N];
    204 
    205 int add(int x, int y)
    206 {
    207     x += y;
    208     while(x >= MOD) x -= MOD;
    209     while(x < 0) x += MOD;
    210     return x;
    211 }
    212 
    213 int mul(int x, int y)
    214 {
    215     return (x * 1ll * y) % MOD;
    216 }
    217 
    218 void precalc()
    219 {
    220     for(int i = 0; i < N; i++)
    221     {
    222         C[i][0] = C[i][i] = 1;
    223         for(int j = 1; j < i; j++)
    224             C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    225     }
    226     bell[0] = 1;
    227     for(int i = 1; i < N; i++)
    228         for(int k = 0; k < i; k++)
    229             bell[i] = add(bell[i], mul(C[i - 1][k], bell[i - k - 1]));
    230     dp[0] = 1;
    231     for(int i = 1; i < N; i++)
    232     {
    233         if(i >= 2) dp[i] = add(dp[i], dp[i - 2]);
    234         if(i >= 3) dp[i] = add(dp[i], dp[i - 3]);
    235     }
    236 }
    237 
    238 void solve()
    239 {
    240     int n;
    241     cin >> n;
    242     string s;
    243     cin >> s;
    244     int zero = 0, one = 0, cur = 0;
    245     int ans = 1;
    246     int val = 0;
    247     for(int i = 0; i < n; i++)
    248     {
    249         bool neq_adj = false;
    250         if(i > 0 && s[i] != s[i - 1]) neq_adj = true;
    251         if(i + 1 < n && s[i] != s[i + 1]) neq_adj = true;
    252         if(i > 0 && s[i] == s[i - 1])
    253         {
    254             ans = mul(ans, dp[cur]);
    255             cur = 0;
    256         }
    257         if(neq_adj)
    258         {
    259             cur++;
    260             val += 2;
    261         }
    262         else
    263         {
    264             ans = mul(ans, dp[cur]);
    265             cur = 0;
    266             if(s[i] == '0') zero++;
    267             else one++;    
    268             val++;
    269         }
    270     }
    271     ans = mul(ans, dp[cur]);
    272     ans = mul(ans, bell[zero]);
    273     ans = mul(ans, bell[one]);
    274     cout << val << " " << ans << endl;
    275 }
    276 
    277 int main()
    278 {
    279     ios_base::sync_with_stdio(0);
    280     cin.tie(0);
    281     precalc();
    282     int t;
    283     cin >> t;
    284     for(int i = 0; i < t; i++)
    285         solve();    
    286 }
    287 ```
    288 
    289 [2283F - Minimize the Graph](/contest/2283/problem/F "Educational Codeforces Round 196 (Rated for Div. 2)")
    290 
    291 **Tutorial**
    292 
    293 Tutorial is loading...
    294 
    295 **Solution**
    296 
    297 ```
    298 #include<bits/stdc++.h>
    299 
    300 using namespace std;
    301 
    302 const int INF = int(1e9);
    303 
    304 struct FenwickSum
    305 {
    306     vector<int> f;
    307     int n;
    308 
    309     void add(int i, int x)
    310     {
    311         for(; i < n; i |= (i + 1))
    312             f[i] += x;
    313     }
    314 
    315     int get(int i)
    316     {
    317         int ans = 0;
    318         for(; i >= 0; i = (i & (i + 1)) - 1)
    319             ans += f[i];
    320         return ans;    
    321     }
    322 
    323     int get(int l, int r)
    324     {
    325         return get(r) - get(l - 1);
    326     }
    327 
    328     FenwickSum(int n = 0) : n(n)
    329     {
    330         f.resize(n);
    331     }
    332 };
    333 
    334 struct event
    335 {
    336     int moment;
    337     int type;
    338     int idx;
    339     event(int moment = 0, int type = 0, int idx = 0) : moment(moment), type(type), idx(idx) {};
    340 };
    341 
    342 bool operator<(const event& a, const event& b)
    343 {
    344     if(a.moment != b.moment) return a.moment < b.moment;
    345     if(a.type != b.type) return a.type < b.type;
    346     return a.idx < b.idx;
    347 }
    348 
    349 void solve()
    350 {
    351     int n;
    352     cin >> n;
    353     vector<int> l(n), r(n);
    354     for(int i = 1; i < n; i++)
    355     {
    356         cin >> l[i] >> r[i];     
    357         l[i]--;
    358     }
    359 
    360     vector<int> h(n, INF);
    361     set<int> s;
    362     for(int i = 0; i < n; i++) s.insert(i);
    363     for(int i = 1; i < n; i++)              
    364     {
    365         int lf = l[i];
    366         int rg = r[i];
    367         while(true)
    368         {
    369             auto it = s.lower_bound(lf);
    370             if(it == s.end() || *it >= rg) break;
    371             h[*it] = i;
    372             s.erase(it);
    373         }
    374     }
    375 
    376     vector<event> events;
    377     for(int i = 0; i < n; i++)
    378         events.push_back(event(h[i], 0, i));
    379     for(int i = 1; i < n; i++)
    380         events.push_back(event(r[i] - 1, 1, i));
    381 
    382     long long ans = 0;
    383 
    384     FenwickSum f(n + 1);
    385     for(int i = 0; i < n; i++)
    386         f.add(i, 1);
    387 
    388     sort(events.begin(), events.end());
    389     for(auto e : events)
    390         if(e.type == 0)
    391             f.add(e.idx, -1);
    392         else
    393         {
    394             int lf = l[e.idx];
    395             int rg = r[e.idx];
    396             ans += f.get(lf, rg - 1);
    397         }
    398 
    399     cout << ans << endl;
    400 }
    401 
    402 int main()
    403 {
    404     ios_base::sync_with_stdio(0);
    405     cin.tie(0);
    406     int t;
    407     cin >> t;
    408     for(int i = 0; i < t; i++)
    409         solve();    
    410 }
    411 ```
    412 
    413 [2283G - Order Statistics on the Graph](/contest/2283/problem/G "Educational Codeforces Round 196 (Rated for Div. 2)")
    414 
    415 **Tutorial**
    416 
    417 Tutorial is loading...
    418 
    419 **Solution**
    420 
    421 ```
    422 #include<bits/stdc++.h>
    423 
    424 using namespace std;
    425 
    426 const int N = 20;
    427 const int V = 1 << N;
    428 const int Q = int(1e5);
    429 
    430 int adj_mask[N];
    431 int idx[N];
    432 int nxt[V];
    433 vector<int> gt[V];
    434 vector<pair<long long, int>> que[N];
    435 int ans[N * Q];
    436 bool used[V];
    437 int cycle_pos[V];
    438 vector<int> cycle;
    439 vector<int> dfs_stack;
    440 
    441 vector<int> get_unique(const vector<int>& a)
    442 {
    443     vector<int> b = a;
    444     sort(b.begin(), b.end());
    445     b.erase(unique(b.begin(), b.end()), b.end());
    446     return b;
    447 } 
    448 
    449 vector<int> get_masks(const vector<int>& a)
    450 {
    451     int n = a.size();
    452     auto b = get_unique(a);
    453     int m = b.size();
    454     vector<int> masks(m - 1);
    455     for(int i = 0; i < m - 1; i++)
    456     {
    457         int mask = 0;
    458         for(int j = 0; j < n; j++)
    459             if(a[j] > b[i])
    460                 mask |= (1 << j);
    461         masks[i] = mask;
    462     }
    463     return masks;
    464 }
    465 
    466 vector<int> restore(const vector<int>& a, const vector<int>& masks)
    467 {
    468     int n = a.size();
    469     auto b = get_unique(a);
    470     int m = b.size();
    471     vector<int> ans(n, b[0]);
    472     for(int i = 0; i < m - 1; i++)
    473         for(int j = 0; j < n; j++)
    474             if((masks[i] >> j) & 1)
    475                 ans[j] = b[i + 1];
    476     return ans;
    477 }
    478 
    479 void dfs(int x)
    480 {
    481     used[x] = true;
    482     int depth = dfs_stack.size();
    483     dfs_stack.push_back(x);
    484     for(auto y : gt[x])
    485         if(!used[y])
    486             dfs(y);
    487     for(auto [t, i] : que[x])
    488     {
    489         if(t <= depth)
    490             ans[i] = dfs_stack[depth - t];
    491         else
    492         {
    493             long long add = t - depth;
    494             int pos = (cycle_pos[dfs_stack[0]] + add) % cycle.size();
    495             ans[i] = cycle[pos];
    496         }
    497     }
    498     dfs_stack.pop_back();
    499 }
    500 
    501 void solve()
    502 {
    503     int n, m, q;
    504     cin >> n >> m >> q;
    505     for(int i = 0; i < n; i++)
    506         cin >> idx[i];
    507     for(int i = 0; i < m; i++)
    508     {
    509         int x, y;
    510         cin >> x >> y;
    511         --x;
    512         --y;
    513         adj_mask[y] |= (1 << x);
    514     }
    515     
    516     vector<long long> t(q);
    517     vector<vector<int>> a(q, vector<int>(n));
    518     for(int i = 0; i < q; i++)
    519     {
    520         cin >> t[i];
    521         for(int j = 0; j < n; j++)
    522             cin >> a[i][j];
    523     }
    524 
    525     int qid = 0;
    526     for(int i = 0; i < q; i++)
    527     {
    528         auto masks = get_masks(a[i]);
    529         for(auto mask : masks)
    530         {
    531             que[mask].push_back(make_pair(t[i], qid));
    532             qid++;
    533         }
    534     }
    535 
    536     for(int i = 0; i < (1 << n); i++)
    537     {
    538         int ni = 0;
    539         for(int j = 0; j < n; j++)
    540         {
    541             int cur_mask = adj_mask[j] & i;
    542             if(__builtin_popcount(cur_mask) >= idx[j])
    543                 ni |= (1 << j); 
    544         }
    545         nxt[i] = ni;
    546         gt[ni].push_back(i);
    547     }
    548 
    549     for(int i = 0; i < (1 << n); i++)
    550     {
    551         if(used[i]) continue;
    552         int j = i;
    553         while(!used[j])
    554         {
    555             used[j] = true;
    556             j = nxt[j];
    557         }
    558         int k = j;
    559         cycle = {};
    560         do
    561         {
    562             cycle_pos[k] = cycle.size();
    563             cycle.push_back(k);
    564             k = nxt[k];
    565         }
    566         while(k != j);
    567         for(auto c : cycle) dfs(c);
    568     }
    569 
    570     qid = 0;
    571     for(int i = 0; i < q; i++)
    572     {
    573         auto masks = get_masks(a[i]);
    574         vector<int> res;
    575         for(int i = 0; i < masks.size(); i++)
    576         {
    577             res.push_back(ans[qid]);
    578             qid++;
    579         }
    580         vector<int> res2 = restore(a[i], res);
    581         for(auto x : res2) cout << x << " ";
    582         cout << "\n";
    583     }
    584 }
    585 
    586 int main()
    587 {
    588     ios_base::sync_with_stdio(0);
    589     cin.tie(0);
    590     int t = 1;
    591     // cin >> t;
    592     for(int i = 0; i < t; i++)
    593         solve();
    594 }
    595 ```