codeforces-scrape

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

1800.md (9679B)


      1 Source: https://codeforces.com/blog/entry/113477
      2 
      3 [1800A - Is It a Cat?](/contest/1800/problem/A "Codeforces Round 855 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 
     17 void solve(){
     18     int n;
     19     cin >> n;
     20     string s;
     21     cin >> s;
     22     transform(s.begin(), s.end(), s.begin(), [] (char c) {
     23         return tolower(c);
     24     });
     25     s.erase(unique(s.begin(), s.end()), s.end());
     26     cout << (s == "meow" ? "YES" : "NO") << "\n";
     27 }
     28 
     29 int main(){
     30     int t;
     31     cin >> t;
     32     while(t--) solve();
     33 }
     34 ```
     35 
     36 [1800B - Count the Number of Pairs](/contest/1800/problem/B "Codeforces Round 855 (Div. 3)")
     37 
     38 Idea: [myav](/profile/myav "Pupil myav")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 using namespace std;
     49 const int N = 26;
     50 
     51 void solve(){
     52     int n, k;
     53     cin >> n >> k;
     54     string s;
     55     cin >> s;
     56     vector<int>big(N, 0), small(N, 0);
     57     for(auto &i : s){
     58         if('A' <= i && 'Z' >= i) big[i - 'A']++;
     59         else small[i - 'a']++;
     60     }
     61     int answer = 0;
     62     for(int i = 0; i < N; i++){
     63         int pairs = min(small[i], big[i]);
     64         answer += pairs;
     65         small[i] -=pairs; big[i] -= pairs;
     66         int add = min(k, max(small[i], big[i]) / 2);
     67         k -= add; answer += add;
     68     }
     69     cout << answer << endl;
     70 }
     71 int main(){
     72     int t;
     73     cin >> t;
     74     while(t--) solve();
     75     return 0;
     76 }
     77 ```
     78 
     79 [1800C1 - Powering the Hero (easy version)](/contest/1800/problem/C1 "Codeforces Round 855 (Div. 3)")
     80 
     81 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 def solve():
     91     n = int(input())
     92     s = [int(x) for x in input().split()]
     93     ans = 0
     94     buffs = [0] * n
     95     for e in s:
     96         if e > 0:
     97             buffs += [e]
     98             j = len(buffs) - 1
     99             while buffs[j] < buffs[j - 1]:
    100                 buffs[j], buffs[j - 1] = buffs[j - 1], buffs[j]
    101                 j -= 1
    102         else:
    103             ans += buffs.pop()
    104     print(ans)
    105 
    106 t = int(input())
    107 for _ in range(t):
    108     solve()
    109 ```
    110 
    111 [1800C2 - Powering the Hero (hard version)](/contest/1800/problem/C2 "Codeforces Round 855 (Div. 3)")
    112 
    113 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution**
    120 
    121 ```
    122 from queue import PriorityQueue
    123 
    124 def solve():
    125     n = int(input())
    126     s = [int(x) for x in input().split()]
    127     ans = 0
    128     buffs = PriorityQueue()
    129     for e in s:
    130         if e > 0:
    131             buffs.put(-e)
    132         elif not buffs.empty():
    133             ans -= buffs.get()
    134     print(ans)
    135 
    136 t = int(input())
    137 for _ in range(t):
    138     solve()
    139 ```
    140 
    141 [1800D - Remove Two Letters](/contest/1800/problem/D "Codeforces Round 855 (Div. 3)")
    142 
    143 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 ```
    152 #include <iostream>
    153 #include <vector>
    154 #include <queue>
    155 #include <map>
    156 #include <set>
    157 
    158 using namespace std;
    159 
    160 void solve() {
    161     int n;
    162     cin >> n;
    163     string s;
    164     cin >> s;
    165     int res = n - 1;
    166     for (int i = 1; i + 1 < n; ++i) {
    167         if (s[i - 1] == s[i + 1]) {
    168             res--;
    169         }
    170     }
    171     cout << res << '\n';
    172 }
    173 
    174 int main(int argc, char* argv[]) {
    175     int t;
    176     cin >> t;
    177     for (int i = 0; i < t; ++i) {
    178         solve();
    179     }
    180 }
    181 ```
    182 
    183 [1800E1 - Unforgivable Curse (easy version)](/contest/1800/problem/E1 "Codeforces Round 855 (Div. 3)")
    184 
    185 Idea: [Aris](/profile/Aris "Candidate Master Aris"), [mutant](/profile/mutant "International Master mutant")
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Solution**
    192 
    193 ```
    194 #include <bits/stdc++.h>
    195 
    196 using namespace std;
    197 
    198 #define sz(v) (int)v.size()
    199 #define all(v) v.begin(),v.end()
    200 #define eb emplace_back
    201 
    202 void slow_solve(int n, int k, string s, string t) {
    203     set<string> was;
    204 
    205     queue<string> q;
    206     q.push(s);
    207     was.insert(s);
    208 
    209     auto add = [&](string& s, int i, int j) {
    210         if (i >= 0 && i < j && j < n) {
    211             swap(s[i], s[j]);
    212             if (!was.count(s)) {
    213                 was.insert(s);
    214                 q.push(s);
    215             }
    216             swap(s[i], s[j]);
    217         }
    218 
    219     };
    220 
    221     while (!q.empty()) {
    222         s = q.front(); q.pop();
    223         for (int i = 0; i < n; ++i) {
    224             add(s, i, i+k);
    225             add(s, i, i+k+1);
    226             add(s, i-k, i);
    227             add(s, i-k-1, i);
    228         }
    229     }
    230     cout << (was.count(t) ? "Yes" : "No") << '\n';
    231 }
    232 
    233 void solve() {
    234     int n,k; cin >> n >> k;
    235     string s; cin >> s;
    236     string t; cin >> t;
    237 
    238     if (n <= 5) {
    239         slow_solve(n, k, s, t);
    240         return;
    241     }
    242     map<char, int> cnt;
    243     for (char c : s) {
    244         cnt[c]++;
    245     }
    246 
    247     for (char c : t) {
    248         cnt[c]--;
    249     }
    250 
    251     bool ok = true;
    252     for (auto [c, x] : cnt) {
    253         ok &= x == 0;
    254     }
    255     cout << (ok ? "Yes" : "No") << '\n';
    256 }
    257 
    258 int main() {
    259     int t;
    260     cin >> t;
    261 
    262     while (t--) {
    263         solve();
    264     }
    265 }
    266 ```
    267 
    268 [1800E2 - Unforgivable Curse (hard version)](/contest/1800/problem/E2 "Codeforces Round 855 (Div. 3)")
    269 
    270 Idea: [Aris](/profile/Aris "Candidate Master Aris"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    271 
    272 **Tutorial**
    273 
    274 Tutorial is loading...
    275 
    276 **Solution**
    277 
    278 ```
    279 #include <bits/stdc++.h>
    280 
    281 using namespace std;
    282 
    283 #define sz(v) (int)v.size()
    284 #define all(v) v.begin(),v.end()
    285 #define eb emplace_back
    286 
    287 void solve() {
    288     int n, k; cin >> n >> k;
    289     string s; cin >> s;
    290     string t; cin >> t;
    291     vector<int> cnt(26, 0);
    292 
    293     bool ok = true;
    294     for (int i = 0; i < n; ++i) {
    295         if (i >= k || i+k < n){
    296             cnt[s[i] - 'a']++;
    297             cnt[t[i] - 'a']--;
    298         } else {
    299             ok &= s[i] == t[i];
    300         }
    301     }
    302 
    303     cout << (ok && count(all(cnt), 0) == 26 ? "YES" : "NO") << '\n';
    304 }
    305 
    306 int main() {
    307     int t;
    308     cin >> t;
    309 
    310     while (t--) {
    311         solve();
    312     }
    313 }
    314 ```
    315 
    316 [1800F - Dasha and Nightmares](/contest/1800/problem/F "Codeforces Round 855 (Div. 3)")
    317 
    318 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution**
    325 
    326 ```
    327 #pragma GCC optimize("O3")
    328 #pragma GCC optimize("unroll-loops")
    329 #pragma GCC target("avx2,avx,fma,bmi2")
    330 
    331 #include <bits/stdc++.h>
    332 #include <immintrin.h>
    333 #include <ext/pb_ds/assoc_container.hpp>
    334 using namespace std;
    335 using namespace __gnu_pbds;
    336 
    337 #define endl '\n'
    338 //#define int long long
    339 #define all(arr) arr.begin(), arr.end()
    340 #define multitest() int _gorilla_silverback; cin >> _gorilla_silverback; while (_gorilla_silverback --> 0)
    341 #define pikachu push_back
    342 #define ls(id) (id << 1 | 1)
    343 #define rs(id) ((id << 1) + 2)
    344 #define sqr(x) ((x) * (x))
    345 #define dlg(x) (31 - __builtin_clz(x))
    346 #define ulg(x) (32 - __builtin_clz(x))
    347 
    348 typedef pair<int, int> ipair;
    349 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
    350 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    351 
    352 const int MAXN = 200200;
    353 const int L = 26;
    354 
    355 int n;
    356 string srr[MAXN];
    357 int arr[MAXN], brr[MAXN], crr[MAXN];
    358 
    359 void build() {
    360 	for (int i = 0; i < n; ++i) {
    361 		for (char c: srr[i]) {
    362 			arr[i] ^= (1 << (c - 'a'));
    363 			brr[i] |= (1 << (c - 'a'));
    364 		}
    365 	}
    366 }
    367 
    368 long long calc(int c) {
    369 	int k = 0;
    370 	for (int i = 0; i < n; ++i)
    371 		if (brr[i] >> c & 1 ^ 1) crr[k++] = arr[i];
    372 	sort(crr, crr + k);
    373 	int mask = -1 & ((1 << L) - 1) ^ (1 << c);
    374 	long long ans = 0;
    375 	for (int i = 0; i < k; ++i) {
    376 		auto itl = lower_bound(crr, crr + k, crr[i] ^ mask);
    377 		auto itr = upper_bound(crr, crr + k, crr[i] ^ mask);
    378 		ans += itr - itl;
    379 	}
    380 	return ans >> 1LL;
    381 }
    382 
    383 long long solve() {
    384 	long long ans = 0;
    385 	for (int c = 0; c < L; ++c)
    386 		ans += calc(c);
    387 	return ans;
    388 }
    389 
    390 signed main() {
    391 	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    392 	cin >> n;
    393 	for (int i = 0; i < n; ++i)
    394 		cin >> srr[i];
    395 	build();
    396 	cout << solve() << endl;
    397 }
    398 ```
    399 
    400 [1800G - Symmetree](/contest/1800/problem/G "Codeforces Round 855 (Div. 3)")
    401 
    402 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    403 
    404 **Tutorial**
    405 
    406 Tutorial is loading...
    407 
    408 **Solution**
    409 
    410 ```
    411 #include <bits/stdc++.h>
    412 
    413 #define int long long
    414 #define pb emplace_back
    415 #define mp make_pair
    416 #define x first
    417 #define y second
    418 #define all(a) a.begin(), a.end()
    419 #define rall(a) a.rbegin(), a.rend()
    420 
    421 typedef long double ld;
    422 typedef long long ll;
    423 
    424 using namespace std;
    425 
    426 mt19937 rnd(time(nullptr));
    427 
    428 const int inf = 2e18;
    429 const ll M = 1e9;
    430 const ld pi = atan2(0, -1);
    431 const ld eps = 1e-6;
    432 
    433 int last;
    434 map<vector<int>, int> eq;
    435 map<int, bool> symmetrical;
    436 
    437 int dfs(int v, int p, vector<vector<int>> &sl){
    438     vector<int> children;
    439     for(int u: sl[v]){
    440         if(u == p) continue;
    441         children.emplace_back(dfs(u, v, sl));
    442     }
    443     sort(all(children));
    444     if(!eq.count(children)){
    445         map<int, int> cnt;
    446         for(int e: children){
    447             cnt[e]++;
    448         }
    449         int odd = 0, bad = 0;
    450         for(auto e: cnt){
    451             if(e.y & 1){
    452                 odd++;
    453                 bad += !symmetrical[e.x];
    454             }
    455         }
    456         eq[children] = last;
    457         symmetrical[last] = odd < 2 && bad == 0;
    458         last++;
    459     }
    460     return eq[children];
    461 }
    462 
    463 void solve(int tc){
    464     int n;
    465     cin >> n;
    466     eq.clear();
    467     symmetrical.clear();
    468     eq[vector<int>(0)] = 0;
    469     symmetrical[0] = true;
    470     last = 1;
    471     vector<vector<int>> sl(n);
    472     for(int i = 1; i < n; ++i){
    473         int u, v;
    474         cin >> u >> v;
    475         sl[--u].emplace_back(--v);
    476         sl[v].emplace_back(u);
    477     }
    478     cout << (symmetrical[dfs(0, 0, sl)]? "YES" : "NO");
    479 }
    480 
    481 bool multi = true;
    482 
    483 signed main() {
    484     int t = 1;
    485     if (multi)cin >> t;
    486     for (int i = 1; i <= t; ++i) {
    487         solve(i);
    488         cout << "\n";
    489     }
    490     return 0;
    491 }
    492 ```