codeforces-scrape

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

1620.md (10501B)


      1 Source: https://codeforces.com/blog/entry/98061
      2 
      3 [1620A - Equal or Not Equal](/contest/1620/problem/A "Educational Codeforces Round 119 (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     string s;
     23     cin >> s;
     24     cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n");
     25   }
     26 }
     27 ```
     28 
     29 [1620B - Triangles on a Rectangle](/contest/1620/problem/B "Educational Codeforces Round 119 (Rated for Div. 2)")
     30 
     31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution (awoo)**
     38 
     39 ```
     40 for _ in range(int(input())):
     41   w, h = map(int, input().split())
     42   ans = 0
     43   for i in range(4):
     44     a = [int(x) for x in input().split()][1:]
     45     ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w))
     46   print(ans)
     47 ```
     48 
     49 [1620C - BA-String](/contest/1620/problem/C "Educational Codeforces Round 119 (Rated for Div. 2)")
     50 
     51 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution (awoo)**
     58 
     59 ```
     60 for _ in range(int(input())):
     61   n, k, x = map(int, input().split())
     62   x -= 1
     63   s = input()[::-1]
     64   res = []
     65   i = 0
     66   while i < n:
     67     if s[i] == 'a':
     68       res.append(s[i])
     69     else:
     70       j = i
     71       while j + 1 < n and s[j + 1] == s[i]:
     72         j += 1
     73       cur = (j - i + 1) * k + 1
     74       res.append('b' * (x % cur))
     75       x //= cur
     76       i = j
     77     i += 1
     78   print(''.join(res[::-1]))
     79 ```
     80 
     81 [1620D - Exact Change](/contest/1620/problem/D "Educational Codeforces Round 119 (Rated for Div. 2)")
     82 
     83 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution (adedalic)**
     90 
     91 ```
     92 #include<bits/stdc++.h>
     93 
     94 using namespace std;
     95 
     96 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     97 #define sz(a) int((a).size())
     98 
     99 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    100   return out << "(" << p.x << ", " << p.y << ")";
    101 }
    102 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    103   fore(i, 0, sz(v)) {
    104     if(i) out << " ";
    105     out << v[i];
    106   }
    107   return out;
    108 }
    109 
    110 int n;
    111 vector<int> a;
    112 
    113 inline bool read() {
    114   if(!(cin >> n))
    115     return false;
    116   a.resize(n);
    117   fore (i, 0, n)
    118     cin >> a[i];
    119   return true;
    120 }
    121 
    122 bool p(int val, int c1, int c2, int c3) {
    123   fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) {
    124     if (cur1 + 2 * cur2 > val)
    125       continue;
    126     if ((val - cur1 - 2 * cur2) % 3 != 0)
    127       continue;
    128     if ((val - cur1 - 2 * cur2) / 3 <= c3)
    129       return true;
    130   }
    131   return false;
    132 }
    133 
    134 bool possible(int c1, int c2, int c3) {
    135   for (int v : a) {
    136     if (!p(v, c1, c2, c3))
    137       return false;
    138   }
    139   return true;
    140 }
    141 
    142 inline void solve() {
    143   int m = *max_element(a.begin(), a.end());
    144   int ans = int(1e9);
    145   
    146   const int MAG = 3;
    147   fore (c1, 0, MAG) fore (c2, 0, MAG) {
    148     int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3);
    149     assert(c1 + 2 * c2 + 3 * c3 >= m);
    150     
    151     if (possible(c1, c2, c3))
    152       ans = min(ans, c1 + c2 + c3);
    153   }
    154   cout << ans << endl;
    155 }
    156 
    157 int main() {
    158 #ifdef _DEBUG
    159   freopen("input.txt", "r", stdin);
    160 #endif
    161   int t; cin >> t;
    162   while(t--) {
    163     read();
    164     solve();
    165   }
    166   return 0;
    167 }
    168 ```
    169 
    170 [1620E - Replace the Numbers](/contest/1620/problem/E "Educational Codeforces Round 119 (Rated for Div. 2)")
    171 
    172 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution 1 (Neon)**
    179 
    180 ```
    181 #include <bits/stdc++.h>
    182 
    183 using namespace std;
    184 
    185 const int N = 500 * 1000 + 13;
    186 
    187 int main() {
    188   int q;
    189   scanf("%d", &q);
    190   vector<int> t(q), x(q), y(q);
    191   for (int i = 0; i < q; ++i) {
    192     scanf("%d%d", &t[i], &x[i]);
    193     if (t[i] == 2) scanf("%d", &y[i]);
    194   }
    195   vector<int> p(N);
    196   iota(p.begin(), p.end(), 0);
    197   vector<int> ans;
    198   for (int i = q - 1; i >= 0; --i) {
    199     if (t[i] == 1) {
    200       ans.push_back(p[x[i]]);
    201     } else {
    202       p[x[i]] = p[y[i]];
    203     }
    204   }
    205   reverse(ans.begin(), ans.end());
    206   for (int &x : ans) printf("%d ", x);
    207 }
    208 ```
    209 
    210 **Solution 2 (Neon)**
    211 
    212 ```
    213 #include <bits/stdc++.h>
    214 
    215 using namespace std;
    216 
    217 const int N = 500 * 1000 + 13;
    218 
    219 int n, q;
    220 vector<int> pos[N];
    221 
    222 int main() {
    223   scanf("%d", &q);
    224   while (q--) {
    225     int t, x, y;
    226     scanf("%d", &t);
    227     if (t == 1) {
    228       scanf("%d", &x);
    229       pos[x].push_back(n++);
    230     } else {
    231       scanf("%d%d", &x, &y);
    232       if (x != y) {
    233         if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]);
    234         for (int &i : pos[x]) pos[y].push_back(i);
    235         pos[x].clear();
    236       }
    237     }
    238   }
    239   vector<int> ans(n);
    240   for (int x = 0; x < N; ++x)
    241     for (int &i : pos[x]) 
    242       ans[i] = x;
    243   for (int &x : ans) printf("%d ", x);
    244 }
    245 ```
    246 
    247 [1620F - Bipartite Array](/contest/1620/problem/F "Educational Codeforces Round 119 (Rated for Div. 2)")
    248 
    249 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [Neon](/profile/Neon "Candidate Master Neon")
    250 
    251 **Tutorial**
    252 
    253 Tutorial is loading...
    254 
    255 **Solution 1 (Neon)**
    256 
    257 ```
    258 #include <bits/stdc++.h>
    259 
    260 using namespace std;
    261 
    262 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    263 
    264 const int INF = 1e9;
    265 const int N = 1000 * 1000 + 13;
    266 
    267 int n;
    268 int p[N], a[N];
    269 int dp[N][2][2];
    270 pair<int, int> pr[N][2][2];
    271 
    272 void solve() {
    273   scanf("%d", &n);
    274   forn(i, n) scanf("%d", &p[i]);
    275   forn(i, n) forn(pos, 2) forn(sg, 2)
    276     dp[i][pos][sg] = INF;
    277   dp[0][0][0] = dp[0][0][1] = -INF;
    278   
    279   forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {
    280     forn(nsg, 2) {
    281       int x = sg ? -p[i] : p[i];
    282       int y = dp[i][pos][sg];
    283       if (pos) swap(x, y);
    284       int z = nsg ? -p[i + 1] : p[i + 1];
    285       if (z > x) {
    286         if (dp[i + 1][0][nsg] > y) {
    287           dp[i + 1][0][nsg] = y;
    288           pr[i + 1][0][nsg] = make_pair(pos, sg);
    289         }
    290       } else if (z > y)  {
    291         if (dp[i + 1][1][nsg] > x) {
    292           dp[i + 1][1][nsg] = x;
    293           pr[i + 1][1][nsg] = make_pair(pos, sg);
    294         }
    295       }
    296     }
    297   }
    298   
    299   int pos = -1, sg = -1;
    300   forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF) 
    301     pos = j, sg = k;
    302   if (pos == -1) {
    303     puts("NO");
    304     return;
    305   }
    306   for (int i = n - 1; i >= 0; i--) {
    307     a[i] = sg ? -p[i] : p[i];
    308     tie(pos, sg) = pr[i][pos][sg];
    309   }
    310   
    311   puts("YES");
    312   forn(i, n) printf("%d ", a[i]);
    313   puts("");
    314 }
    315 
    316 int main() {
    317   int t;
    318   scanf("%d", &t);
    319   while (t--) solve();
    320 }
    321 ```
    322 
    323 **Solution 2 (Neon)**
    324 
    325 ```
    326 #include <bits/stdc++.h>
    327 
    328 using namespace std;
    329 
    330 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    331 
    332 const int INF = 1e9;
    333 const int N = 1000 * 1000 + 13;
    334 
    335 int n;
    336 int p[N], a[N];
    337 int dp[N][2], pr[N][2];
    338 
    339 void solve() {
    340   scanf("%d", &n);
    341   forn(i, n) scanf("%d", &p[i]);
    342   forn(i, n) forn(j, 2) dp[i][j] = INF;
    343   dp[0][0] = dp[0][1] = -INF;
    344   forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {
    345     int x = j ? -p[i] : p[i];
    346     int y = dp[i][j];
    347     if (x < y) swap(x, y);
    348     forn(nj, 2) {
    349       int z = nj ? -p[i + 1] : p[i + 1];
    350       if (z > x) {
    351         if (dp[i + 1][nj] > y) {
    352           dp[i + 1][nj] = y;
    353           pr[i + 1][nj] = j;
    354         }
    355       } else if (z > y)  {
    356         if (dp[i + 1][nj] > x) {
    357           dp[i + 1][nj] = x;
    358           pr[i + 1][nj] = j;
    359         }
    360       }
    361     }
    362   }
    363   int j = -1;
    364   forn(i, 2) if (dp[n - 1][i] != INF) j = i;
    365   if (j == -1) {
    366     puts("NO");
    367     return;
    368   }
    369   for (int i = n - 1; i >= 0; i--) {
    370     a[i] = j ? -p[i] : p[i];
    371     j = pr[i][j];
    372   }
    373   puts("YES");
    374   forn(i, n) printf("%d ", a[i]);
    375   puts("");
    376 }
    377 
    378 int main() {
    379   int t;
    380   scanf("%d", &t);
    381   while (t--) solve();
    382 }
    383 ```
    384 
    385 [1620G - Subsequences Galore](/contest/1620/problem/G "Educational Codeforces Round 119 (Rated for Div. 2)")
    386 
    387 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    388 
    389 **Tutorial**
    390 
    391 Tutorial is loading...
    392 
    393 **Solution (BledDest)**
    394 
    395 ```
    396 #include<bits/stdc++.h>
    397 
    398 using namespace std;
    399 
    400 const int N = 23;
    401 const int A = 26;
    402 const int S = 20043;
    403 int n;
    404 string inp[N];
    405 char buf[S];
    406 int cnt[N][A];
    407 const int MOD = 998244353;
    408 
    409 int add(int x, int y)
    410 {
    411     x += y;
    412     while(x >= MOD) x -= MOD;
    413     while(x < 0) x += MOD;
    414     return x;
    415 }
    416 
    417 int sub(int x, int y)
    418 {
    419     return add(x, -y);
    420 }
    421 
    422 int mul(int x, int y)
    423 {
    424     return (x * 1ll * y) % MOD;
    425 }
    426 
    427 void flip_all(vector<int>& a)
    428 {
    429     int msk = (1 << n) - 1;
    430     for(int i = 0; i < (1 << (n - 1)); i++)
    431         swap(a[i], a[i ^ msk]);
    432 }
    433 
    434 int val[S];
    435 int* where[S];
    436 int cur = 0;
    437 
    438 void change(int& x, int y)
    439 {
    440     where[cur] = &x;
    441     val[cur] = x;
    442     x = y;
    443     cur++;
    444 }
    445 
    446 void rollback()
    447 {
    448     --cur;
    449     (*where[cur]) = val[cur];
    450 }
    451 
    452 void zeta_transform(vector<int>& a)
    453 {
    454     for(int i = 0; i < n; i++)
    455     {
    456         for(int j = 0; j < (1 << n); j++)
    457             if((j & (1 << i)) == 0)
    458                 a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);
    459     }
    460 }                     
    461 
    462 void mobius_transform(vector<int>& a)
    463 {
    464     for(int i = n - 1; i >= 0; i--)
    465     {
    466         for(int j = (1 << n) - 1; j >= 0; j--)
    467             if((j & (1 << i)) != 0)
    468                 a[j] = sub(a[j], a[j ^ (1 << i)]);
    469     }
    470 }
    471 
    472 int cur_max[A];
    473 vector<int> mask_cnt;
    474 
    475 void rec(int depth, int mask)
    476 {
    477     if(depth == n)
    478     {
    479         mask_cnt[mask] = 1;
    480         for(int i = 0; i < A; i++)
    481             mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);
    482     }
    483     else
    484     {
    485         int state = cur;
    486         for(int i = 0; i < A; i++)
    487             change(cur_max[i], min(cur_max[i], cnt[depth][i]));
    488         rec(depth + 1, mask + (1 << depth));
    489         while(state != cur) rollback();
    490         rec(depth + 1, mask);
    491     }   
    492 }
    493 
    494 int main()
    495 {
    496     scanf("%d", &n);
    497     for(int i = 0; i < n; i++)
    498     {
    499         scanf("%s", buf);
    500         inp[i] = buf;
    501         for(auto x : inp[i])
    502             cnt[i][x - 'a']++;
    503     }
    504 
    505     for(int i = 0; i < A; i++)
    506         cur_max[i] = S;
    507     mask_cnt.resize(1 << n);
    508     rec(0, 0);
    509     flip_all(mask_cnt);
    510     mobius_transform(mask_cnt);
    511     flip_all(mask_cnt);
    512     int sum = 0;
    513     for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);
    514     zeta_transform(mask_cnt);
    515     vector<int> res(1 << n);
    516     for(int i = 0; i < (1 << n); i++)
    517         res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);
    518 
    519     long long ans = 0;
    520 
    521     for(int i = 0; i < (1 << n); i++)
    522     {
    523         int c = 0, s = 0;
    524         for(int j = 0; j < n; j++)
    525         {
    526             if(i & (1 << j))
    527             {
    528                 c++;
    529                 s += j + 1;
    530             }   
    531         }
    532         ans ^= res[i] * 1ll * c * 1ll * s;
    533     }
    534 
    535     //for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);
    536     printf("%lld\n", ans);
    537 }
    538 ```