999.md (7375B)
1 Source: https://codeforces.com/blog/entry/60138 2 3 I'm really sorry for the issue with the problem D difficulty, it was much harder than i expected, and there was a big difficulty gap between problems C and D. I hope in the next rounds it will never happen again. 4 5 **UPD**: I'd like to say a big thanks to [kevinsogo](/profile/kevinsogo "Grandmaster kevinsogo") for the great help with tutorials and the round preparation in general. 6 7 [999A - Mishka and Contest](/contest/999/problem/A "Codeforces Round 490 (Div. 3)") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution (Vovuh)** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 int main() { 21 #ifdef _DEBUG 22 freopen("input.txt", "r", stdin); 23 // freopen("output.txt", "w", stdout); 24 #endif 25 26 int n, k; 27 cin >> n >> k; 28 vector<int> a(n); 29 for (int i = 0; i < n; ++i) 30 cin >> a[i]; 31 32 int ans = 0; 33 while (!a.empty() && a.back() <= k) { 34 ++ans; 35 a.pop_back(); 36 } 37 reverse(a.begin(), a.end()); 38 while (!a.empty() && a.back() <= k) { 39 ++ans; 40 a.pop_back(); 41 } 42 43 cout << ans << endl; 44 45 return 0; 46 } 47 ``` 48 49 [999B - Reversing Encryption](/contest/999/problem/B "Codeforces Round 490 (Div. 3)") 50 51 **Tutorial** 52 53 Tutorial is loading... 54 55 **Solution (Vovuh)** 56 57 ``` 58 #include <bits/stdc++.h> 59 60 using namespace std; 61 62 int main() { 63 #ifdef _DEBUG 64 freopen("input.txt", "r", stdin); 65 // freopen("output.txt", "w", stdout); 66 #endif 67 68 int n; 69 string s; 70 cin >> n >> s; 71 for (int i = 1; i <= n; ++i) { 72 if (n % i == 0) { 73 reverse(s.begin(), s.begin() + i); 74 } 75 } 76 cout << s << endl; 77 78 return 0; 79 } 80 ``` 81 82 [999C - Alphabetic Removals](/contest/999/problem/C "Codeforces Round 490 (Div. 3)") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution 1 (Vovuh)** 89 90 ``` 91 #include <bits/stdc++.h> 92 93 using namespace std; 94 95 int main() { 96 #ifdef _DEBUG 97 freopen("input.txt", "r", stdin); 98 // freopen("output.txt", "w", stdout); 99 #endif 100 101 int n, k; 102 cin >> n >> k; 103 string s; 104 cin >> s; 105 106 vector<int> cnt(26); 107 for (auto c : s) ++cnt[c - 'a']; 108 109 int pos = 26; 110 for (int i = 0; i < 26; ++i) { 111 if (k >= cnt[i]) { 112 k -= cnt[i]; 113 } else { 114 pos = i; 115 break; 116 } 117 } 118 119 string ans; 120 int rem = k; 121 for (auto c : s) { 122 int cur = c - 'a'; 123 if (cur > pos || (cur == pos && rem == 0)) { 124 ans += c; 125 } else if (cur == pos) { 126 --rem; 127 } 128 } 129 130 cout << ans << endl; 131 132 return 0; 133 } 134 ``` 135 136 **Solution 2 (Vovuh)** 137 138 ``` 139 #include <bits/stdc++.h> 140 141 using namespace std; 142 143 int main() { 144 #ifdef _DEBUG 145 freopen("input.txt", "r", stdin); 146 // freopen("output.txt", "w", stdout); 147 #endif 148 149 int n, k; 150 cin >> n >> k; 151 string s; 152 cin >> s; 153 154 vector<pair<char, int>> c(n); 155 for (int i = 0; i < n; ++i) 156 c[i] = make_pair(s[i], i); 157 sort(c.begin(), c.end()); 158 sort(c.begin() + k, c.end(), [&] (const pair<char, int> &a, const pair<char, int> &b) { 159 return a.second < b.second; 160 }); 161 162 for (int i = k; i < n; ++i) 163 cout << c[i].first; 164 cout << endl; 165 166 return 0; 167 } 168 ``` 169 170 [999D - Equalize the Remainders](/contest/999/problem/D "Codeforces Round 490 (Div. 3)") 171 172 **Tutorial** 173 174 Tutorial is loading... 175 176 **Solution (Vovuh)** 177 178 ``` 179 #include <bits/stdc++.h> 180 181 using namespace std; 182 183 int main() { 184 #ifdef _DEBUG 185 freopen("input.txt", "r", stdin); 186 // freopen("output.txt", "w", stdout); 187 #endif 188 189 int n, m; 190 cin >> n >> m; 191 int k = n / m; 192 vector<int> a(n); 193 vector<vector<int>> val(m); 194 for (int i = 0; i < n; ++i) { 195 cin >> a[i]; 196 val[a[i] % m].push_back(i); 197 } 198 199 long long ans = 0; 200 vector<pair<int, int>> fre; 201 for (int i = 0; i < 2 * m; ++i) { 202 int cur = i % m; 203 while (int(val[cur].size()) > k) { 204 int elem = val[cur].back(); 205 val[cur].pop_back(); 206 fre.push_back(make_pair(elem, i)); 207 } 208 while (int(val[cur].size()) < k && !fre.empty()) { 209 int elem = fre.back().first; 210 int mmod = fre.back().second; 211 fre.pop_back(); 212 val[cur].push_back(elem); 213 a[elem] += i - mmod; 214 ans += i - mmod; 215 } 216 } 217 218 cout << ans << endl; 219 for (int i = 0; i < n; ++i) 220 cout << a[i] << " "; 221 cout << endl; 222 223 return 0; 224 } 225 ``` 226 227 [999E - Reachability from the Capital](/contest/999/problem/E "Codeforces Round 490 (Div. 3)") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution (Vovuh)** 234 235 ``` 236 #include <bits/stdc++.h> 237 238 using namespace std; 239 240 const int N = 5010; 241 242 int n, m, s; 243 vector<int> g[N]; 244 bool used[N]; 245 bool ok[N]; 246 247 int cnt; 248 249 void dfs1(int v) { 250 ok[v] = true; 251 for (auto to : g[v]) 252 if (!ok[to]) 253 dfs1(to); 254 } 255 256 void dfs2(int v) { 257 used[v] = true; 258 ++cnt; 259 for (auto to : g[v]) 260 if (!used[to] && !ok[to]) 261 dfs2(to); 262 } 263 264 int main() { 265 #ifdef _DEBUG 266 freopen("input.txt", "r", stdin); 267 // freopen("output.txt", "w", stdout); 268 #endif 269 270 cin >> n >> m >> s; 271 --s; 272 for (int i = 0; i < m; ++i) { 273 int x, y; 274 cin >> x >> y; 275 --x, --y; 276 g[x].push_back(y); 277 } 278 279 dfs1(s); 280 281 vector<pair<int, int>> val; 282 for (int i = 0; i < n; ++i) { 283 if (!ok[i]) { 284 cnt = 0; 285 memset(used, false, sizeof(used)); 286 dfs2(i); 287 val.push_back(make_pair(cnt, i)); 288 } 289 } 290 sort(val.begin(), val.end()); 291 reverse(val.begin(), val.end()); 292 293 int ans = 0; 294 for (auto it : val) { 295 if (!ok[it.second]) { 296 ++ans; 297 dfs1(it.second); 298 } 299 } 300 301 cout << ans << endl; 302 303 return 0; 304 } 305 ``` 306 307 **Linear Solution (Vovuh)** 308 309 ``` 310 #include <bits/stdc++.h> 311 312 using namespace std; 313 314 const int N = 5010; 315 316 int n, m, s; 317 vector<int> g[N]; 318 vector<int> tg[N]; 319 vector<int> cg[N]; 320 vector<int> ord; 321 int indeg[N]; 322 bool ucomp[N]; 323 bool used[N]; 324 int comp[N]; 325 int cnt; 326 327 void dfs1(int v) { 328 used[v] = true; 329 for (auto to : g[v]) 330 if (!used[to]) 331 dfs1(to); 332 ord.push_back(v); 333 } 334 335 void dfs2(int v) { 336 comp[v] = cnt; 337 for (auto to : tg[v]) 338 if (comp[to] == -1) 339 dfs2(to); 340 } 341 342 void dfs3(int v) { 343 ucomp[v] = true; 344 for (auto to : cg[v]) 345 if (!ucomp[to]) 346 dfs3(to); 347 } 348 349 int main() { 350 #ifdef _DEBUG 351 freopen("input.txt", "r", stdin); 352 // freopen("output.txt", "w", stdout); 353 #endif 354 355 cin >> n >> m >> s; 356 --s; 357 for (int i = 0; i < m; ++i) { 358 int x, y; 359 cin >> x >> y; 360 --x, --y; 361 g[x].push_back(y); 362 tg[y].push_back(x); 363 } 364 365 for (int i = 0; i < n; ++i) { 366 if (!used[i]) { 367 dfs1(i); 368 } 369 } 370 371 reverse(ord.begin(), ord.end()); 372 memset(comp, -1, sizeof(comp)); 373 for (int i = 0; i < n; ++i) { 374 if (comp[ord[i]] == -1) { 375 dfs2(ord[i]); 376 ++cnt; 377 } 378 } 379 380 for (int v = 0; v < n; ++v) { 381 for (auto to : g[v]) { 382 if (comp[v] != comp[to]) { 383 cg[comp[v]].push_back(comp[to]); 384 ++indeg[comp[to]]; 385 } 386 } 387 } 388 389 dfs3(comp[s]); 390 int ans = 0; 391 for (int i = 0; i < cnt; ++i) 392 if (!ucomp[i] && indeg[i] == 0) 393 ++ans; 394 395 cout << ans << endl; 396 397 return 0; 398 } 399 ``` 400 401 [999F - Cards and Joy](/contest/999/problem/F "Codeforces Round 490 (Div. 3)") 402 403 **Tutorial** 404 405 Tutorial is loading... 406 407 **Solution (Vovuh)** 408 409 ``` 410 #include <bits/stdc++.h> 411 412 using namespace std; 413 414 const int N = 520; 415 const int K = 12; 416 const int C = 100 * 1000 + 11; 417 418 int n, k; 419 int c[C]; 420 int f[C]; 421 vector<int> h; 422 423 int dp[N][K * N]; 424 425 int main() { 426 #ifdef _DEBUG 427 freopen("input.txt", "r", stdin); 428 // freopen("output.txt", "w", stdout); 429 #endif 430 431 cin >> n >> k; 432 h = vector<int>(k + 1); 433 for (int i = 0; i < n * k; ++i) { 434 int x; 435 cin >> x; 436 ++c[x]; 437 } 438 for (int i = 0; i < n; ++i) { 439 int x; 440 cin >> x; 441 ++f[x]; 442 } 443 for (int i = 1; i <= k; ++i) 444 cin >> h[i]; 445 446 for (int i = 0; i < n; ++i) { 447 for (int j = 0; j <= n * k; ++j) { 448 for (int cur = 0; cur <= k; ++cur) { 449 dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]); 450 } 451 } 452 } 453 454 int ans = 0; 455 for (int i = 0; i < C; ++i) { 456 if (f[i] != 0) ans += dp[f[i]][c[i]]; 457 } 458 459 cout << ans << endl; 460 461 return 0; 462 } 463 ```