codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```