codeforces-scrape

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

1833.md (8690B)


      1 Source: https://codeforces.com/blog/entry/116636
      2 
      3 [1833A - Musical Puzzle](/contest/1833/problem/A "Codeforces Round 874 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n = int(input())
     16     s = input()
     17     cnt = set()
     18     for i in range(1, n):
     19         cnt.add(s[i - 1] + s[i])
     20     print(len(cnt))
     21 
     22 t = int(input())
     23 for _ in range(t):
     24     solve()
     25 ```
     26 
     27 [1833B - Restore the Weather](/contest/1833/problem/B "Codeforces Round 874 (Div. 3)")
     28 
     29 Idea: [myav](/profile/myav "Pupil myav"), prepared: [myav](/profile/myav "Pupil myav")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution**
     36 
     37 ```
     38 #include<bits/stdc++.h>
     39 using namespace std;
     40 void  solve(){
     41     int n, k;
     42     cin >> n >> k;
     43     vector<pair<int, int>>a(n);
     44     vector<int>b(n), ans(n);
     45     for(int i = 0; i < n; i++){
     46         cin >> a[i].first;
     47         a[i].second = i;
     48     }
     49     for(auto &i : b) cin >> i;
     50     sort(b.begin(), b.end());
     51     sort(a.begin(), a.end());
     52 
     53     for(int i = 0; i < n; i++){
     54         ans[a[i].second] = b[i];
     55     }
     56     for(auto &i : ans) cout << i << ' ';
     57     cout << endl;
     58 }
     59 int main(){
     60     int t;
     61     cin >> t;
     62     while(t--) solve();
     63 }
     64 ```
     65 
     66 [1833C - Vlad Building Beautiful Array](/contest/1833/problem/C "Codeforces Round 874 (Div. 3)")
     67 
     68 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     69 
     70 **Tutorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution**
     75 
     76 ```
     77 def solve():
     78     n = int(input())
     79     a = [int(x) for x in input().split()]
     80     a.sort()
     81     if a[0] % 2 == 1:
     82         print("YES")
     83         return
     84     for i in range(n):
     85         if a[i] % 2 == 1:
     86             print("NO")
     87             return
     88     print("YES")
     89 
     90 t = int(input())
     91 for _ in range(t):
     92     solve()
     93 ```
     94 
     95 [1833D - Flipper](/contest/1833/problem/D "Codeforces Round 874 (Div. 3)")
     96 
     97 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Aris](/profile/Aris "Candidate Master Aris")
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Solution**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107 
    108 using namespace std;
    109 
    110 #define forn(i, n) for (int i = 0; i < int(n); i++)
    111 #define sz(v) (int)v.size()
    112 #define all(v) v.begin(),v.end()
    113 #define eb emplace_back
    114 
    115 void solve() {
    116     int n; cin >> n;
    117     vector<int> p(n);
    118     for (auto &e : p) cin >> e;
    119 
    120     int r = 0;
    121     for (int i = 0; i < n; ++i) {
    122         if (p[min(n-1, r+1)] <= p[min(n-1, i+1)]) {
    123             r = i;
    124         }
    125     }
    126     vector<int> ans;
    127     for (int i = r + 1; i < n; ++i) ans.eb(p[i]);
    128     ans.eb(p[r]);
    129     for (int i = r-1; i >= 0; --i) {
    130         if (p[i] > p[0]) {
    131             ans.eb(p[i]);
    132         } else {
    133             for (int j = 0; j <= i; ++j) {
    134                 ans.eb(p[j]);
    135             }
    136             break;
    137         }
    138     }
    139     for (auto e : ans) cout << e << ' ';
    140     cout << endl;
    141 }
    142 
    143 int main() {
    144     int t;
    145     cin >> t;
    146 
    147     forn(tt, t) {
    148         solve();
    149     }
    150 }
    151 ```
    152 
    153 [1833E - Round Dance](/contest/1833/problem/E "Codeforces Round 874 (Div. 3)")
    154 
    155 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution**
    162 
    163 ```
    164 #include <iostream>
    165 #include <vector>
    166 #include <set>
    167 #include <queue>
    168 #include <algorithm>
    169 
    170 using namespace std;
    171 
    172 typedef long long ll;
    173 
    174 void solve() {
    175     int n;
    176     cin >> n;
    177     vector<int> a(n);
    178     vector<set<int>> g(n);
    179     vector<set<int>> neighbours(n);
    180     vector<int> d(n);
    181     for (int i = 0; i < n; ++i) {
    182         cin >> a[i];
    183         a[i]--;
    184         g[i].insert(a[i]);
    185         g[a[i]].insert(i);
    186     }
    187     for (int i = 0; i < n; ++i) {
    188         d[i] = g[i].size();
    189     }
    190     int bamboos = 0, cycles = 0;
    191     vector<bool> vis(n);
    192     for (int i = 0; i < n; ++i) {
    193         if (!vis[i]) {
    194             queue<int> q;
    195             q.push(i);
    196             vis[i] = true;
    197             vector<int> component = {i};
    198             while (!q.empty()) {
    199                 int u = q.front();
    200                 q.pop();
    201                 for (int v: g[u]) {
    202                     if (!vis[v]) {
    203                         vis[v] = true;
    204                         q.push(v);
    205                         component.push_back(v);
    206                     }
    207                 }
    208             }
    209             bool bamboo = false;
    210             for (int j: component) {
    211                 if (d[j] == 1) {
    212                     bamboo = true;
    213                     break;
    214                 }
    215             }
    216             if (bamboo) {
    217                 bamboos++;
    218             } else {
    219                 cycles++;
    220             }
    221         }
    222     }
    223     cout << cycles + min(bamboos, 1) << ' ' << cycles + bamboos << '\n';
    224 }
    225 
    226 int main() {
    227     int t;
    228     cin >> t;
    229     for (int _ = 0; _ < t; ++_) {
    230         solve();
    231     }
    232 }
    233 ```
    234 
    235 [1833F - Ira and Flamenco](/contest/1833/problem/F "Codeforces Round 874 (Div. 3)")
    236 
    237 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    238 
    239 **Tutorial**
    240 
    241 Tutorial is loading...
    242 
    243 **Solution**
    244 
    245 ```
    246 /*
    247          `)
    248         _ \
    249       (( }/  ,_
    250       )))__ /
    251      (((---'
    252        \ '
    253         )|____.---- )
    254        / \ `       (
    255       / ' \ `      )
    256      /  '  \  `   /
    257     /   '       _/
    258    /   _!____.-'
    259   /_.-'/    \
    260      |`_    |`_
    261 */
    262 #include <bits/stdc++.h>
    263 
    264 using namespace std;
    265 typedef pair<int, int> ipair;
    266 
    267 const int MAXN = 200200;
    268 const int MAXK = MAXN;
    269 const int MOD = 1000000007;
    270 
    271 inline int add(int a, int b) {
    272 	return (a + b >= MOD ? a + b - MOD : a + b);
    273 }
    274 
    275 inline int mul(int a, int b) {
    276 	return 1LL * a * b % MOD;
    277 }
    278 
    279 int n, m, k;
    280 int arr[MAXN], brr[MAXN], cnt[MAXK];
    281 
    282 void build() {
    283 	sort(arr, arr + n);
    284 	memcpy(brr, arr, sizeof(int) * n);
    285 	k = unique(arr, arr + n) - arr;
    286 	for (int j = 0; j < k; ++j)
    287 		cnt[j] = upper_bound(brr, brr + n, arr[j]) - lower_bound(brr, brr + n, arr[j]);
    288 }
    289 
    290 inline void push(stack<ipair> &S, int x) {
    291 	S.emplace(x, mul(x, S.empty() ? 1 : S.top().second));
    292 }
    293 
    294 int solve() {
    295 	if (k < m) return 0;
    296 	stack<ipair> S1, S2;
    297 	for (int j = 0; j < m; ++j)
    298 		push(S1, cnt[j]);
    299 	int ans = 0;
    300 	for (int j = m; j <= k; ++j) {
    301 		if (arr[j - 1] - arr[j - m] == m - 1)
    302 			ans = add(ans, mul(S1.empty() ? 1 : S1.top().second, S2.empty() ? 1 : S2.top().second));
    303 		if (S2.empty()) {
    304 			for (; !S1.empty(); S1.pop())
    305 				push(S2, S1.top().first);
    306 		}
    307 		S2.pop();
    308 		push(S1, cnt[j]);
    309 	}
    310 	return ans;
    311 }
    312 
    313 int main() {
    314 	int t; cin >> t;
    315 	while (t--) {
    316 		cin >> n >> m;
    317 		for (int i = 0; i < n; ++i)
    318 			cin >> arr[i];
    319 		build();
    320 		cout << solve() << endl;
    321 	}
    322 }
    323 ```
    324 
    325 [1833G - Ksyusha and Chinchilla](/contest/1833/problem/G "Codeforces Round 874 (Div. 3)")
    326 
    327 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    328 
    329 **Tutorial**
    330 
    331 Tutorial is loading...
    332 
    333 **Solution**
    334 
    335 ```
    336 #include <bits/stdc++.h>
    337 
    338 using namespace std;
    339 typedef pair<int, int> ipair;
    340 
    341 const int MAXN = 200200;
    342 
    343 int n;
    344 vector<ipair> gr[MAXN];
    345 vector<int> res;
    346 queue<int> qu;
    347 int par[MAXN], ipar[MAXN], deg[MAXN], hard[MAXN];
    348 
    349 void init() {
    350 	res.clear();
    351 	while (!qu.empty()) qu.pop();
    352 	memset(deg, 0, sizeof(int) * n);
    353 	memset(hard, 0, sizeof(int) * n);
    354 	for (int v = 0; v < n; ++v)
    355 		gr[v].clear();
    356 }
    357 
    358 void dfs(int v, int p, int ip) {
    359 	par[v] = p;
    360 	ipar[v] = ip;
    361 	for (auto [u, i]: gr[v]) {
    362 		if (u == p) continue;
    363 		dfs(u, v, i);
    364 		++deg[v];
    365 		hard[v] += (deg[u] > 0);
    366 	}
    367 }
    368 
    369 void build() {
    370 	dfs(0, -1, -1);
    371 }
    372 
    373 bool rempar(int v) {
    374 	int u = par[v];
    375 	if (u == -1) return true;
    376 	par[v] = -1;
    377 	res.push_back(ipar[v]);
    378 	--deg[u], --hard[u];
    379 	if (deg[u]) {
    380 		if (!hard[u]) qu.push(u);
    381 		return true;
    382 	}
    383 	if (par[u] == -1) return false;
    384 	--hard[par[u]];
    385 	if (!hard[par[u]]) qu.push(par[u]);
    386 	return true;
    387 }
    388 
    389 bool solve() {
    390 	if (n % 3) return false;
    391 	for (int v = 0; v < n; ++v)
    392 		if (!hard[v] && deg[v]) qu.push(v);
    393 	while (!qu.empty()) {
    394 		int v = qu.front(); qu.pop();
    395 		if (deg[v] > 2) return false;
    396 		if (deg[v] == 2) {
    397 			if (!rempar(v)) return false;
    398 		} else if (deg[v] == 1) {
    399 			if (par[v] == -1) return false;
    400 			for (auto [u, i]: gr[par[v]]) {
    401 				if (u == par[par[v]] || u == v || par[u] == -1) continue;
    402 				if (!deg[u]) return false;
    403 				res.push_back(i);
    404 				par[u] = -1;
    405 			}
    406 			if (!rempar(par[v])) return false;
    407 		}
    408 	}
    409 	return true;
    410 }
    411 
    412 int main() {
    413 	int t; cin >> t;
    414 	while (t--) {
    415 		cin >> n, init();
    416 		for (int i = 1; i < n; ++i) {
    417 			int v, u; cin >> v >> u, --v, --u;
    418 			gr[v].emplace_back(u, i);
    419 			gr[u].emplace_back(v, i);
    420 		}
    421 		build();
    422 		if (!solve()) {
    423 			cout << -1 << endl;
    424 			continue;
    425 		}
    426 		cout << res.size() << endl;
    427 		for (int id: res)
    428 			cout << id << ' ';
    429 		cout << endl;
    430 	}
    431 }
    432 ```