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