1144.md (7476B)
1 Source: https://codeforces.com/blog/entry/66307 2 3 [1144A - Diverse Strings](/contest/1144/problem/A "Codeforces Round 550 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 20 int main() { 21 int n; 22 cin >> n; 23 forn(i, n) { 24 string s; 25 cin >> s; 26 if (set<char>(s.begin(), s.end()).size() == s.length() 27 && *max_element(s.begin(), s.end()) == char(*min_element(s.begin(), s.end()) + (s.length() - 1))) 28 cout << "Yes" << endl; 29 else 30 cout << "No" << endl; 31 } 32 } 33 ``` 34 35 [1144B - Parity Alternated Deletions](/contest/1144/problem/B "Codeforces Round 550 (Div. 3)") 36 37 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 #ifdef _DEBUG 52 freopen("input.txt", "r", stdin); 53 // freopen("output.txt", "w", stdout); 54 #endif 55 56 int n; 57 cin >> n; 58 int sum = 0; 59 vector<int> even, odd; 60 for (int i = 0; i < n; ++i) { 61 int x; 62 cin >> x; 63 sum += x; 64 if (x & 1) odd.push_back(x); 65 else even.push_back(x); 66 } 67 68 sort(odd.rbegin(), odd.rend()); 69 sort(even.rbegin(), even.rend()); 70 int k = min(odd.size(), even.size()); 71 int rem = sum; 72 rem -= accumulate(odd.begin(), odd.begin() + k, 0); 73 rem -= accumulate(even.begin(), even.begin() + k, 0); 74 if (int(odd.size()) > k) { 75 rem -= odd[k]; 76 } 77 if (int(even.size()) > k) { 78 rem -= even[k]; 79 } 80 81 cout << rem << endl; 82 83 return 0; 84 } 85 ``` 86 87 [1144C - Two Shuffled Sequences](/contest/1144/problem/C "Codeforces Round 550 (Div. 3)") 88 89 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 int main() { 103 #ifdef _DEBUG 104 freopen("input.txt", "r", stdin); 105 // freopen("output.txt", "w", stdout); 106 #endif 107 108 int n; 109 cin >> n; 110 vector<int> cnt(200 * 1000 + 1); 111 for (int i = 0; i < n; ++i) { 112 int x; 113 cin >> x; 114 ++cnt[x]; 115 if (cnt[x] > 2) { 116 cout << "NO" << endl; 117 return 0; 118 } 119 } 120 121 cout << "YES" << endl << count(cnt.begin(), cnt.end(), 2) << endl; 122 for (int i = 0; i <= 200 * 1000; ++i) { 123 if (cnt[i] == 2) { 124 cout << i << " "; 125 --cnt[i]; 126 } 127 } 128 cout << endl << count(cnt.begin(), cnt.end(), 1) << endl; 129 for (int i = 200 * 1000; i >= 0; --i) { 130 if (cnt[i] == 1) { 131 cout << i << " "; 132 --cnt[i]; 133 } 134 } 135 cout << endl; 136 137 assert(count(cnt.begin(), cnt.end(), 0) == 200 * 1000 + 1); 138 139 return 0; 140 } 141 ``` 142 143 [1144D - Equalize Them All](/contest/1144/problem/D "Codeforces Round 550 (Div. 3)") 144 145 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 146 147 **Tutorial** 148 149 Tutorial is loading... 150 151 **Solution** 152 153 ``` 154 #include <bits/stdc++.h> 155 156 using namespace std; 157 158 int main() { 159 #ifdef _DEBUG 160 freopen("input.txt", "r", stdin); 161 // freopen("output.txt", "w", stdout); 162 #endif 163 164 int n; 165 cin >> n; 166 167 vector<int> a(n), cnt(200 * 1000 + 1); 168 for (int i = 0; i < n; ++i) { 169 cin >> a[i]; 170 ++cnt[a[i]]; 171 } 172 173 int val = max_element(cnt.begin(), cnt.end()) - cnt.begin(); 174 int pos = find(a.begin(), a.end(), val) - a.begin(); 175 176 cout << n - cnt[val] << endl; 177 int siz = 0; 178 for (int i = pos - 1; i >= 0; --i) { 179 cout << 1 + (a[i] > a[i + 1]) << " " << i + 1 << " " << i + 2 << " " << endl; 180 a[i] = a[i + 1]; 181 ++siz; 182 } 183 for (int i = 0; i < n - 1; ++i) { 184 if (a[i + 1] != val) { 185 assert(a[i] == val); 186 cout << 1 + (a[i + 1] > a[i]) << " " << i + 2 << " " << i + 1 << " " << endl; 187 a[i + 1] = a[i]; 188 ++siz; 189 } 190 } 191 192 assert(siz == n - cnt[val]); 193 return 0; 194 } 195 ``` 196 197 [1144E - Median String](/contest/1144/problem/E "Codeforces Round 550 (Div. 3)") 198 199 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution** 206 207 ``` 208 #include <bits/stdc++.h> 209 210 using namespace std; 211 212 vector<int> get(const string &s) { 213 vector<int> res(s.size() + 1); 214 for (int i = 0; i < int(s.size()); ++i) { 215 res[i + 1] = s[i] - 'a'; 216 } 217 return res; 218 } 219 220 int main() { 221 #ifdef _DEBUG 222 freopen("input.txt", "r", stdin); 223 // freopen("output.txt", "w", stdout); 224 #endif 225 226 int k; 227 string s, t; 228 cin >> k >> s >> t; 229 vector<int> a = get(s), b = get(t); 230 231 for (int i = k; i >= 0; --i) { 232 a[i] += b[i]; 233 if (i) { 234 a[i - 1] += a[i] / 26; 235 a[i] %= 26; 236 } 237 } 238 239 for (int i = 0; i <= k; ++i) { 240 int rem = a[i] % 2; 241 a[i] /= 2; 242 if (i + 1 <= k) { 243 a[i + 1] += rem * 26; 244 } else { 245 assert(rem == 0); 246 } 247 } 248 249 for (int i = 1; i <= k; ++i) { 250 cout << char('a' + a[i]); 251 } 252 cout << endl; 253 254 return 0; 255 } 256 ``` 257 258 [1144F - Graph Without Long Directed Paths](/contest/1144/problem/F "Codeforces Round 550 (Div. 3)") 259 260 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 261 262 **Tutorial** 263 264 Tutorial is loading... 265 266 **Solution** 267 268 ``` 269 #include <bits/stdc++.h> 270 271 using namespace std; 272 273 const int N = 200 * 1000 + 11; 274 275 int n, m; 276 vector<int> g[N]; 277 vector<pair<int, int>> e; 278 279 bool bipartite; 280 vector<int> color; 281 282 void dfs(int v, int c) { 283 color[v] = c; 284 for (auto to : g[v]) { 285 if (color[to] == -1) { 286 dfs(to, c ^ 1); 287 } else { 288 if (color[to] == color[v]) { 289 bipartite = false; 290 } 291 } 292 } 293 } 294 295 int main() { 296 #ifdef _DEBUG 297 freopen("input.txt", "r", stdin); 298 // freopen("output.txt", "w", stdout); 299 #endif 300 301 cin >> n >> m; 302 for (int i = 0; i < m; ++i) { 303 int x, y; 304 cin >> x >> y; 305 --x, --y; 306 g[x].push_back(y); 307 g[y].push_back(x); 308 e.push_back(make_pair(x, y)); 309 } 310 311 bipartite = true; 312 color = vector<int>(n, -1); 313 dfs(0, 0); 314 315 if (!bipartite) { 316 cout << "NO" << endl; 317 return 0; 318 } 319 320 cout << "YES" << endl; 321 for (int i = 0; i < m; ++i) { 322 cout << (color[e[i].first] < color[e[i].second]); 323 } 324 cout << endl; 325 326 return 0; 327 } 328 ``` 329 330 [1144G - Two Merged Sequences](/contest/1144/problem/G "Codeforces Round 550 (Div. 3)") 331 332 [There](//codeforces.com/blog/entry/66284?#comment-503140) is different solution for the problem, it is pretty interesting! Thanks, [Roundgod](/profile/Roundgod "Grandmaster Roundgod")! 333 334 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 335 336 **Tutorial** 337 338 Tutorial is loading... 339 340 **Solution** 341 342 ``` 343 #include <bits/stdc++.h> 344 345 using namespace std; 346 347 const int INF = 1e9; 348 349 int main() { 350 #ifdef _DEBUG 351 freopen("input.txt", "r", stdin); 352 // freopen("output.txt", "w", stdout); 353 #endif 354 355 int n; 356 cin >> n; 357 vector<int> a(n); 358 for (int i = 0; i < n; ++i) { 359 cin >> a[i]; 360 } 361 362 vector<vector<int>> dp(n, vector<int>({-INF, INF})); 363 vector<vector<int>> p(n, vector<int>(2, -1)); 364 dp[0][0] = INF; 365 dp[0][1] = -INF; 366 367 for (int i = 1; i < n; ++i) { 368 { 369 if (a[i] > a[i - 1] && dp[i][0] < dp[i - 1][0]) { 370 dp[i][0] = dp[i - 1][0]; 371 p[i][0] = 0; 372 } 373 if (a[i] < dp[i - 1][0] && dp[i][1] > a[i - 1]) { 374 dp[i][1] = a[i - 1]; 375 p[i][1] = 0; 376 } 377 } 378 { 379 if (a[i] < a[i - 1] && dp[i][1] > dp[i - 1][1]) { 380 dp[i][1] = dp[i - 1][1]; 381 p[i][1] = 1; 382 } 383 if (a[i] > dp[i - 1][1] && dp[i][0] < a[i - 1]) { 384 dp[i][0] = a[i - 1]; 385 p[i][0] = 1; 386 } 387 } 388 } 389 390 int pos = -1; 391 if (dp[n - 1][0] != -INF) { 392 pos = 0; 393 } 394 if (dp[n - 1][1] != INF) { 395 pos = 1; 396 } 397 398 if (pos == -1) { 399 cout << "NO" << endl; 400 return 0; 401 } 402 403 vector<int> inInc(n); 404 for (int i = n - 1; i >= 0; --i) { 405 if (pos == 0) { 406 inInc[i] = 1; 407 } 408 pos = p[i][pos]; 409 } 410 411 cout << "YES" << endl; 412 for (int i = 0; i < n; ++i) { 413 cout << !inInc[i] << " "; 414 } 415 cout << endl; 416 417 return 0; 418 } 419 ```