codeforces-scrape

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

2093.md (11629B)


      1 Source: https://codeforces.com/blog/entry/141434
      2 
      3 We hope you enjoyed the contest! Thank you for participating! This is our first official round on Codeforces, so we would be happy to hear your feedback in the comments and in the mini-survey below.
      4 
      5 **How did you like the contest?**
      6 
      7 * Excellent:
      8 * Good:
      9 * Average:
     10 * Bad:
     11 * Terrible:
     12 
     13 **Which problems did you like (you can choose multiple)?**
     14 
     15 * A:
     16 * B:
     17 * C:
     18 * D:
     19 * E:
     20 * F:
     21 * G:
     22 
     23 **Which problems did you not like (you can choose multiple)?**
     24 
     25 * A:
     26 * B:
     27 * C:
     28 * D:
     29 * E:
     30 * F:
     31 * G:
     32 
     33 [2093A - Ideal Generator](/contest/2093/problem/A "Codeforces Round 1016 (Div. 3)")
     34 
     35 Идея: [EzikBro](/profile/EzikBro "Master EzikBro")
     36 
     37 **Hint 1**
     38 
     39 Prove that the number $2$ is not an ideal generator. What other numbers are not ideal generators for the same reason?
     40 
     41 **Hint 2**
     42 
     43 Prove that the number $3$ is an ideal generator. What is the difference from the previous case?
     44 
     45 **Editorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53  
     54 using namespace std;
     55  
     56 int main() {
     57     int t;
     58     cin >> t;
     59  
     60     while (t--) {
     61         int n;
     62         cin >> n;
     63         if (n % 2 == 1) {
     64             cout << "YES\n";
     65         } else {
     66             cout << "NO\n";
     67         }
     68     }
     69  
     70     return 0;
     71 }
     72 ```
     73 
     74 [2093B - Expensive Number](/contest/2093/problem/B "Codeforces Round 1016 (Div. 3)")
     75 
     76 Идея: [gravitsapa](/profile/gravitsapa "International Master gravitsapa")
     77 
     78 **Hint 1**
     79 
     80 What is the minimum cost that can be achieved?
     81 
     82 **Hint 2**
     83 
     84 How many non-zero digits should be in the remaining number for the cost to be minimal?
     85 
     86 **Hint 3**
     87 
     88 How can we ensure that the number has as many leading zeros as possible?
     89 
     90 **Editorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98  
     99 using namespace std;
    100  
    101 int main() {
    102     int t;
    103     cin >> t;
    104     while (t--) {
    105         string s;
    106         cin >> s;
    107         int n = s.size();
    108         bool met_positive = false;
    109         int cnt_zero = 0;
    110         
    111         for (auto i = n - 1; i >= 0; --i) {
    112             if (s[i] != '0') {
    113                 met_positive = true;
    114             } else if (met_positive) {
    115                 cnt_zero++;
    116             }
    117         }
    118         
    119         cout << n - (cnt_zero + 1) << '\n';
    120     }
    121     return 0;
    122 }
    123 ```
    124 
    125 [2093C - Simple Repetition](/contest/2093/problem/C "Codeforces Round 1016 (Div. 3)")
    126 
    127 Идея: [pskobx](/profile/pskobx "Candidate Master pskobx")
    128 
    129 **Hint 1**
    130 
    131 $y$ is always divisible by $x$.
    132 
    133 **Hint 2**
    134 
    135 What happens if $k \geq 2$?
    136 
    137 **Hint 3**
    138 
    139 If $k \geq 2$ and $x \geq 2$, then $y$ will never be prime. Are there any edge cases with $k = 1$ or $x = 1$?
    140 
    141 **Editorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149  
    150 using namespace std;
    151  
    152 bool is_prime(int x) {
    153     if (x <= 1) {
    154         return false;
    155     }
    156     for (int i = 2; i * i <= x; i++) {
    157         if (x % i == 0) {
    158             return false;
    159         }
    160     }
    161     return true;
    162 }
    163  
    164 void solve() {
    165     int x, k;
    166     cin >> x >> k;
    167     if (k > 1 && x > 1) {
    168         cout << "NO";
    169     } else if (k == 1) {
    170         cout << (is_prime(x) ? "YES" : "NO");
    171     } else {
    172         cout << ((k == 2) ? "YES" : "NO");
    173     }
    174 }
    175  
    176 int main() {
    177     int tests;
    178     cin >> tests;
    179     while (tests--) {
    180         solve();
    181         cout << '\n';
    182     }
    183 }
    184 ```
    185 
    186 [2093D - Skibidi Table](/contest/2093/problem/D "Codeforces Round 1016 (Div. 3)")
    187 
    188 Идея: [fstilus](/profile/fstilus "Expert fstilus")
    189 
    190 **Hint**
    191 
    192 How does the answer change when $n$ is decreased?
    193 
    194 **Editorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202  
    203 using namespace std;
    204  
    205 int main() {
    206     int t;
    207     cin >> t;
    208     
    209     while (t--) {
    210         int n, q;
    211         cin >> n >> q;
    212         
    213         while (q--) {
    214             string type;
    215             cin >> type;
    216             
    217             if (type == "->") {
    218                 int x, y;
    219                 cin >> x >> y;
    220                 x--, y--;
    221                 
    222                 long long num = 0;
    223                 for (int i = n - 1; i >= 0; --i) {
    224                     int cur = 1 << i;
    225                     if (!(x & cur) && !(y & cur))
    226                         num ^= 0ll << (2 * i);
    227                     if ((x & cur) && (y & cur))
    228                         num ^= 1ll << (2 * i);
    229                     if ((x & cur) && !(y & cur))
    230                         num ^= 2ll << (2 * i);
    231                     if (!(x & cur) && (y & cur))
    232                         num ^= 3ll << (2 * i);
    233                 }
    234                 cout << num + 1 << '\n';
    235             }
    236             else {
    237                 long long num;
    238                 cin >> num;
    239                 num--;
    240                 
    241                 int x = 0, y = 0;
    242                 for (int i = n - 1; i >= 0; --i) {
    243                     long long cur = 3ll << (2 * i);
    244                     if ((num & cur) >> (2 * i) == 0)
    245                         x ^= 0 << i, y ^= 0 << i;
    246                     if ((num & cur) >> (2 * i) == 1)
    247                         x ^= 1 << i, y ^= 1 << i;
    248                     if ((num & cur) >> (2 * i) == 2)
    249                         x ^= 1 << i, y ^= 0 << i;
    250                     if ((num & cur) >> (2 * i) == 3)
    251                         x ^= 0 << i, y ^= 1 << i;
    252                 }
    253                 cout << x + 1 << ' ' << y + 1 << '\n';
    254             }
    255         }
    256     }
    257     
    258     return 0;
    259 }
    260 ```
    261 
    262 [2093E - Min Max MEX](/contest/2093/problem/E "Codeforces Round 1016 (Div. 3)")
    263 
    264 Идея: [Boodoochai](/profile/Boodoochai "Expert Boodoochai")
    265 
    266 **Hint 1**
    267 
    268 How to check if a solution exists for a fixed $x$?
    269 
    270 **Hint 2**
    271 
    272 We can use binary search.
    273 
    274 **Editorial**
    275 
    276 Tutorial is loading...
    277 
    278 **Solution**
    279 
    280 ```
    281 #include <bits/stdc++.h>
    282 
    283 using namespace std;
    284 
    285 vector<int> nums(2e5 + 5, 0);
    286 
    287 bool check(vector<int>& v, int k, int m)
    288 {
    289     int cnt = 0;
    290     int cur_mex = 0;
    291     for (int i = 0; i < v.size(); i++) {
    292         if (v[i] <= v.size() + 1) {
    293             nums[v[i]] = 1;
    294         }
    295         while (nums[cur_mex]) {
    296             cur_mex++;
    297         }
    298         if (cur_mex >= m) {
    299             cnt++;
    300             for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) {
    301                 nums[j] = 0;
    302             }
    303             cur_mex = 0;
    304         }
    305     }
    306     for (int j = 0; j < v.size() + 2; j++) {
    307         nums[j] = 0;
    308     }
    309     return cnt >= k;
    310 }
    311 
    312 void solve()
    313 {
    314     int n, k;
    315     cin >> n >> k;
    316 
    317     vector<int> v(n);
    318     for (int i = 0; i < n; i++) {
    319         cin >> v[i];
    320     }
    321 
    322     int l = 0;
    323     int r = 1e9;
    324     while (r - l > 1) {
    325         int m = (r + l) / 2;
    326         if (check(v, k, m)) {
    327             l = m;
    328         } else {
    329             r = m;
    330         }
    331     }
    332 
    333     cout << l << '\n';
    334 }
    335 
    336 signed main()
    337 {
    338     int t;
    339     cin >> t;
    340     for (int i = 0; i < t; i++) {
    341         solve();
    342     }
    343     return 0;
    344 }
    345 ```
    346 
    347 [2093F - Hackers and Neural Networks](/contest/2093/problem/F "Codeforces Round 1016 (Div. 3)")
    348 
    349 Идея: [_icy_](/profile/_icy_ "Expert _icy_")
    350 
    351 **Hint 1**
    352 
    353 We need to ensure that we construct the array $a$. Therefore, when interacting with the neural network, we should consider the worst-case scenario.
    354 
    355 **Hint 2**
    356 
    357 Read the previous hint. How many operations of the first type applied to the $i$-th neural network do we need to obtain at least one *correct* word (i.e., one such that $b_{i, j} = a_j$)?
    358 
    359 **Answer**
    360 
    361 If we have obtained at least one *correct* word from the neural network, then, since we are considering the worst-case scenario, it has already placed all *incorrect* words in the array $c$.
    362 
    363 **Hint 3**
    364 
    365 Read the previous hint and its answer. Which neural network is optimal to start with? How many blanks will there be in the array $c$ after interacting with this neural network?
    366 
    367 **Answer**
    368 
    369 It is optimal to start with the neural network that has the most *correct* words. There will be no blanks in the array $c$.
    370 
    371 **Hint 4**
    372 
    373 There are currently no blanks in the array $c$, but there are *incorrect* words in some positions. How many operations are needed to replace one *incorrect* word with a *correct* one?
    374 
    375 **Editorial**
    376 
    377 Tutorial is loading...
    378 
    379 **Solution**
    380 
    381 ```
    382 #include <bits/stdc++.h>
    383  
    384 using namespace std;
    385  
    386 void solve() {
    387     int n, m;
    388     cin >> n >> m;
    389     vector<string> a(n);
    390     for (auto &i: a) {
    391         cin >> i;
    392     }
    393     vector<vector<string>> b(m, vector<string>(n));
    394     for (auto &ar: b) {
    395         for (auto &s: ar) {
    396             cin >> s;
    397         }
    398     }
    399     vector<bool> exists(n);
    400     int x = 0;
    401     for (int i = 0; i < m; i++) {
    402         int cnt = 0;
    403         for (int j = 0; j < n; j++) {
    404             if (a[j] == b[i][j]) {
    405                 cnt++;
    406                 exists[j] = true;
    407             }
    408         }
    409         x = max(x, cnt);
    410     }
    411     if (all_of(exists.begin(), exists.end(), identity())) {
    412         cout << n + 2 * (n - x) << "\n";
    413     } else {
    414         cout << "-1\n";
    415     }
    416 }
    417  
    418 int main() {
    419     int t;
    420     cin >> t;
    421     while (t--) {
    422         solve();
    423     }
    424     return 0;
    425 }
    426 ```
    427 
    428 [2093G - Shorten the Array](/contest/2093/problem/G "Codeforces Round 1016 (Div. 3)")
    429 
    430 Идея: [EzikBro](/profile/EzikBro "Master EzikBro")
    431 
    432 **Hint 1**
    433 
    434 Let the shortest segment have boundaries $l$ and $r$. What can be said about the indices $i$ and $j$ for which the maximum value of the expression $a_i \oplus a_j$ is achieved?
    435 
    436 **Hint 2**
    437 
    438 The operation $x \oplus y$ on int32 numbers can be represented as the XOR of two binary strings of length $32$. What can be said about the comparison of numbers? In what case does the expression $x \oplus y = z$ hold? And $x \oplus y \gt z$?
    439 
    440 **Hint 3**
    441 
    442 How can we use a trie on binary strings to find the nearest index $j$ such that $a_i \oplus a_j = k$?
    443 
    444 **Editorial**
    445 
    446 Tutorial is loading...
    447 
    448 **Solution**
    449 
    450 ```
    451 #include <bits/stdc++.h>
    452  
    453 using namespace std;
    454  
    455 const int LOG_X = 29;
    456  
    457 struct node {
    458     int children[2] { -1, -1 };
    459     int last = -1;
    460 };
    461  
    462 int find(const vector<node>& trie, int value, int border) {
    463     int res = -1;
    464     int current = 0;
    465     bool ok = true;
    466     for (int position = LOG_X; ok && position >= 0; position--) {
    467         int x_bit = (value >> position) & 1;
    468         int k_bit = (border >> position) & 1;
    469         auto& children = trie[current].children;
    470         if (k_bit == 1) {
    471             if (children[x_bit ^ 1] != -1) {
    472                 current = children[x_bit ^ 1];
    473             } else {
    474                 ok = false;
    475             }
    476         } else {
    477             if (children[x_bit ^ 1] != -1) {
    478                 res = max(res, trie[children[x_bit ^ 1]].last);
    479             }
    480             if (children[x_bit] != -1) {
    481                 current = children[x_bit];
    482             } else {
    483                 ok = false;
    484             }
    485         }
    486     }
    487     if (ok) {
    488         res = max(res, trie[current].last);
    489     }
    490     return res;
    491 }
    492  
    493 void add(vector<node>& trie, int value, int index) {
    494     int current = 0;
    495     trie[current].last = max(trie[current].last, index);
    496     for (int position = LOG_X; position >= 0; position--) {
    497         int x_bit = (value >> position) & 1;
    498         if (trie[current].children[x_bit] == -1) {
    499             trie[current].children[x_bit] = trie.size();
    500             trie.push_back(node());
    501         }
    502         current = trie[current].children[x_bit];
    503         trie[current].last = max(trie[current].last, index);
    504     }
    505 }
    506  
    507 void solve() {
    508     int n, k;
    509     cin >> n >> k;
    510  
    511     int ans = n + 1;
    512     vector<node> trie(1);
    513     for (int i = 0; i < n; i++) {
    514         int x;
    515         cin >> x;
    516         add(trie, x, i);
    517         int y = find(trie, x, k);
    518         if (y != -1) {
    519             ans = min(ans, i - y + 1);
    520         }
    521     }
    522  
    523     if (ans == n + 1) {
    524         cout << "-1\n";
    525     } else {
    526         cout << ans << '\n';
    527     }
    528 }
    529  
    530 int main() {
    531     int t;
    532     cin >> t;
    533     
    534     while (t--) {
    535         solve();
    536     }
    537  
    538     return 0;
    539 }
    540 ```