codeforces-scrape

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

2259.md (13137B)


      1 Source: https://codeforces.com/blog/entry/156457
      2 
      3 Thank y'all so much for participating!
      4 
      5 [2259A - Школа языка Му](/contest/2259/problem/A "Codeforces Round 1119 (Div. 3)")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 
     17 int main() {
     18     int t;
     19     cin >> t;
     20 
     21     while (t--) {
     22         int n, k;
     23         cin >> n >> k;
     24 
     25         string s;
     26         cin >> s;
     27 
     28         int ans = 0;
     29         for (int i = 0; i < n / k; i++) {
     30             bool has_non_nhoj_farm = false;
     31             for (int j = i * k; j < (i + 1) * k; j++) {
     32                 if (s[j] == '0') has_non_nhoj_farm = true;
     33             }
     34             ans += !has_non_nhoj_farm;
     35         }
     36 
     37         cout << ans << "\n";
     38     }
     39 }
     40 ```
     41 
     42 **Difficulty**
     43 
     44 Too hard
     45 
     46 A bit on the harder side
     47 
     48 Good difficulty
     49 
     50 Easy
     51 
     52 Too easy
     53 
     54 **Quality**
     55 
     56 Amazing
     57 
     58 Good
     59 
     60 So-so
     61 
     62 Bad
     63 
     64 Awful
     65 
     66 [2259B - Minus Two](/contest/2259/problem/B "Codeforces Round 1119 (Div. 3)")
     67 
     68 **Hint 1**
     69 
     70 When comparing two numbers that are initially not equal, the only way they can become equal after some number of operations is if at least one of them has an operation performed on it when it is $ \lt 2$.
     71 
     72 **Hint 2**
     73 
     74 If two elements are equal at some point, they'll be equal no matter how many more operations are performed. Therefore, it suffices to look at the end behavior of each element.
     75 
     76 **Solution**
     77 
     78 Tutorial is loading...
     79 
     80 **Code**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 using namespace std;
     85  
     86 int main() {
     87     int t;
     88     cin >> t;
     89     
     90     while (t--) {
     91         int n;
     92         cin >> n;
     93         
     94         vector<int> vec(n); for (auto &x: vec) cin >> x;
     95         
     96         int mod_4[] {0, 0, 0, 0};
     97         for (auto &x: vec) mod_4[x%4]++;
     98         cout << max({mod_4[0], mod_4[2], mod_4[1] + mod_4[3]}) << "\n";
     99     }
    100 }
    101 ```
    102 
    103 **Difficulty**
    104 
    105 Too hard
    106 
    107 A bit on the harder side
    108 
    109 Good difficulty
    110 
    111 Easy
    112 
    113 Too easy
    114 
    115 **Quality**
    116 
    117 Amazing
    118 
    119 Good
    120 
    121 So-so
    122 
    123 Bad
    124 
    125 Awful
    126 
    127 [2259C - 101](/contest/2259/problem/C "Codeforces Round 1119 (Div. 3)")
    128 
    129 **Hint 1**
    130 
    131 If a $-1$ is in between two $1$s, it would only hurt the answer to make it a $1$.
    132 
    133 **Hint 2**
    134 
    135 If a $-1$ is not in between two $1$ s, the $-1$ would only be included in a subarray satisfying the conditions if it was an endpoint.
    136 
    137 **Solution**
    138 
    139 Tutorial is loading...
    140 
    141 **Code**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145 using namespace std;
    146  
    147 int main() {
    148     int t;
    149     cin >> t;
    150     
    151     while (t--) {
    152         int n;
    153         cin >> n;
    154         
    155         vector<int> vec(n); for (auto &x: vec) cin >> x;
    156         
    157         for (int i = 0; i < n; i++) {
    158             if (vec[i] == -1) vec[i] = 1;
    159             if (vec[i] == 1) break;
    160         }
    161         
    162         for (int i = n-1; i >= 0; i--) {
    163             if (vec[i] == -1) vec[i] = 1;
    164             if (vec[i] == 1) break;
    165         }
    166         
    167         
    168         for (auto &x: vec) cout << max(x, 0) << " ";
    169         cout << "\n";
    170     }
    171 }
    172 ```
    173 
    174 **Difficulty**
    175 
    176 Too hard
    177 
    178 A bit on the harder side
    179 
    180 Good difficulty
    181 
    182 Easy
    183 
    184 Too easy
    185 
    186 **Quality**
    187 
    188 Amazing
    189 
    190 Good
    191 
    192 So-so
    193 
    194 Bad
    195 
    196 Awful
    197 
    198 [2259D - MEX мультимножеств](/contest/2259/problem/D "Codeforces Round 1119 (Div. 3)")
    199 
    200 **Hint 1**
    201 
    202 If there is only one $0$ in the array, then exactly one set will have a mex greater than zero
    203 
    204 **Hint 2**
    205 
    206 $MEX(A) = MEX(B), MEX(C) = 0$ satisfies the constraints.
    207 
    208 **Solution**
    209 
    210 Tutorial is loading...
    211 
    212 **Code**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 using namespace std;
    217  
    218 int main() {
    219     int t;
    220     cin >> t;
    221  
    222     while (t--) {
    223         int n;
    224         cin >> n;
    225  
    226         vector<int> vec(n); for (auto &x: vec) cin >> x;
    227         if (count(vec.begin(), vec.end(), 0) == 1) {
    228             cout << "NO\n";
    229             continue;
    230         }
    231         cout << "YES\n";
    232         bool seen_zero = false;
    233         for (int i = 0; i < n; i++) {
    234             if (vec[i] != 0) cout << 'A';
    235             else if (seen_zero) cout << 'B';
    236             else {
    237                 seen_zero = true;
    238                 cout << 'C';
    239             }
    240         }
    241         cout << "\n";
    242     }
    243 }
    244 ```
    245 
    246 **Difficulty**
    247 
    248 Too hard
    249 
    250 A bit on the harder side
    251 
    252 Good difficulty
    253 
    254 Easy
    255 
    256 Too easy
    257 
    258 **Quality**
    259 
    260 Amazing
    261 
    262 Good
    263 
    264 So-so
    265 
    266 Bad
    267 
    268 Awful
    269 
    270 [2259E - Разрушение карты сокровищ (конструктивная версия)](/contest/2259/problem/E "Codeforces Round 1119 (Div. 3)")
    271 
    272 **Hint 1**
    273 
    274 If an element $x$ at index $i$ is not equal to $-1$, there must be a treasure at either island $i + x$ or $i - x$
    275 
    276 **Hint 2**
    277 
    278 If an element $x$ at index $i$ is not equal to $-1$, there must no treasures in the exclusive range of indices ($i + x$, $i - x$)
    279 
    280 **Solution**
    281 
    282 Tutorial is loading...
    283 
    284 **Code**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 using namespace std;
    289 #define ll long long
    290  
    291 int main() {
    292     int t;
    293     cin >> t;
    294  
    295  
    296     while (t--) {
    297         int n;
    298         cin >> n;
    299  
    300         vector<int> vec(n); for (auto &x: vec) cin >> x;
    301  
    302         vector<int> diff(n+1);
    303         for (int i = 0; i < n; i++) {
    304             if (vec[i] > 0) {
    305                 diff[max(0, i-vec[i]+1)]++; 
    306                 diff[min(n, i+vec[i])]--; 
    307             }
    308         }
    309         vector<bool> restricted(n);
    310         int curr_count = 0;
    311         for (int i = 0; i < n; i++) {
    312             curr_count += diff[i];
    313             restricted[i] = curr_count > 0;
    314         }
    315         bool possible = true;
    316         for (int i = 0; i < n && possible; i++) {
    317             if (vec[i] >= 0) {
    318                 if (i - vec[i] >= 0 && !restricted[i - vec[i]]) continue;
    319                 if (i + vec[i] < n && !restricted[i + vec[i]]) continue;
    320                 possible = false;
    321             }
    322         }
    323  
    324         if (!possible) cout << -1 << "\n";
    325         else {
    326             for (auto x: restricted) cout << !x;
    327             cout << "\n";
    328         } 
    329     }
    330 }
    331 ```
    332 
    333 **Difficulty**
    334 
    335 Too hard
    336 
    337 A bit on the harder side
    338 
    339 Good difficulty
    340 
    341 Easy
    342 
    343 Too easy
    344 
    345 **Quality**
    346 
    347 Amazing
    348 
    349 Good
    350 
    351 So-so
    352 
    353 Bad
    354 
    355 Awful
    356 
    357 [2259F - Инверсии бинарной пузырьковой сортировки](/contest/2259/problem/F "Codeforces Round 1119 (Div. 3)")
    358 
    359 **Hint 1**
    360 
    361 Look at performing some bubbles and reverse bubbles on small arrays. How many elements are moved?
    362 
    363 **Hint 2**
    364 
    365 A bubble will result is the leftmost 1 being moved all the way to the right. Similarly, a reverse bubble will result in the rightmost 0 being moved all the way to the left.
    366 
    367 **Hint 3**
    368 
    369 Since prefix zeroes and suffix ones don't matter, if we continuously remove them, then a bubble removes the last element of the array and a reverse bubble removes the first element of the array. Is there a way to remove the first and last elements of an array in constant time?
    370 
    371 **Solution**
    372 
    373 Tutorial is loading...
    374 
    375 **Code**
    376 
    377 ```
    378 #include <bits/stdc++.h>
    379 using namespace std;
    380  
    381 #define ll long long
    382 int main() {
    383     int t;
    384     cin >> t;
    385  
    386     while (t--) {
    387         int n;
    388         cin >> n;
    389  
    390         vector<int> vec(n); for (auto &x: vec) cin >> x;
    391         string s;
    392         cin >> s;
    393  
    394         ll inversions = 0;
    395         int cnt_ones = 0;
    396         for (int i = 0; i < n; i++) {
    397             cnt_ones += vec[i];
    398             if (vec[i] == 0) inversions += cnt_ones;
    399         }
    400         cout << inversions << " ";
    401         
    402         deque<int> dq;
    403         for (auto &x: vec) dq.push_back(x);
    404         int cnt_zeroes = count(vec.begin(), vec.end(), 0);
    405         for (int i = 0; i < n; i++) {
    406             while (dq.size() > 0 && dq.front() == 0) {
    407                 dq.pop_front();
    408                 cnt_zeroes--;
    409             }
    410             while (dq.size() > 0 && dq.back() == 1) dq.pop_back();
    411             if (dq.size() == 0) {
    412                 cout << 0 << " ";
    413                 continue;
    414             }
    415             if (s[i] == '0') {
    416                 inversions -= (dq.size() - cnt_zeroes);
    417                 dq.pop_back();
    418                 cnt_zeroes--;
    419             }
    420             else {
    421                 inversions -= cnt_zeroes;
    422                 dq.pop_front();
    423             }
    424             cout << inversions << " ";
    425         }
    426         cout << "\n";
    427     }
    428 }
    429 ```
    430 
    431 **Difficulty**
    432 
    433 Too hard
    434 
    435 A bit on the harder side
    436 
    437 Good difficulty
    438 
    439 Easy
    440 
    441 Too easy
    442 
    443 **Quality**
    444 
    445 Amazing
    446 
    447 Good
    448 
    449 So-so
    450 
    451 Bad
    452 
    453 Awful
    454 
    455 [2259G - Убрали индекс](/contest/2259/problem/G "Codeforces Round 1119 (Div. 3)")
    456 
    457 **Hint 1**
    458 
    459 Ignoring indexes 1 and $n$, if we remove index $i$, if we perform an operation on index $j$, all elements between $[i, j]$ will also have an operation performed on them.
    460 
    461 **Hint 2**
    462 
    463 If we remove index $i$, and we have to reduce the element at index $i+1$, $i+2$, etc, what will we subtract it to?
    464 
    465 **Solution**
    466 
    467 Tutorial is loading...
    468 
    469 **Code**
    470 
    471 ```
    472 #include <bits/stdc++.h>
    473 using namespace std;
    474  
    475 #define ll long long
    476 int main() {
    477     int t;
    478     cin >> t;
    479  
    480     while (t--) {
    481         ll n, k;
    482         cin >> n >> k;
    483  
    484         vector<ll> vec(n); for (auto &x: vec) cin >> x;
    485         vector<ll> vec_2(n); for (int i = 0; i < n; i++) vec_2[i] = vec[i] - i * k;
    486  
    487         vector<ll> prefix(n); prefix[0] = vec[0];
    488         for (int i = 1; i < n; i++) prefix[i] = prefix[i-1] + vec[i];
    489  
    490         vector<ll> ans(n);
    491         for (int i = 1; i < n-1; i++) {
    492             int lo = i+1;
    493             int hi = n-1;
    494             while (lo <= hi) {
    495                 int mid = lo + (hi - lo) / 2;
    496                 if (vec_2[mid] <= (vec[i-1] - i*k)) hi = mid - 1;
    497                 else lo = mid + 1;
    498             }
    499             
    500             ll num_needed = (lo - i - 1);
    501             ans[i] = (prefix[num_needed + i] - prefix[i]) - (k * (num_needed * (num_needed + 1))/2) - vec[i-1] * num_needed;
    502         }
    503         for (auto &x: ans) cout << x << " ";
    504         cout << "\n";
    505     }
    506 }
    507 ```
    508 
    509 **Difficulty**
    510 
    511 Too hard
    512 
    513 A bit on the harder side
    514 
    515 Good difficulty
    516 
    517 Easy
    518 
    519 Too easy
    520 
    521 **Quality**
    522 
    523 Amazing
    524 
    525 Good
    526 
    527 So-so
    528 
    529 Bad
    530 
    531 Awful
    532 
    533 [2259H - Разрушение карты сокровищ (версия подсчёта)](/contest/2259/problem/H "Codeforces Round 1119 (Div. 3)")
    534 
    535 Read the solution to problem E first
    536 
    537 **Hint 1**
    538 
    539 Let's consider all locations that we have not restricted: we can separate them into 3 categories: the position is forced to be a treasure, the position has no undestroyed that depend on it, and all other positions.
    540 
    541 **Hint 2**
    542 
    543 The islands that are considered "non-restricted" form a chain of locations, with each non-restricted chain having a treasure between them. What must be true of the locations in this chain such that no condition is violated?
    544 
    545 **Hint 3**
    546 
    547 For every pair of adjacent locations, there must be at least one treasure at one of those locations.
    548 
    549 **Solution**
    550 
    551 Tutorial is loading...
    552 
    553 **Code**
    554 
    555 ```
    556 #include <bits/stdc++.h>
    557 using namespace std;
    558 #define ll long long
    559  
    560 const ll MOD = 1000000007;
    561 const int MAX_N = 200055;
    562 int main() {
    563     int t;
    564     cin >> t;
    565  
    566  
    567     vector<ll> fibo(MAX_N);
    568     fibo[1] = 1;
    569     fibo[2] = 1;
    570     for (int i = 3; i < MAX_N; i++) {
    571         fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD;
    572     }
    573  
    574     while (t--) {
    575         int n;
    576         cin >> n;
    577  
    578         vector<int> vec(n); for (auto &x: vec) cin >> x;
    579  
    580         vector<int> diff(n+1);
    581         for (int i = 0; i < n; i++) {
    582             if (vec[i] > 0) {
    583                 diff[max(0, i-vec[i]+1)]++; 
    584                 diff[min(n, i+vec[i])]--; 
    585             }
    586         }
    587         
    588         vector<bool> restricted(n);
    589         vector<bool> forced(n);
    590         vector<int> non_required;
    591         int curr_count = 0;
    592         for (int i = 0; i < n; i++) {
    593             curr_count += diff[i];
    594             restricted[i] = curr_count > 0;
    595         }
    596  
    597         bool possible = true;
    598         for (int i = 0; i < n; i++) {
    599             if (vec[i] != -1) {
    600                 int cnt = 0;
    601                 cnt += (i - vec[i] >= 0 && !restricted[i - vec[i]]); 
    602                 cnt += (i + vec[i] < n && !restricted[i + vec[i]]);
    603                 if (cnt == 0) { possible = false;}
    604                 if (cnt == 1 || vec[i] == 0) {
    605                     if (i + vec[i] < n) forced[i + vec[i]] = true;
    606                     if (i - vec[i] >= 0) forced[i - vec[i]] = true;
    607                 }
    608             }
    609         }
    610         for (int i = 0; i < n; i++) {
    611             if (!restricted[i] && !forced[i]) non_required.push_back(i);
    612         }
    613         if (!possible) {
    614             cout << 0 << "\n";
    615             continue;
    616         }
    617  
    618         ll total = 1;
    619         int chain_len = 1;
    620         for (int i = 0; i < non_required.size(); i++) {
    621             bool cond1 = i == non_required.size() - 1 || vec[(non_required[i] + non_required[i+1])/2] == (non_required[i+1] - non_required[i])/2;
    622             bool cond2 = i == non_required.size() - 1 || (non_required[i+1] - non_required[i]) % 2 == 0;
    623             //if (i != 1) cout << (non_required[i+1] - non_required[i]) << "\n";
    624             if (i == non_required.size() - 1 || !cond1 || !cond2) {
    625                 //cout << chain_len << "\n";
    626                 total *= fibo[chain_len+2];
    627                 total %= MOD;
    628                 chain_len = 1;
    629             }
    630             else chain_len++;
    631         }
    632         if (count(vec.begin(), vec.end(), -1) == n) {
    633             total = (total + MOD - 1) % MOD;
    634         }
    635         cout << total << "\n";
    636     }
    637 }
    638 ```
    639 
    640 **Difficulty**
    641 
    642 Too hard
    643 
    644 A bit on the harder side
    645 
    646 Good difficulty
    647 
    648 Easy
    649 
    650 Too easy
    651 
    652 **Quality**
    653 
    654 Amazing
    655 
    656 Good
    657 
    658 So-so
    659 
    660 Bad
    661 
    662 Awful