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 ```