2169.md (10400B)
1 Source: https://codeforces.com/blog/entry/148390 2 3 [2169A - Alice and Bob](/contest/2169/problem/A "Educational Codeforces Round 184 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int t; 19 20 int main() { 21 cin >> t; 22 for (int tc = 0; tc < t; ++tc) { 23 int n, a; 24 cin >> n >> a; 25 vector <int> v(n); 26 int l = 0, r = 0; 27 for (int i = 0; i < n; ++i) { 28 cin >> v[i]; 29 if (a > v[i]) ++l; 30 if (a < v[i]) ++r; 31 } 32 33 cout << (l > r ? a - 1 : a + 1) << endl; 34 } 35 return 0; 36 } 37 ``` 38 39 [2169B - Drifting Away](/contest/2169/problem/B "Educational Codeforces Round 184 (Rated for Div. 2)") 40 41 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution (awoo)** 48 49 ``` 50 for _ in range(int(input())): 51 s = input() 52 for i in range(len(s) - 1): 53 if s[i] != '<' and s[i + 1] != '>': 54 print(-1) 55 break 56 else: 57 print(len(s) - min(s.count('<'), s.count('>'))) 58 ``` 59 60 [2169C - Range Operation](/contest/2169/problem/C "Educational Codeforces Round 184 (Rated for Div. 2)") 61 62 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (Neon)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 using namespace std; 74 75 using li = long long; 76 77 int main() { 78 int t; 79 cin >> t; 80 while (t--) { 81 int n; 82 cin >> n; 83 li s = 0, mn = 0, bst = 0; 84 for (int i = 0; i < n; ++i) { 85 int x; 86 cin >> x; 87 s += x; 88 li cur = (i + 1) * li(i + 2) - s; 89 mn = min(mn, cur); 90 bst = max(bst, cur - mn); 91 } 92 cout << s + bst << '\n'; 93 } 94 } 95 ``` 96 97 [2169D1 - Removal of a Sequence (Easy Version)](/contest/2169/problem/D1 "Educational Codeforces Round 184 (Rated for Div. 2)") 98 99 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (FelixArg)** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 using namespace std; 111 112 const long long INF = 1000000000000LL + 1; 113 114 void solve(){ 115 int x; 116 long long y, k; 117 118 cin >> x >> y >> k; 119 120 long long l = 1, r = INF; 121 long long m; 122 123 while(l <= r){ 124 m = l + (r - l) / 2; 125 long long ost = (m - 1); 126 for (int i = 0; i < x; i++){ 127 ost -= ost / y; 128 } 129 if (ost + 1 > k){ 130 r = m - 1; 131 } 132 else{ 133 l = m + 1; 134 } 135 } 136 137 if (r == INF){ 138 cout << -1 << '\n'; 139 } 140 else{ 141 cout << r << '\n'; 142 } 143 } 144 145 signed main() 146 { 147 #ifdef FELIX 148 auto _clock_start = chrono::high_resolution_clock::now(); 149 #endif 150 ios_base::sync_with_stdio(false); 151 cin.tie(0); 152 cout.tie(0); 153 154 int t = 1; 155 cin >> t; 156 while(t--){ 157 solve(); 158 } 159 160 #ifdef FELIX 161 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 162 chrono::high_resolution_clock::now() 163 - _clock_start).count() << "ms." << endl; 164 #endif 165 return 0; 166 } 167 ``` 168 169 [2169D2 - Removal of a Sequence (Hard Version)](/contest/2169/problem/D2 "Educational Codeforces Round 184 (Rated for Div. 2)") 170 171 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 172 173 **Tutorial** 174 175 Tutorial is loading... 176 177 **Solution (FelixArg)** 178 179 ``` 180 #include <bits/stdc++.h> 181 182 using namespace std; 183 184 #define int long long 185 186 const int INF = 1'000'000'000'000LL; 187 188 void solve(){ 189 int x, y, k; 190 cin >> x >> y >> k; 191 192 if (y == 1){ 193 cout << -1 << '\n'; 194 return; 195 } 196 197 for (int i = 0; i < x; ){ 198 int cur = (k - 1) / (y - 1); 199 if (cur == 0){ 200 break; 201 } 202 int fk = (cur + 1) * (y - 1) + 1; 203 int cnt = (fk - k + cur - 1) / cur; 204 cnt = min(x - i, cnt); 205 k += cnt * cur; 206 if (k > INF){ 207 cout << -1 << '\n'; 208 return; 209 } 210 i += cnt; 211 } 212 213 cout << k << '\n'; 214 } 215 216 signed main() 217 { 218 #ifdef FELIX 219 auto _clock_start = chrono::high_resolution_clock::now(); 220 #endif 221 ios_base::sync_with_stdio(false); 222 cin.tie(0); 223 cout.tie(0); 224 225 int t = 1; 226 cin >> t; 227 while(t--){ 228 solve(); 229 } 230 231 #ifdef FELIX 232 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 233 chrono::high_resolution_clock::now() 234 - _clock_start).count() << "ms." << endl; 235 #endif 236 return 0; 237 } 238 ``` 239 240 [2169E - Points Selection](/contest/2169/problem/E "Educational Codeforces Round 184 (Rated for Div. 2)") 241 242 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 243 244 **Tutorial** 245 246 Tutorial is loading... 247 248 **Solution (BledDest)** 249 250 ``` 251 #include<bits/stdc++.h> 252 253 using namespace std; 254 255 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 256 #define sz(a) int((a).size()) 257 258 typedef long long li; 259 260 const int INF = int(1e9); 261 const li INF64 = li(1e18); 262 263 int n; 264 vector<li> x[3]; 265 266 bool read() { 267 if(!(cin >> n)) 268 return false; 269 fore (k, 0, 3) { 270 x[k].resize(n); 271 fore (i, 0, n) 272 cin >> x[k][i]; 273 } 274 return true; 275 } 276 277 void solve() { 278 vector< vector<li> > w(n, vector<li>(1 << 4, 0)); 279 fore (i, 0, n) { 280 fore (mask, 0, 1 << 4) { 281 fore (k, 0, 4) if ((mask >> k) & 1) 282 w[i][mask] += x[k & 1][i] * (k < 2 ? -1 : 1); 283 } 284 } 285 286 vector< vector<li> > d(n + 1, vector<li>(1 << 4, -INF64)); 287 d[0][0] = 0; 288 fore (i, 0, n) fore (mask, 0, 1 << 4) { 289 if (d[i][mask] < -INF64 / 2) 290 continue; 291 292 d[i + 1][mask] = max(d[i + 1][mask], d[i][mask] + x[2][i]); 293 294 int filter = ((1 << 4) - 1) ^ mask; 295 for (int cmask = filter; cmask > 0; cmask = (cmask - 1) & filter) 296 d[i + 1][mask | cmask] = max(d[i + 1][mask | cmask], d[i][mask] + 2ll * w[i][cmask]); 297 } 298 cout << d[n][(1 << 4) - 1] << endl; 299 } 300 301 int main() { 302 #ifdef _DEBUG 303 freopen("input.txt", "r", stdin); 304 int tt = clock(); 305 #endif 306 ios_base::sync_with_stdio(false); 307 308 int t; cin >> t; 309 while (t--) { 310 read(); 311 solve(); 312 313 #ifdef _DEBUG 314 cerr << "TIME = " << clock() - tt << endl; 315 tt = clock(); 316 #endif 317 } 318 return 0; 319 } 320 ``` 321 322 [2169F - Subsequence Problem](/contest/2169/problem/F "Educational Codeforces Round 184 (Rated for Div. 2)") 323 324 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 325 326 **Tutorial** 327 328 Tutorial is loading... 329 330 **Solution (BledDest)** 331 332 ``` 333 #include<bits/stdc++.h> 334 335 using namespace std; 336 337 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 338 #define sz(a) int((a).size()) 339 340 const int LOGN = 19; 341 const int MOD = 998244353; 342 int g = 3; 343 344 int mul(int a, int b) { 345 return int(a * 1ll * b % MOD); 346 } 347 int norm(int a) { 348 while(a >= MOD) a -= MOD; 349 while(a < 0) a += MOD; 350 return a; 351 } 352 int binPow (int a, int k) { 353 int ans = 1; 354 for (; k > 0; k >>= 1) { 355 if (k & 1) 356 ans = mul(ans, a); 357 a = mul(a, a); 358 } 359 return ans; 360 } 361 int inv(int a) { 362 return binPow(a, MOD - 2); 363 } 364 365 vector<int> w[LOGN], rv; 366 bool precalced = false; 367 368 void precalc() { 369 if(precalced) 370 return; 371 precalced = true; 372 373 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 374 fore(st, 0, LOGN) { 375 w[st].assign(1 << st, 1); 376 377 int bw = binPow(wb, 1 << (LOGN - st - 1)); 378 int cw = 1; 379 380 fore(k, 0, (1 << st)) { 381 w[st][k] = cw; 382 cw = mul(cw, bw); 383 } 384 } 385 386 rv.assign(1 << LOGN, 0); 387 fore(i, 1, sz(rv)) 388 rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1)); 389 } 390 391 const int MX = (1 << LOGN) + 3; 392 393 inline void fft(int a[MX], int n, bool inverse) { 394 precalc(); 395 396 int ln = __builtin_ctz(n); 397 assert((1 << ln) < MX); 398 assert((1 << ln) == n); 399 400 fore(i, 0, n) { 401 int ni = rv[i] >> (LOGN - ln); 402 if(i < ni) swap(a[i], a[ni]); 403 } 404 405 for(int st = 0; (1 << st) < n; st++) { 406 int len = (1 << st); 407 for(int k = 0; k < n; k += (len << 1)) { 408 fore(pos, k, k + len) { 409 int l = a[pos]; 410 int r = mul(a[pos + len], w[st][pos - k]); 411 412 a[pos] = norm(l + r); 413 a[pos + len] = norm(l - r); 414 } 415 } 416 } 417 418 if(inverse) { 419 int in = inv(n); 420 fore(i, 0, n) 421 a[i] = mul(a[i], in); 422 reverse(a + 1, a + n); 423 } 424 } 425 426 int aa[MX], bb[MX], cc[MX]; 427 428 vector<int> multiply(const vector<int> &a, const vector<int> &b, int cutoff) { 429 int ln = 1; 430 while(ln < (sz(a) + sz(b))) 431 ln <<= 1; 432 433 fore(i, 0, ln) 434 aa[i] = (i < sz(a) ? a[i] : 0); 435 fore(i, 0, ln) 436 bb[i] = (i < sz(b) ? b[i] : 0); 437 438 fft(aa, ln, false); 439 fft(bb, ln, false); 440 441 fore(i, 0, ln) 442 cc[i] = mul(aa[i], bb[i]); 443 fft(cc, ln, true); 444 445 vector<int> ans(cc, cc + ln); 446 while((ans.size() > 0 && ans.back() == 0) || ans.size() > cutoff) 447 ans.pop_back(); 448 return ans; 449 } 450 451 vector<int> fact, ifact; 452 453 void precalc_factorials(int s) { 454 fact.resize(s); 455 fact[0] = 1; 456 for(int i = 1; i < s; i++) 457 fact[i] = mul(fact[i - 1], i); 458 ifact.resize(s); 459 for(int i = 0; i < s; i++) 460 ifact[i] = inv(fact[i]); 461 } 462 463 int choose(int n, int k) { 464 if(n < 0 || n < k || k < 0) return 0; 465 return mul(fact[n], mul(ifact[n - k], ifact[k])); 466 } 467 468 int main() { 469 ios_base::sync_with_stdio(0); 470 cin.tie(0); 471 int n, m, k; 472 cin >> n >> m >> k; 473 vector<int> lens(k); 474 for(int i = 0; i < k; i++) cin >> lens[i]; 475 476 int cutoff = n + 1; 477 precalc_factorials(1 << LOGN); 478 vector<int> segments(6); 479 segments[0] = 1; 480 for(auto len : lens) 481 for(int i = 1; i <= len; i++) 482 segments[i]++; 483 vector<vector<int>> poly(6); 484 for(int i = 0; i < 6; i++) { 485 if(segments[i] == 0) 486 poly[i] = { 1 }; 487 else { 488 int choices = norm(m - i); 489 int p = 1; 490 poly[i].resize(cutoff); 491 for(int k = 0; k < cutoff; k++) { 492 int cur = mul(p, choose(k + segments[i] - 1, k)); 493 poly[i][k] = cur; 494 p = mul(p, choices); 495 } 496 } 497 } 498 vector<int> ans = { 1 }; 499 for(int i = 0; i < 6; i++) 500 ans = multiply(ans, poly[i], cutoff); 501 502 int used = 0; 503 int coef = 1; 504 for(auto len : lens) { 505 coef = mul(coef, fact[len]); 506 used += len; 507 } 508 int res = mul(coef, ans[n - used]); 509 cout << res << endl; 510 } 511 ```