1861.md (11864B)
1 Source: https://codeforces.com/blog/entry/119964 2 3 [1861A - Prime Deletion](/contest/1861/problem/A "Educational Codeforces Round 154 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 int t; 21 cin >> t; 22 for(int i = 0; i < t; i++) 23 { 24 string s; 25 cin >> s; 26 if(s.find("1") < s.find("3")) 27 cout << 13; 28 else 29 cout << 31; 30 cout << endl; 31 } 32 } 33 ``` 34 35 [1861B - Two Binary Strings](/contest/1861/problem/B "Educational Codeforces Round 154 (Rated for Div. 2)") 36 37 Idea: [Roms](/profile/Roms "Master Roms") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (Roms)** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 int t; 52 cin >> t; 53 for (int tc = 0; tc < t; ++tc) { 54 string a, b; 55 cin >> a >> b; 56 bool ok = false; 57 for (int i = 0; i + 1 < a.size(); ++i) { 58 if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') { 59 ok = true; 60 } 61 } 62 63 if (ok) 64 puts("YES"); 65 else 66 puts("NO"); 67 } 68 return 0; 69 } 70 ``` 71 72 [1861C - Queries for the Array](/contest/1861/problem/C "Educational Codeforces Round 154 (Rated for Div. 2)") 73 74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution 1 (Roms)** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 using namespace std; 86 87 const int N = 200000; 88 89 int main() { 90 int t; 91 cin >> t; 92 for (int tc = 0; tc < t; ++tc) { 93 string s; 94 cin >> s; 95 int maxSortedPref = 0; 96 int minNotSortedPref = 0; 97 int bal = 0; 98 bool good = true; 99 100 for (auto c : s) { 101 if (c == '+') { 102 ++bal; 103 } else if (c == '-') { 104 --bal; 105 maxSortedPref = min(maxSortedPref, bal); 106 if (bal < minNotSortedPref) 107 minNotSortedPref = 0; 108 } else if (c == '1') { 109 maxSortedPref = max(maxSortedPref, bal); 110 } else { 111 if (bal <= 1) { 112 good = false; 113 break; 114 } 115 if (minNotSortedPref == 0 || minNotSortedPref > bal) 116 minNotSortedPref = bal; 117 } 118 if(minNotSortedPref <= maxSortedPref && minNotSortedPref != 0) { 119 good = false; 120 break; 121 } 122 } 123 124 if (good) 125 puts("YES"); 126 else 127 puts("NO"); 128 } 129 return 0; 130 } 131 ``` 132 133 **Solution 2 (BledDest)** 134 135 ``` 136 #include<bits/stdc++.h> 137 138 using namespace std; 139 140 vector<int> has0, has1; 141 vector<vector<int>> g; 142 143 bool ans; 144 145 bool dfs(int x, int d) 146 { 147 if(has0[x] && (has1[x] || d <= 1)) 148 ans = false; 149 bool res = false; 150 for(auto y : g[x]) 151 res |= dfs(y, d + 1); 152 if(has0[x] && res) 153 ans = false; 154 return res || has1[x]; 155 } 156 157 void solve() 158 { 159 ans = true; 160 has0.push_back(0); 161 has1.push_back(0); 162 g.push_back(vector<int>()); 163 int ts = 1; 164 165 string s; 166 cin >> s; 167 vector<int> st = {0}; 168 for(auto x : s) 169 { 170 int cur = st.back(); 171 if(x == '0') 172 has0[cur] = 1; 173 if(x == '1') 174 has1[cur] = 1; 175 if(x == '+') 176 { 177 g[cur].push_back(ts); 178 st.push_back(ts); 179 ts++; 180 has0.push_back(0); 181 has1.push_back(0); 182 g.push_back(vector<int>()); 183 } 184 if(x == '-') 185 st.pop_back(); 186 } 187 188 dfs(0, 0); 189 cout << (ans ? "YES\n" : "NO\n"); 190 191 has0.clear(); 192 has1.clear(); 193 g.clear(); 194 } 195 196 int main() 197 { 198 ios_base::sync_with_stdio(0); 199 cin.tie(0); 200 int t; 201 cin >> t; 202 for(int i = 0; i < t; i++) 203 solve(); 204 } 205 ``` 206 207 [1861D - Sorting By Multiplication](/contest/1861/problem/D "Educational Codeforces Round 154 (Rated for Div. 2)") 208 209 Idea: [Roms](/profile/Roms "Master Roms") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution (Roms)** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 const int N = 200 * 1000 + 5; 223 224 int t; 225 int n; 226 int a[N]; 227 228 int main() { 229 cin >> t; 230 for (int tc = 0; tc < t; ++tc){ 231 cin >> n; 232 for (int i = 0; i < n; ++i) 233 cin >> a[i]; 234 235 int cnt = 0; 236 for (int i = 1; i < n; ++i) 237 cnt += (a[i - 1] >= a[i]); 238 239 int res = n, cnt2 = 0; 240 for (int i = 0; i <= n; ++i) { 241 bool isMultipliedByNegative = (i > 0); 242 res = min(res, isMultipliedByNegative + cnt + cnt2); 243 244 if (i + 1 < n) 245 cnt -= (a[i] >= a[i + 1]); 246 if (i > 0) 247 cnt2 += (a[i - 1] <= a[i]); 248 } 249 250 cout << res << endl; 251 } 252 } 253 ``` 254 255 [1861E - Non-Intersecting Subpermutations](/contest/1861/problem/E "Educational Codeforces Round 154 (Rated for Div. 2)") 256 257 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 258 259 **Tutorial** 260 261 Tutorial is loading... 262 263 **Solution (BledDest)** 264 265 ``` 266 #include<bits/stdc++.h> 267 268 using namespace std; 269 270 const int MOD = 998244353; 271 272 int add(int x, int y) 273 { 274 x += y; 275 while(x >= MOD) x -= MOD; 276 while(x < 0) x += MOD; 277 return x; 278 } 279 280 int sub(int x, int y) 281 { 282 return add(x, -y); 283 } 284 285 int mul(int x, int y) 286 { 287 return (x * 1ll * y) % MOD; 288 } 289 290 int binpow(int x, int y) 291 { 292 int z = 1; 293 while(y > 0) 294 { 295 if(y & 1) z = mul(z, x); 296 x = mul(x, x); 297 y /= 2; 298 } 299 return z; 300 } 301 302 int main() 303 { 304 int n, k; 305 cin >> n >> k; 306 int ans = 0; 307 vector<vector<int>> dp(n + 1, vector<int>(k, 0)); 308 dp[0][0] = 1; 309 for(int i = 0; i < n; i++) 310 { 311 int cur = 0; 312 for(int j = k - 1; j >= 1; j--) 313 { 314 cur = add(cur, dp[i][j]); 315 dp[i + 1][j] = cur; 316 } 317 for(int j = k - 1; j >= 0; j--) 318 { 319 int nxt = (j + 1) % k; 320 dp[i + 1][nxt] = add(dp[i + 1][nxt], mul(dp[i][j], k - j)); 321 } 322 ans = add(ans, mul(dp[i + 1][0], binpow(k, n - (i + 1)))); 323 } 324 cout << ans << endl; 325 } 326 ``` 327 328 [1861F - Four Suits](/contest/1861/problem/F "Educational Codeforces Round 154 (Rated for Div. 2)") 329 330 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 331 332 **Tutorial** 333 334 Tutorial is loading... 335 336 **Solution (BledDest)** 337 338 ``` 339 #include<bits/stdc++.h> 340 341 using namespace std; 342 343 const int K = 4; 344 const int N = 2 * int(1e6) + 43; 345 346 pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b) 347 { 348 return make_pair(a.first + b.first, a.second + b.second); 349 } 350 351 pair<long long, long long> operator-(const pair<long long, long long>& a, const pair<long long, long long>& b) 352 { 353 return make_pair(a.first - b.first, a.second - b.second); 354 } 355 356 // prefix sums for an array of pairs 357 vector<pair<long long, long long>> pref_sums(const vector<pair<long long, long long>>& a) 358 { 359 int n = a.size(); 360 vector<pair<long long, long long>> ans(n); 361 ans[0] = a[0]; 362 for(int i = 1; i < n; i++) 363 ans[i] = ans[i - 1] + a[i]; 364 return ans; 365 } 366 367 // for an array of pairs denoting linear functions, evaluate 368 // them in the corresponding points 369 vector<long long> eval(const vector<pair<long long, long long>>& a) 370 { 371 int n = a.size(); 372 vector<long long> ans(n); 373 for(int i = 0; i < n; i++) 374 ans[i] = a[i].first * i + a[i].second; 375 return ans; 376 } 377 378 void solve() 379 { 380 int n; 381 scanf("%d", &n); 382 vector<vector<int>> a(n, vector<int>(K)); 383 for(int i = 0; i < n; i++) 384 for(int j = 0; j < K; j++) 385 scanf("%d", &a[i][j]); 386 vector<int> b(K); 387 for(int i = 0; i < K; i++) 388 scanf("%d", &b[i]); 389 390 int deck_size = 0; 391 for(int i = 0; i < K; i++) 392 deck_size += b[i]; 393 394 // calculate the remaining number of cards for each player 395 long long full = deck_size; 396 for(int i = 0; i < n; i++) 397 for(int j = 0; j < K; j++) 398 full += a[i][j]; 399 vector<int> remain(n, full / n); 400 for(int i = 0; i < n; i++) 401 for(int j = 0; j < K; j++) 402 remain[i] -= a[i][j]; 403 404 // for every player, calculate the maximum number of cards 405 // they already have among all suits 406 // and store it in a multiset 407 vector<int> min_val(n); 408 for(int i = 0; i < n; i++) 409 min_val[i] = *max_element(a[i].begin(), a[i].end()); 410 multiset<int> min_vals; 411 for(int i = 0; i < n; i++) 412 min_vals.insert(min_val[i]); 413 414 // for every mask of suits and every player, calculate 415 // the number of cards in those suits they already have 416 vector<vector<int>> already_has(1 << K, vector<int>(n)); 417 for(int mask = 0; mask < (1 << K); mask++) 418 for(int i = 0; i < n; i++) 419 for(int j = 0; j < K; j++) 420 if(mask & (1 << j)) 421 already_has[mask][i] += a[i][j]; 422 // for every mask of suits and every player, calculate the 423 // maximum value of x such that if that player can receive 424 // no more than x cards in each suit, the vertex of that 425 // player should belong to T in the cut 426 vector<vector<int>> max_x(1 << K, vector<int>(n)); 427 for(int mask = 0; mask < (1 << K); mask++) 428 for(int i = 0; i < n; i++) 429 { 430 int suits = __builtin_popcount(mask); 431 if (suits == 0) max_x[mask][i] = N - 2; 432 else 433 { 434 // incoming edges have capacity of 435 // x - a[i][j] 436 int incoming = -already_has[mask][i]; 437 // outgoing edge has capacity of remain[i] 438 // find the maximum x such that 439 // suits * x + incoming < remains[i] 440 int x = (remain[i] - incoming) / suits; 441 x = min(x, N - 2); 442 max_x[mask][i] = x; 443 } 444 } 445 446 // for every mask and for all players, calculate the sum of 447 // values they add to the cut if they can have no more than 448 // x cards of each suit in the mask 449 vector<vector<long long>> add_to_cut(1 << K, vector<long long>(N)); 450 for(int mask = 0; mask < (1 << K); mask++) 451 { 452 int suits = __builtin_popcount(mask); 453 vector<pair<long long, long long>> aux(N); 454 for(int i = 0; i < n; i++) 455 { 456 // for the i-th player, they add remains[i] to 457 // the minimum cut if x > max_x[mask][i] 458 // otherwise, they add 459 // suits * x - already_has[mask][i] 460 int incoming = -already_has[mask][i]; 461 // add [suits * x - incoming] on segment [0, max_x] 462 int x = max_x[mask][i]; 463 pair<long long, long long> f1 = {suits, incoming}; 464 aux[0] = aux[0] + f1; 465 aux[x + 1] = aux[x + 1] - f1; 466 // add remain[i] on [max_x + 1, N) 467 pair<long long, long long> f2 = {0, remain[i]}; 468 aux[x + 1] = aux[x + 1] + f2; 469 aux[N - 1] = aux[N - 1] - f2; 470 } 471 // sum up those functions and evaluate them 472 add_to_cut[mask] = eval(pref_sums(aux)); 473 } 474 475 // now we're ready to solve the problem! 476 vector<int> ans(n); 477 // iterate on the player we want to maximize 478 for(int i = 0; i < n; i++) 479 { 480 // iterate on the suits they will maximize 481 for(int j = 0; j < K; j++) 482 { 483 int d = min(remain[i], b[j]); 484 int max_cards = a[i][j] + d; 485 b[j] -= d; 486 // find the maximum current score over all others 487 min_vals.erase(min_vals.find(min_val[i])); 488 int max_rival = *min_vals.rbegin(); 489 min_vals.insert(min_val[i]); 490 if(max_rival >= max_cards) 491 ans[i] = max(ans[i], 0); 492 else 493 { 494 // binary search on the maximum cards over all 495 // opponents 496 int L = max_rival - 1; 497 int R = max_cards; 498 while(R - L > 1) 499 { 500 int mid = (L + R) / 2; 501 long long min_cut = 1e18; 502 long long req_flow = deck_size - remain[i]; 503 // iterate on the mask of suit vertices 504 // which belong to S 505 for(int mask = 0; mask < (1 << K); mask++) 506 { 507 int suits = __builtin_popcount(mask); 508 long long cur_cut = 0; 509 for(int z = 0; z < K; z++) 510 if(!(mask & (1 << z))) 511 cur_cut += b[z]; 512 cur_cut += add_to_cut[mask][mid]; 513 // don't forget to discard our player 514 // from the flow network! 515 if(mid > max_x[mask][i]) 516 cur_cut -= remain[i]; 517 else 518 { 519 long long add = mid * suits - already_has[mask][i]; 520 cur_cut -= add; 521 } 522 min_cut = min(min_cut, cur_cut); 523 } 524 if(min_cut < req_flow) 525 L = mid; 526 else 527 R = mid; 528 } 529 ans[i] = max(ans[i], max_cards - R); 530 } 531 b[j] += d; 532 } 533 } 534 535 for(int i = 0; i < n; i++) 536 printf("%d ", ans[i]); 537 puts(""); 538 } 539 540 int main() 541 { 542 int t = 1; 543 for(int i = 0; i < t; i++) solve(); 544 } 545 ```