2185.md (16562B)
1 Source: https://codeforces.com/blog/entry/150288 2 3 Thank y'all so much for participating in my first Codeforces round! Special thanks to [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") for suggesting a major change to problem D and [Intellegent](/profile/Intellegent "Grandmaster Intellegent") for helping to rewrite the statement of problem F. 4 5 [2185A - Perfect Root](/contest/2185/problem/A "Codeforces Round 1074 (Div. 4)") 6 7 **Hint 1** 8 9 Fix an integer $x$, how could you find out the value of $y$? 10 11 **Hint 2** 12 13 Square both sides of the equation, for what values of $x$ is $x^2$ an integer? 14 15 **Editorial** 16 17 Tutorial is loading... 18 19 **Code** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 25 int main() { 26 int t; 27 cin >> t; 28 29 while (t--) { 30 int n; 31 cin >> n; 32 33 for (int i = 0; i < n; i++) cout << i+1 << " "; 34 cout << "\n"; 35 } 36 } 37 ``` 38 39 [2185B - Prefix Max](/contest/2185/problem/B "Codeforces Round 1074 (Div. 4)") 40 41 **Hint 1** 42 43 If we were to change the problem such that you could perform as many swaps as you wanted, the answer would remain the same. 44 45 **Hint 2** 46 47 Once our running sum encounters the maximum element of the array, the max of that prefix will always be the maximum element of the array. 48 49 **Editorial** 50 51 Tutorial is loading... 52 53 **Code** 54 55 ``` 56 #include <bits/stdc++.h> 57 using namespace std; 58 59 int main() { 60 int t; 61 cin >> t; 62 63 while (t--) { 64 int n; 65 cin >> n; 66 67 vector<int> vec(n); 68 for (auto &x: vec) cin >> x; 69 70 cout << *max_element(vec.begin(), vec.end()) * n << "\n"; 71 } 72 } 73 ``` 74 75 [2185C - Shifted MEX](/contest/2185/problem/C "Codeforces Round 1074 (Div. 4)") 76 77 **Solution 1: Hint 1** 78 79 Duplicate values don't matter, nor does the order of the elements. 80 81 **Solution 1: Hint 2** 82 83 Let's consider the inverse problem, where we have a array that is equal to [$0, 1, 2, \ldots, k-1$] and we can add $x$ to each value in the array. No matter which value of $x$ we choose, the values in $a$ are consecutive. 84 85 **Solution 2: Hint 1** 86 87 In order for the MEX to be greater than 0, 0 has to be contained in the array. 88 89 **Solution 2: Hint 2** 90 91 Since there are at most $3000$ elements in $a$, there are $3000$ possible values of $x$ that have a MEX greater than 0. 92 93 **Editorial** 94 95 Tutorial is loading... 96 97 **Solution 1: Code** 98 99 ``` 100 #include <bits/stdc++.h> 101 using namespace std; 102 103 int main() { 104 int t; 105 cin >> t; 106 107 while (t--) { 108 int n; 109 cin >> n; 110 111 vector<int> vec(n); 112 for (auto &x: vec) cin >> x; 113 114 sort(vec.begin(), vec.end()); 115 // Remove duplicates 116 vec.erase(unique(vec.begin(), vec.end()), vec.end()); 117 n = vec.size(); 118 int best = 0; 119 int current = 0; 120 for (int i = 0; i < n; i++) { 121 if (i == 0 || vec[i] != vec[i-1]+1) { 122 current = 0; 123 } 124 current++; 125 best = max(best, current); 126 } 127 cout << best << "\n"; 128 } 129 } 130 ``` 131 132 **Solution 2: Code** 133 134 ``` 135 #include <bits/stdc++.h> 136 using namespace std; 137 138 int main() { 139 int t; 140 cin >> t; 141 142 while (t--) { 143 int n; 144 cin >> n; 145 146 vector<int> vec(n); 147 for (auto &x: vec) cin >> x; 148 149 sort(vec.begin(), vec.end()); 150 int best = 0; 151 for (auto &x: vec) { 152 int next = 0; 153 for (int i = 0; i < vec.size(); i++) { 154 if (vec[i]-x == next) next++; 155 } 156 best = max(best, next); 157 } 158 cout << best << "\n"; 159 } 160 } 161 ``` 162 163 [2185D - OutOfMemoryError](/contest/2185/problem/D "Codeforces Round 1074 (Div. 4)") 164 165 **Hint 1** 166 167 Clearly, resetting all of the values is too slow, but we don't have to update all the elements at the same time. 168 169 **Hint 2** 170 171 If an element hasn't been modified after the last crash, it's value in the final array is the same as its value in the original array. 172 173 **Editorial** 174 175 Tutorial is loading... 176 177 **Code** 178 179 ``` 180 #include <bits/stdc++.h> 181 using namespace std; 182 #define ll long long 183 int main() { 184 int t; 185 cin >> t; 186 187 while (t--) { 188 int n, m, k; 189 cin >> n >> m >> k; 190 191 vector<int> vec(n); for (auto &x: vec) cin >> x; 192 vector<int> original_vec(n); for (int i = 0; i < n; i++) original_vec[i] = vec[i]; 193 vector<int> last_element_update(n, -1); 194 int last_reset = -1; 195 int reset_count = 0; 196 for (int i = 0; i < m; i++) { 197 int a, b; 198 cin >> a >> b; 199 a--; 200 201 if (last_element_update[a] < last_reset) vec[a] = original_vec[a]; 202 vec[a] += b; 203 if (vec[a] > k) { 204 last_reset = i; 205 reset_count++; 206 vec[a] = original_vec[a]; 207 } 208 last_element_update[a] = i; 209 } 210 211 ll sum = 0; 212 for (int i = 0; i < n; i++) { 213 214 if (last_element_update[i] < last_reset) vec[i] = original_vec[i]; 215 cout << vec[i] << " "; 216 } 217 cout << "\n"; 218 219 } 220 } 221 ``` 222 223 [2185E - The Robotic Rush](/contest/2185/problem/E "Codeforces Round 1074 (Div. 4)") 224 225 **Hint 1** 226 227 Each robot's movements is independent of another robot's movements. 228 229 **Hint 2** 230 231 We only need to care about the spikes directly to the right and left of the robot, if they exist. 232 233 **Hint 3** 234 235 To figure out when a robot dies, we don't need to care about the position of the robot, only the distance to its left and right spikes. 236 237 **Hint 4** 238 239 We only care about the left-most a robot has been and the right-most a robot has been. 240 241 **Editorial** 242 243 Tutorial is loading... 244 245 **Code** 246 247 ``` 248 #include <bits/stdc++.h> 249 using namespace std; 250 251 int main() { 252 int t; 253 cin >> t; 254 255 while (t--) { 256 int n, m, k; 257 cin >> n >> m >> k; 258 259 vector<int> robots(n); for (auto &x: robots) cin >> x; 260 261 vector<int> lava(m); for (auto &x: lava) cin >> x; 262 263 vector<bool> dead(n); 264 map<int, vector<int>> death_locations; 265 266 string instructions; 267 cin >> instructions; 268 269 sort(lava.begin(), lava.end()); 270 271 for (int i = 0; i < n; i++) { 272 if (lava[0] < robots[i]) { 273 int left_dist = robots[i] - (*(lower_bound(lava.begin(), lava.end(), robots[i]) - 1)); 274 death_locations[-left_dist].push_back(i); 275 } 276 if (lava[m-1] > robots[i]) { 277 int right_dist = *lower_bound(lava.begin(), lava.end(), robots[i]) - robots[i]; 278 death_locations[right_dist].push_back(i); 279 } 280 281 } 282 283 int current_pos = 0; 284 int alive = n; 285 286 for (auto &x: instructions) { 287 if (x == 'L') current_pos--; 288 else current_pos++; 289 290 for (int i: death_locations[current_pos]) { 291 292 if (dead[i]) continue; 293 dead[i] = true; 294 alive--; 295 } 296 death_locations[current_pos].clear(); 297 cout << alive << " "; 298 } 299 300 cout << "\n"; 301 } 302 } 303 ``` 304 305 [2185F - BattleCows](/contest/2185/problem/F "Codeforces Round 1074 (Div. 4)") 306 307 **Hint 1** 308 309 A single cow will only face $n$ matches. 310 311 **Hint 2** 312 313 XOR is cumulative, meaning the order of the cows in a stack doesn't change its skill level. 314 315 **Hint 3** 316 317 Similarly, the order of the cows in the stack doesn't change the final position of the cow who was given the potion in the final line. 318 319 **Hint 4** 320 321 You can calculate range XOR queries in O(1) using prefix sum. 322 323 **Editorial** 324 325 Tutorial is loading... 326 327 **Code** 328 329 ``` 330 #include <bits/stdc++.h> 331 using namespace std; 332 333 int main() { 334 int t; 335 cin >> t; 336 337 while (t--) { 338 int n, q; 339 cin >> n >> q; 340 341 int num_cows = (1<<n); 342 vector<int> cows(num_cows); for (auto &x: cows) cin >> x; 343 344 vector<int> prefix(num_cows); prefix[0] = cows[0]; 345 for (int i = 1; i < num_cows; i++) { 346 prefix[i] = cows[i] ^ prefix[i-1]; 347 } 348 349 while (q--) { 350 int cow_idx, skill_level; 351 cin >> cow_idx >> skill_level; 352 cow_idx--; 353 354 int curr_position = 0; 355 for (int i = 0; i < n; i++) { 356 int size = (1<<i); 357 int leader_idx = cow_idx / size; 358 359 int leader_value = prefix[(size)*(leader_idx+1)-1] ^ (leader_idx == 0 ? 0 : prefix[(size)*(leader_idx)-1]); 360 leader_value ^= cows[cow_idx]; 361 leader_value ^= skill_level; 362 363 int enemy_value; 364 if (leader_idx % 2 == 0) { 365 enemy_value = prefix[(size)*(leader_idx+2)-1] ^ prefix[(size)*(leader_idx+1)-1]; 366 } 367 else { 368 enemy_value = prefix[(size)*(leader_idx)-1] ^ ((leader_idx-1) == 0 ? 0 : prefix[(size)*(leader_idx-1)-1]); 369 } 370 if (leader_value < enemy_value || (leader_value == enemy_value && leader_idx % 2 == 1)) { 371 curr_position += size; 372 } 373 } 374 375 cout << curr_position << "\n"; 376 } 377 } 378 } 379 ``` 380 381 [2185G - Mixing MEXes](/contest/2185/problem/G "Codeforces Round 1074 (Div. 4)") 382 383 **Hint 1** 384 385 The only time adding an element changes the MEX of an array is if the added element is equal to the MEX of the array. 386 387 **Hint 2** 388 389 For a given element, the element is removed $n - 1$ times, and the element is added to another array $n - 1$ times. 390 391 **Hint 3** 392 393 We can treat removing an element from the array and adding it to another array as two separate interactions. 394 395 **Editorial** 396 397 Tutorial is loading... 398 399 **Code** 400 401 ``` 402 #include <bits/stdc++.h> 403 using namespace std; 404 405 #define ll long long 406 407 int main() { 408 int t; 409 cin >> t; 410 while (t--) { 411 int n; 412 cin >> n; 413 414 vector<int> lengths(n); 415 vector<vector<int>> arrays(n); 416 map<int, int> count; 417 for (int i = 0; i < n; i++) { 418 int length; 419 cin >> length; 420 lengths[i] = length; 421 arrays[i] = vector<int>(lengths[i]); 422 for (auto &x: arrays[i]) { 423 cin >> x; 424 count[x]++; 425 } 426 sort(arrays[i].begin(), arrays[i].end()); 427 } 428 429 int mex_sum = 0; 430 vector<int> mexes(n); 431 vector<int> second_mexes(n); 432 433 // Calculate mex and second mex for each array 434 for (int i = 0; i < n; i++) { 435 int current_mex = 0; 436 for (int j = 0; j < lengths[i]; j++) { 437 if (arrays[i][j] > current_mex) break; 438 if (arrays[i][j] == current_mex) current_mex++; 439 } 440 int second_mex = current_mex+1; 441 for (int j = 0; j < lengths[i]; j++) { 442 if (arrays[i][j] > second_mex) break; 443 if (arrays[i][j] == second_mex) second_mex++; 444 } 445 mexes[i] = current_mex; 446 second_mexes[i] = second_mex; 447 mex_sum += current_mex; 448 } 449 450 ll total = 0; 451 // Calculate removals 452 for (int i = 0; i < n; i++) { 453 for (int j = 0; j < lengths[i]; j++) { 454 ll org = total; 455 bool is_alone = (j == 0 || arrays[i][j-1] != arrays[i][j]) && (j == lengths[i]-1 || arrays[i][j+1] != arrays[i][j]); 456 if (is_alone && arrays[i][j] < mexes[i]) total += ((ll)(mex_sum-mexes[i]+arrays[i][j]))*(n-1); 457 else total += (ll)(mex_sum) * (n-1); 458 } 459 } 460 // Calculate additions 461 for (int i = 0; i < n; i++) { 462 total += (ll)(count[mexes[i]])*(second_mexes[i]-mexes[i]); 463 } 464 465 cout << total << "\n"; 466 } 467 468 } 469 ``` 470 471 [2185H - BattleCows 2](/contest/2185/problem/H "Codeforces Round 1074 (Div. 4)") 472 473 **Hint 1** 474 475 I had originally proposed this problem with a subtask to solve for Cow 0 only, try that. 476 477 **Hint 1.1** 478 479 Trivially, a cow must cheat when it loses a match, and a cow shouldn't cheat if it can win a match 480 481 **Hint 1.2** 482 483 Simulate the process for Cow 0 starting at position 0. If Cow 0 wins all of its matches in under $k$ cheats, Cow 0 can win all of its matches. 484 485 **Hint 1.3** 486 487 If we simulate the process for Cow 0 starting at position 0, no matter which position Cow 0 starts, after $k$ matches, if Cow 0 has already had a match, its skill value would be the same no matter in which position it initially started. 488 489 **Hint 1.4** 490 491 A cow can always win its first match using at most one hint, and so if there's another earlier position where Cow 0 had already used a cheat and won all of its matches, Cow 0 can also win in this new position. 492 493 **Hint 1.5** 494 495 Going back to the second hint, if Cow 0 used over $k$ cheats (let's call the number of cheats used $m$), Cow 0 can only win if its first match's match number is greater than or equal to the round number where Cow 0 at position 0 has used its $m - k$-th cheat. 496 497 **Hint 1.6** 498 499 Now we're down to the case we used exactly $k$ cheats. Let's denote the last position where Cow 0 can win its first match without cheating as $b$ (which is the first index where the sum of all the skill levels of the cows before is less than the skill level as cow 0). Using hint 3, this means that all the positions less than or equal to $b$ are also winning positions. 500 501 **Hint 1.7** 502 503 Finally, using hint 4, if Cow 0's first match is the same match or after the match where Cow 0 at position 0 could used its first cheat, cow 0 can win at that new position. Note that if $k = 0$, we can ignore this step. 504 505 **Hint 2** 506 507 We can simulate each cow as if it started as position 0. 508 509 **Hint 3** 510 511 A cow only needs cheat at most $\log(max(a_i))$ times, since its skill level is (at least) double after each cheat. 512 513 **Hint 4** 514 515 Prefix sums, binary search, and helper methods are your friend. 516 517 **Editorial** 518 519 Tutorial is loading... 520 521 **Code** 522 523 ``` 524 #include <bits/stdc++.h> 525 using namespace std; 526 527 #define ll long long 528 529 int main() { 530 int t; 531 cin >> t; 532 533 int test_num = 0; 534 while (t--) { 535 int n, k; 536 cin >> n >> k; 537 test_num++; 538 vector<ll> skill_levels(n); for (auto &x: skill_levels) cin >> x; 539 540 vector<ll> prefix(n); prefix[0] = skill_levels[0]; 541 for (int i = 1; i < n; i++) prefix[i] = skill_levels[i] + prefix[i-1]; 542 543 auto sum_without_index = [&](int l, int r, int i) { 544 if (r < l || r < 0 || l < 0) return 0ll; 545 ll val = prefix[r] - (l == 0 ? 0 : prefix[l-1]); 546 if (r < i) return val; 547 if (l > i) { 548 r++; 549 l++; 550 return prefix[r] - (l == 0 ? 0 : prefix[l-1]); 551 } 552 else { 553 r++; 554 return prefix[r] - (l == 0 ? 0 : prefix[l-1]) - skill_levels[i]; 555 } 556 557 }; 558 559 auto bs_for_prefix = [&](ll target, int ignoring) { 560 int lo = 0; 561 int hi = n - 1; 562 while (lo <= hi) { 563 int mid = lo + (hi - lo) / 2; 564 if (mid == 0 || sum_without_index(0, mid-1, ignoring) < target) { 565 lo = mid + 1; 566 } 567 else { 568 hi = mid - 1; 569 } 570 } 571 return hi; 572 }; 573 574 vector<int> answer(n); 575 for (int i = 0; i < n; i++) { 576 int last_starting_position = bs_for_prefix(skill_levels[i], i); 577 578 vector<int> bad_positions; 579 int pos = -1; 580 581 while (true) { 582 ll value = sum_without_index(0, pos, i) + skill_levels[i]; 583 584 ll pos_of_bad = bs_for_prefix(value * 2 + 1 - skill_levels[i], i); 585 586 if (pos_of_bad >= n - 1) break; 587 588 value = sum_without_index(0, pos_of_bad-1, i) + skill_levels[i]; 589 590 bool bad_position = sum_without_index(pos_of_bad, pos_of_bad, i) > value; 591 592 if (bad_position) { 593 bad_positions.push_back(pos_of_bad + 1); 594 } 595 pos = pos_of_bad; 596 } 597 598 if (k == 0) { 599 if (bad_positions.size() == 0) answer[i] += last_starting_position + 1; 600 } 601 else if (bad_positions.size() > k) { 602 answer[i] += n - bad_positions[bad_positions.size() - k]; 603 } 604 else if (bad_positions.size() < k) { 605 answer[i] += n; 606 } 607 else { 608 answer[i] += min(n, (last_starting_position + 1) + (n - bad_positions[0])); 609 } 610 } 611 612 for (auto &x: answer) cout << x << " "; 613 cout << "\n"; 614 615 } 616 } 617 ```