codeforces-scrape

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

1948.md (6856B)


      1 Source: https://codeforces.com/blog/entry/127182
      2 
      3 [1948A - Special Characters](/contest/1948/problem/A "Educational Codeforces Round 163 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int n;
     23     cin >> n;
     24     if (n % 2 == 1) {
     25       cout << "NO" << '\n';
     26       continue;
     27     }
     28     cout << "YES" << '\n';
     29     for (int i = 0; i < n / 2; ++i)
     30       for (int j = 0; j < 2; ++j)
     31         cout << "AB"[i & 1];
     32     cout << '\n';
     33   }
     34 }
     35 ```
     36 
     37 [1948B - Array Fix](/contest/1948/problem/B "Educational Codeforces Round 163 (Rated for Div. 2)")
     38 
     39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (Neon)**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49  
     50 using namespace std;
     51 
     52 int main() {
     53   int t;
     54   cin >> t;
     55   while (t--) {
     56     int n;
     57     cin >> n;
     58     vector<int> a(n);
     59     for (auto& x : a) cin >> x;
     60     vector<int> b({a[n - 1]});
     61     for (int i = n - 2; i >= 0; --i) {
     62       if (a[i] > b.back()) {
     63         b.push_back(a[i] % 10);
     64         b.push_back(a[i] / 10);
     65       } else {
     66         b.push_back(a[i]);
     67       }
     68     }
     69     cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
     70   }
     71 }
     72 ```
     73 
     74 [1948C - Arrow Path](/contest/1948/problem/C "Educational Codeforces Round 163 (Rated for Div. 2)")
     75 
     76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (Neon)**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86  
     87 using namespace std;
     88 
     89 int main() {
     90   int t;
     91   cin >> t;
     92   while (t--) {
     93     int n;
     94     cin >> n;
     95     vector<char> ok1(n / 2), ok2(n / 2);
     96     for (int i = 0; i < 2; ++i) {
     97       string s;
     98       cin >> s;
     99       for (int j = 0; j < n; ++j) if ((i + j) & 1) {
    100         ok1[(i + j) / 2] |= (s[j] == '>');
    101         ok2[(j - i + 1) / 2] |= (s[j] == '>');
    102       }
    103     }
    104     bool ans = true;
    105     for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
    106     cout << (ans ? "YES" : "NO") << '\n';
    107   }
    108 }
    109 ```
    110 
    111 [1948D - Tandem Repeats?](/contest/1948/problem/D "Educational Codeforces Round 163 (Rated for Div. 2)")
    112 
    113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (awoo)**
    120 
    121 ```
    122 for _ in range(int(input())):
    123     s = input()
    124     n = len(s)
    125     ans = 0
    126     for d in range(1, n // 2 + 1):
    127         cnt = 0
    128         for i in range(n - d):
    129             cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
    130             if i - d >= 0:
    131                 cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
    132             if i - d >= -1 and cnt == d:
    133                 ans = 2 * d
    134     print(ans)
    135 ```
    136 
    137 [1948E - Clique Partition](/contest/1948/problem/E "Educational Codeforces Round 163 (Rated for Div. 2)")
    138 
    139 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution (BledDest)**
    146 
    147 ```
    148 #include<bits/stdc++.h>
    149  
    150 using namespace std;
    151  
    152 void solve()
    153 {
    154     int n, k;
    155     cin >> n >> k;
    156     vector<int> a(n), c(n);
    157     for(int i = 0; i < n; i++)
    158     {
    159         a[i] = i + 1;
    160         c[i] = i / k + 1;
    161     }
    162     int q = *max_element(c.begin(), c.end());
    163     for(int i = 1; i <= q; i++)
    164     {
    165         int l = find(c.begin(), c.end(), i) - c.begin();
    166         int r = c.rend() - find(c.rbegin(), c.rend(), i);
    167         int m = (l + r) / 2;
    168         reverse(a.begin() + l, a.begin() + m);
    169         reverse(a.begin() + m, a.begin() + r);
    170     }
    171     for(int i = 0; i < n; i++)
    172         cout << a[i] << " \n"[i == n - 1];
    173     cout << q << "\n";
    174     for(int i = 0; i < n; i++)
    175         cout << c[i] << " \n"[i == n - 1];
    176 }
    177  
    178 int main()
    179 {
    180     int t;
    181     cin >> t;
    182     for(int i = 0; i < t; i++)
    183         solve();
    184 }
    185 ```
    186 
    187 [1948F - Rare Coins](/contest/1948/problem/F "Educational Codeforces Round 163 (Rated for Div. 2)")
    188 
    189 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    190 
    191 **Tutorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution (Neon)**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199  
    200 using namespace std;
    201 
    202 const int MOD = 998244353;
    203 
    204 int add(int x, int y) {
    205   x += y;
    206   if (x >= MOD) x -= MOD;
    207   return x;
    208 }
    209 
    210 int mul(int x, int y) {
    211   return x * 1LL * y % MOD;
    212 }
    213 
    214 int binpow(int x, int y) {
    215   int z = 1;
    216   while (y) {
    217     if (y & 1) z = mul(z, x);
    218     x = mul(x, x);
    219     y >>= 1;
    220   }
    221   return z;
    222 }
    223 
    224 int main() {
    225   ios::sync_with_stdio(false); cin.tie(0);
    226   int n, q;
    227   cin >> n >> q;
    228   vector<int> a(n), b(n);
    229   for (auto& x : a) cin >> x;
    230   for (auto& x : b) cin >> x;
    231   vector<int> suma(n + 1), sumb(n + 1);
    232   for (int i = 0; i < n; ++i) {
    233     suma[i + 1] = suma[i] + a[i];
    234     sumb[i + 1] = sumb[i] + b[i];
    235   }
    236   int m = sumb[n];
    237   vector<int> f(m + 1), invf(m + 1);
    238   f[0] = 1;
    239   for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
    240   invf[m] = binpow(f[m], MOD - 2);
    241   for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
    242   vector<int> sumc(m + 2);
    243   for (int i = 0; i <= m; ++i)
    244     sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
    245   int pw2 = binpow(binpow(2, MOD - 2), m);
    246   while (q--) {
    247     int l, r;
    248     cin >> l >> r;
    249     --l;
    250     int k = 2 * (suma[r] - suma[l]) - suma[n];
    251     int cur = sumb[r] - sumb[l];
    252     int mx = max(0, min(k + cur, m + 1));
    253     int cnt = sumc[mx];
    254     cout << mul(cnt, pw2) << ' ';
    255   }
    256 }
    257 ```
    258 
    259 [1948G - MST with Matching](/contest/1948/problem/G "Educational Codeforces Round 163 (Rated for Div. 2)")
    260 
    261 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    262 
    263 **Tutorial**
    264 
    265 Tutorial is loading...
    266 
    267 **Solution (BledDest)**
    268 
    269 ```
    270 #include<bits/stdc++.h>
    271 
    272 using namespace std;
    273 
    274 int n, c;
    275 int g[21][21];
    276 
    277 const int INF = int(1e9);
    278 
    279 int primMST(int vertex_cover_mask)
    280 {
    281     vector<int> d(n, INF);
    282     vector<bool> used(n, false);
    283     d[0] = 0;
    284     int ans = 0;
    285     for(int i = 0; i < n; i++)
    286     {
    287         int idx = -1;
    288         for(int j = 0; j < n; j++)
    289         {
    290             if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
    291                 idx = j;
    292         }
    293         if(idx == -1) return INF;
    294         used[idx] = true;
    295         ans += d[idx];
    296         for(int k = 0; k < n; k++)
    297         {
    298             if(used[k]) 
    299                 continue;
    300             if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
    301                 continue;
    302             d[k] = min(d[k], g[idx][k]);
    303         }
    304     }
    305     return ans;
    306 }
    307 
    308 int main()
    309 {
    310     cin >> n >> c;
    311     for(int i = 0; i < n; i++)
    312     {
    313         for(int j = 0; j < n; j++)
    314         {
    315             cin >> g[i][j];
    316             if(g[i][j] == 0) g[i][j] = INF;
    317         }
    318     }
    319     int ans = INF;
    320     for(int mask = 0; mask < (1 << n); mask++)
    321     {
    322         int cur = primMST(mask);
    323         if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
    324     }
    325     cout << ans << endl;
    326 }
    327 ```