1658.md (18379B)
1 Source: https://codeforces.com/blog/entry/101302 2 3 Thank you for participating in the contest! We hope you enjoy the problems. You can also give feedback on each problem, it will help us much in future problem settings. By the way, feel free to share your solution! 4 5 [1658A - Marin and Photoshoot](/contest/1658/problem/A "Codeforces Round 779 (Div. 2)") 6 7 **Hint 1** 8 9 How will you solve this problem if there are just $2$ male cosplayers? 10 11 **Hint 2** 12 13 Notice the distance between $2$ consecutive male cosplayers. 14 15 **Tutorial** 16 17 It is easy to see, in a beautiful picture, there must be at least $2$ female cosplayers between $2$ consecutive male cosplayers. It is also the sufficient condition, as if there are $x$ male cosplayers in a subsegment, there are at least $2(x - 1) = 2x - 2 \geq x$ for all $x \geq 2$. 18 19 **Solution** 20 21 **C++** 22 23 ``` 24 #include <bits/stdc++.h> 25 using namespace std; 26 27 const int N = 2e5 + 5; 28 29 int n; 30 string s; 31 vector<int> v; 32 33 void solve() { 34 v.clear(); 35 cin >> n >> s; 36 int ans = 0; 37 for (int i = 0; i < n; ++i) { 38 if (s[i] == '0') v.push_back(i); 39 } 40 for (int i = 0; i < (int)v.size() - 1; ++i) { 41 if (v[i + 1] - v[i] <= 2) ans += 2 - (v[i + 1] - v[i]) + 1; 42 } 43 cout << ans << '\n'; 44 } 45 46 int main() { 47 ios_base::sync_with_stdio(false); 48 cin.tie(NULL); 49 int t; cin >> t; 50 while (t--) solve(); 51 } 52 ``` 53 54 **Python** 55 56 ``` 57 t = int(input()) 58 for _ in range(t): 59 n = input() 60 s = input() 61 ans = 0 62 cnt = 2 63 for c in s: 64 if c == '1': cnt += 1 65 else: 66 ans += max(2 - cnt, 0) 67 cnt = 0 68 print(ans) 69 ``` 70 71 **Feedback** 72 73 * Didn't solve 74 * Good problem 75 * Average problem 76 * Bad problem 77 78 [1658B - Marin and Anti-coprime Permutation](/contest/1658/problem/B "Codeforces Round 779 (Div. 2)") 79 80 **Hint 1** 81 82 Let's $ g = \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) $. What is the maximum value of $g$? 83 84 **Hint 2** 85 86 For each value of $g$, can you construct a satisfying permutation? 87 88 **Tutorial** 89 90 We can prove that $g \leq 2$. 91 92 **Proof** 93 94 Assuming $g \gt 2$: 95 96 * If there exists a prime number $p \gt 2$ that $p \mid g$, there are $\left \lfloor \dfrac{n}{p} \right \rfloor$ numbers divisible by $p$, so we can match at most $2 \left \lfloor \dfrac{n}{3} \right \rfloor$ numbers into pairs, which is smaller than $n$. 97 * Otherwise, we can match odd numbers with even positions, and even numbers with odd positions, which leads to $2 \mid g$. Because $p_2$ is odd, $2 \cdot p_2$ is not divisible by $2^k$ with $k \gt 1$. 98 99 Therefore, $g\leq 2$. 100 101 Therefore: 102 103 * If $n$ is odd, the answer is $0$ since the number of odd is greater than the number of even. 104 * Otherwise, we will match odd with even and vice versa. For odd number in even position, we have $(\dfrac{n}{2})!$ ways. According to the multiplicative rule, the answer will be $((\dfrac{n}{2})!)^2$. 105 106 **Solution** 107 108 **C++** 109 110 ``` 111 #include <bits/stdc++.h> 112 using namespace std; 113 114 const int MOD = 998244353; 115 116 void solve() { 117 int n; cin >> n; 118 if (n & 1) { 119 cout << "0\n"; 120 return; 121 } 122 long long ans = 1; 123 for (int i = 1; i <= n / 2; ++i) { 124 ans *= 1LL * i * i % MOD; 125 ans %= MOD; 126 } 127 cout << ans << '\n'; 128 } 129 130 int main() { 131 ios_base::sync_with_stdio(false); 132 cin.tie(NULL); 133 int t; cin >> t; 134 while (t--) solve(); 135 return 0; 136 } 137 ``` 138 139 **Python** 140 141 ``` 142 MOD = 998244353 143 t = int(input()) 144 145 for _ in range(t): 146 n = int(input()) 147 if n & 1: 148 print(0) 149 continue 150 ans = 1 151 for i in range(1, n // 2 + 1): 152 ans = ans * i % MOD 153 ans = ans * ans % MOD 154 print(ans) 155 ``` 156 157 **Feedback** 158 159 * Didn't solve 160 * Good problem 161 * Average problem 162 * Bad problem 163 164 [1658C - Shinju and the Lost Permutation](/contest/1658/problem/C "Codeforces Round 779 (Div. 2)") 165 166 **Hint 1** 167 168 There is exactly one $1$ in array $c$ (in $(i - 1)$-th cyclic shift, $c_i \gt 1$ if $p_1 \neq n$, and $c_i = 1$ if $p_1 = n$), so if the number of $1s$ is greater or less than one, the answer is $\texttt{NO}$. 169 170 **Hint 2** 171 172 We can rotate the array such that $c_1 = 1$ (initial state) because we don't have to construct the permutation, so if there exists a permutation with $p_1 = n$, the answer is $\texttt{YES}$. 173 174 **Hint 3** 175 176 Notice the difference of $c_i$ and $c_{i + 1}$. 177 178 **Tutorial** 179 180 In the $i$-th cyclic shift, if $p_1 \gt p_2$ then $c_{i + 1} \leq c_i$, otherwise $c_{i + 1} - c_i = 1$, so if there exists a position $i$ such that $c_{i + 1} - c_i \gt 1$, the answer is $\texttt{NO}$. 181 182 This is the sufficient condition. It can be shown that, if $c_{i + 1} - c_i \leq 1$ for all $1 \leq i \lt n$, then there exists a permutation that satisfies. 183 184 Here is a sketch of the construction: <https://codeforces.com/blog/entry/101302?#comment-899523> 185 186 **Solution** 187 188 **C++** 189 190 ``` 191 #include <bits/stdc++.h> 192 using namespace std; 193 194 void solve() { 195 int n; cin >> n; 196 vector<int> a(n); 197 for (int &v: a) cin >> v; 198 if (count(a.begin(), a.end(), 1) != 1) { 199 cout << "NO\n"; 200 return; 201 } 202 int p = find(a.begin(), a.end(), 1) - a.begin(); 203 rotate(a.begin(), a.begin() + p, a.end()); 204 for (int i = 1; i < n; ++i) { 205 if (a[i] - a[i - 1] > 1) { 206 cout << "NO\n"; 207 return; 208 } 209 } 210 cout << "YES\n"; 211 } 212 213 int main() { 214 ios_base::sync_with_stdio(false); 215 cin.tie(NULL); 216 int t; cin >> t; 217 while (t--) solve(); 218 return 0; 219 } 220 ``` 221 222 **Python** 223 224 ``` 225 import sys 226 input = sys.stdin.readline 227 228 t = int(input()) 229 for _ in range (t): 230 n = int(input()) 231 a = list(map(int, input().split())) 232 233 if a.count(1) != 1: 234 print("NO") 235 continue 236 237 a.append(a[0]) 238 ok = True 239 for i in range (0, n): 240 if a[i + 1] - a[i] > 1: 241 ok = False 242 break 243 244 if ok: print("YES") 245 else: print("NO") 246 ``` 247 248 **Feedback** 249 250 * Didn't solve 251 * Good problem 252 * Average problem 253 * Bad problem 254 255 [1658D1 - 388535 (Easy Version)](/contest/1658/problem/D1 "Codeforces Round 779 (Div. 2)") 256 257 **Tutorial** 258 259 Let's look at the binary representation of numbers from $0$ to $7$: 260 261 * $000$ 262 * $001$ 263 * $010$ 264 * $011$ 265 * $100$ 266 * $101$ 267 * $110$ 268 * $111$ 269 270 Let us look at the $i$-th bit only (maybe $i=2$), we will get a sequence like $[0,0,1,1,0,0,1,1]$. Notice that the number of zeroes equals the number of ones in a prefix only when the length of the prefix is a multiple of $2^i$. Otherwise, there will be more zeros than ones. 271 272 So, we will count the number of flipped and unflipped bits for each bit position. 273 274 * If the number of ones is greater than the number of zeros, the $i$-th bit of $x$ must be $1$. 275 * If the number of zeros is greater than the number of ones, the $i$-th bit of $x$ must be $0$. 276 * If the number of ones is equal to the number of zeros, that $i$-th bit of $x$ can either be $0$ or $1$. 277 278 However, if the number of ones is equal to the number of zeros, we can assign the $i$-th bit anything we like. The rough sketch of the proof is that if $x$ is inside $a$ then $x\oplus2^i$ is also inside $a$. 279 280 **Solution** 281 282 **C++** 283 284 ``` 285 #include <bits/stdc++.h> 286 using namespace std; 287 288 const int N = 2e5 + 5; 289 int p[N], cnt[32][2]; 290 291 void solve() { 292 memset(cnt, 0, sizeof cnt); 293 int l, r; cin >> l >> r; 294 for (int i = l; i <= r; ++i) { 295 int x; cin >> x; 296 for (int j = 0; j <= 30; ++j, x >>= 1) 297 cnt[j][x & 1]++; 298 } 299 int ans = 0; 300 for (int i = 0; i <= 30; ++i) { 301 ans |= ((cnt[i][0] < cnt[i][1]) * (1 << i)); 302 } 303 cout << ans << '\n'; 304 } 305 306 int main() { 307 ios_base::sync_with_stdio(false); 308 cin.tie(NULL); 309 int t; cin >> t; 310 while (t--) solve(); 311 return 0; 312 } 313 ``` 314 315 **Python** 316 317 ``` 318 import sys 319 input = sys.stdin.readline 320 321 t = int(input()) 322 for _ in range (t): 323 l, r = map(int, input().split()) 324 a = list(map(int, input().split())) 325 cnt = [[0] * 2 for _ in range (32)] 326 327 for x in a: 328 for i in range (31): 329 cnt[i][x & 1] += 1 330 x >>= 1 331 332 ans = 0 333 for i in range (31): 334 if (cnt[i][0] < cnt[i][1]): 335 ans |= (1 << i) 336 337 print(ans) 338 ``` 339 340 [1658D2 - 388535 (Hard Version)](/contest/1658/problem/D2 "Codeforces Round 779 (Div. 2)") 341 342 **Hint 1** 343 344 If $a \oplus b = 1$, then $(a \oplus x) \oplus (b \oplus x) = 1$. 345 346 **Hint 2** 347 348 if $l$ is even and $r$ is odd, the last bit of $x$ can be either $0$ or $1$ (we can pair $a_i$ with $a_i \oplus 1$). 349 350 **Tutorial** 351 352 There are two solutions to this problem. 353 354 If $l$ is even and $r$ is odd, we can skip the last bit and divide the range by two, then recursively solve it. Otherwise, we will pair $a_i$ with $a_i \oplus 1$, and we will left with at most $2$ candidates for $x$ to check. 355 356 There is also another solution: we can iterate all possibilities of $x$ (by assuming $a_i$ is $l \oplus x$ for all $1 \leq i \leq n$). If $x$ is the hidden number, $l \leq a_i \oplus x \leq r$ for all $1 \leq i \leq n$, so the problem reduce to "count the number of $a_i$ that $l \leq a_i \oplus x \leq r$", which can be solved with binary trie. 357 358 **Solution** 359 360 **C++** 361 362 ``` 363 #include <bits/stdc++.h> 364 using namespace std; 365 366 const int N = 2e5 + 5; 367 int a[N], l, r; 368 set <int> s, s2; 369 370 void solve() { 371 int mul = 1; 372 s.clear(); 373 cin >> l >> r; 374 for (int i = l; i <= r; ++i) { 375 cin >> a[i]; 376 s.insert(a[i]); 377 } 378 379 for (; l % 2 == 0 && r % 2 == 1; l >>= 1, r >>= 1, mul <<= 1) { 380 s2.clear(); 381 for (int i: s) s2.insert(i >> 1); 382 swap(s, s2); 383 } 384 385 int ans; 386 if (l % 2 == 0) ans = r; 387 else ans = l; 388 389 for (int i: s) { 390 if (s.find(i ^ 1) == s.end()) { 391 int cur = i ^ ans; 392 bool f = true; 393 for (int j : s) 394 f &= ((cur ^ j) >= l && (cur ^ j) <= r); 395 if (f) { 396 ans = cur; 397 break; 398 } 399 } 400 } 401 cout << ans * mul << '\n'; 402 } 403 404 int main() { 405 ios_base::sync_with_stdio(false); 406 cin.tie(NULL); 407 int t; cin >> t; 408 while (t--) solve(); 409 return 0; 410 } 411 ``` 412 413 **Python** 414 415 ``` 416 import sys 417 input = sys.stdin.readline 418 419 def solve(l: int, r: int, s: set): 420 if l % 2 == 0 and r % 2 == 1: 421 t = set() 422 for v in s: t.add(v >> 1) 423 return solve(l >> 1, r >> 1, t) << 1 424 else: 425 for v in s: 426 if (v ^ 1) not in s: 427 ok = True 428 ans = v 429 if l % 2 == 0: ans ^= r 430 else: ans ^= l 431 for x in s: 432 if (x ^ ans) < l or (x ^ ans) > r: 433 ok = False 434 break 435 if ok: return ans 436 437 438 t = int(input()) 439 for _ in range (t): 440 l, r = map(int, input().split()) 441 s = set(map(int, input().split())) 442 print(solve(l, r, s)) 443 ``` 444 445 **Feedback** 446 447 * Didn't solve 448 * Good problem 449 * Average problem 450 * Bad problem 451 452 [1658E - Gojou and Matrix Game](/contest/1658/problem/E "Codeforces Round 779 (Div. 2)") 453 454 **Hint 1** 455 456 What if a player is forced to play in a cell where they get fewer points than the previous move? 457 458 **Hint 2** 459 460 Rephrase the problem, then solve it with dynamic programming. 461 462 **Tutorial** 463 464 Suppose that Marin places a token at $(a,b)$. If Gojou places a token at $(c,d)$ where $V_{c,d} \lt V_{a,b}$, then Gojou would not have any advantage as Marin can play at $(a,b)$ again. After a very huge number of turns, Marin will have more points than Gojou. Generally, if a player is forced to play in a cell where they get fewer points than the previous move, they would instantly lose. 465 466 Therefore, we can rephrase the problem as such: 467 468 * Apart from the first move, the token placed by a player must be more than Manhattan distance *k* away from the previous token placed on the matrix. 469 * Apart from the first move, the token placed by a player must be on a cell with more points than the cell with the token placed by the previous player. 470 * The player who plays the last token is the winner. 471 472 This turns out to be a standard dynamic programming. 473 474 Let $dp[i][j]$ return $1$ if the player who places a token at $(i,j)$ wins. 475 476 Let $V_{a,b}=n^2$, then we have $dp[a][b]=1$ as a base case. 477 478 Then we will fill the values of $dp$ in decreasing values of $V_{i,j}$. $dp[i][j]=1$ if for all $(i',j')$ such that $|i-i'|+|j-j'| \gt k$, we have $dp[i'][j']=0$. Note that by taking the contrapositive, this is equivalent to for all $(i',j')$ such that $dp[i'][j']=1$, we have $|i-i'|+|j-j'| \leq k$. 479 480 Let us maintain a set $S$ that stores the pairs $(i',j')$ such that $dp[i'][j']=1$, then our operations are: 481 482 * adding point $(i,j)$ to $S$ 483 * given $(i,j)$, check if for all $(i',j')$ in $S$, $|i-i'|+|j-j'| \leq k$ 484 485 Notice that $|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$. 486 487 Checking $\max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$ is very simple as we only need to store the minimum and maximum of all $(i+j)$ and $(i-j)$. 488 489 **Solution** 490 491 **C++** 492 493 ``` 494 #include <bits/stdc++.h> 495 using namespace std; 496 497 const int N = 2e3 + 5; 498 bool f[N][N]; 499 int l, r, u, d, n, k; 500 vector<array<int, 5>> v; 501 502 bool check(int i, int j) { 503 return (abs(i - u) <= k && abs(i - d) <= k && abs(j - l) <= k && abs(j - r) <= k); 504 } 505 506 void solve(){ 507 cin >> n >> k; 508 for (int i = 1; i <= n; ++i) { 509 for (int j = 1; j <= n; ++j) { 510 f[i][j] = false; 511 int x; cin >> x; 512 v.push_back({x, i, j, i + j, j - i}); 513 } 514 } 515 516 sort(v.begin(), v.end(), greater<array<int, 5>>()); 517 l = v[0][4], r = v[0][4], u = v[0][3], d = v[0][3]; 518 for (array<int, 5> cell: v) { 519 if (check(cell[3], cell[4])) { 520 f[cell[1]][cell[2]] = true; 521 l = min(l, cell[4]); 522 r = max(r, cell[4]); 523 u = min(u, cell[3]); 524 d = max(d, cell[3]); 525 } 526 } 527 528 for (int i = 1; i <= n; ++i) { 529 for (int j = 1; j <= n; ++j) { 530 if (f[i][j]) cout << 'M'; 531 else cout << 'G'; 532 } 533 cout << '\n'; 534 } 535 } 536 537 int main() { 538 ios_base::sync_with_stdio(false); 539 cin.tie(NULL); 540 solve(); 541 return 0; 542 } 543 ``` 544 545 **Feedback** 546 547 * Didn't solve 548 * Good problem 549 * Average problem 550 * Bad problem 551 552 [1658F - Juju and Binary String](/contest/1658/problem/F "Codeforces Round 779 (Div. 2)") 553 554 **Hint 1** 555 556 Let $b$ be the number of black balls and $w$ be the number of white balls. 557 558 The answer will be impossible if $m$ is not a multiple of $\dfrac{b+w}{gcd(b, w)}$. 559 560 **Observation** 561 562 It is easy to show that the cuteness of $s$ is $\dfrac{b}{n}$. 563 564 What is the number of $\texttt{1}$ in the concatenated string needed so that the answer exists? 565 566 **Proof** 567 568 The cuteness of $s$ is $\dfrac{b}{n} = \dfrac{b}{b+w}$ by definition. 569 570 Now consider $t = s[l_1, r_1] + [l_2, r_2] + \dots + s[l_k, r_k]$, the cuteness of the concatenated string. 571 572 The cuteness of $t$ is $\dfrac{b}{b+w}$, so the number of $\texttt{1}$ needed is $k = \dfrac{m \cdot w}{b + w}$. 573 574 If $k$ is not an integer then there will be no answer, so $m$ must be a multiple of $\dfrac{b+w}{gcd(b, w)}$. 575 576 **Hint 2** 577 578 We don't need more than 2 parts, or to say $k \leq 2$ is needed in this problem. 579 580 **Observation** 581 582 Let $c_i =$ (the number of $\texttt{1}$ in $s[i \dots i + m - 1]$). 583 584 For convenient, from now let assume the array and string is wrapped around: $s[i] = s[i + n]$ and $c_i = c_{i+n}$. 585 586 We have $|c_i-c_{i+1}| \leq 1$ and there exists $c_i = y$ for all $y$ that $min(c_i) \leq y \leq max(c_i)$. 587 588 **Contestant's Proof** 589 590 GM+ [smax](/profile/smax "Grandmaster smax") provides a simple and clean answer [here](https://codeforces.com/blog/entry/101302?#comment-899678). 591 592 **Author's Proof** 593 594 Let $L = min(c_i)$, $R = max(c_i)$ and we are doing with wrap around arrays for convenient. 595 596 We want to prove that for any $y$ that $L \leq y \leq R$ there will be some $c_i = y$. 597 598 Let $d_i = max(c_p, c_{p+1}, \dots, c_i)$ for $p$ is the minimal position that $c_p = L$. 599 600 Let $f_x$ is the first position $i$ starting $p$ that $d_i = x$, we have $d_{f_x} = c_{f_x}$ 601 602 [1] Since $L \leq y \leq R$ and, we have $L = d_p \leq d_{p+1} \leq \dots \leq d_{p+n-1} = R$. 603 604 [2] Since $|c_{i+1} - c_i| \leq 1$ we can show that. 605 606 $\forall p \lt i \lt p + n \rightarrow \left[\begin{array}{l} d_i = d_{i-1} \\ d_i = d_{i-1} + 1 \end{array}\right.$ 607 608 [3] Since $c_i \in \mathbb{N}$, we also have $d_i \in \mathbb{N}$ 609 610 From [1], [2], [3], if there is $d_i = v \gt L$ then there will be $d_j = v - 1$ for some $j$ that $p + (v - L) \leq j \lt i$. 611 612 $\Leftrightarrow \forall v, min(d_i) \leq v \leq max(d_i) \rightarrow \exists d_{f_i} = v$ 613 614 $\Leftrightarrow \exists d_{f_i} = y$ 615 616 $\Leftrightarrow \exists c_{f_i} = y$ 617 618 **Tutorial** 619 620 The answer will be impossible if $m$ is not a multiple of $\dfrac{b+w}{gcd(b, w)}$. 621 622 Otherwise, it is proved that $k \leq 2$ is needed. 623 624 Since we need to select a minimum $k$, let's first check if there is a solution with $k = 1$ 625 626 **Spoiler** 627 628 If there exist such position $p$ that $1 \leq p \leq n - m + 1$ and $s[p, p + m - 1]$ have the same cuteness as $s[1, n]$ then we found an answer. 629 630 Otherwise there must be an answer with $k = 2$, and it is simple too 631 632 **Spoiler** 633 634 If there exist such position $p$ that $1 \leq p \lt m$ and $s[1, p] \cup s[n - (m - p) + 1, n]$ have the same cuteness as $s[1, n]$ then we found an answer. 635 636 Both can be done in linear $O(n)$ with the sliding window technique or prefixsum. 637 638 **Solution** 639 640 **C++** 641 642 ``` 643 #include <bits/stdc++.h> 644 using namespace std; 645 646 int main() { 647 ios_base::sync_with_stdio(false); 648 cin.tie(nullptr); 649 int t; cin >> t; 650 while (t--) { 651 int n, k; cin >> n >> k; 652 string s; cin >> s; 653 int one = count_if(s.begin(), s.end(), [](char c) { return c == '1'; }); 654 if (1LL * one * k % n != 0) { 655 cout << "-1\n"; 656 } else { 657 one = 1LL * one * k / n; 658 vector<int> suf(2 * n + 1); 659 for (int i = 1; i <= 2 * n; i++) { 660 suf[i] = suf[i - 1] + (s[(i - 1) % n] == '1'); 661 if (i >= k && suf[i] == suf[i - k] + one) { 662 if (i <= n) { 663 cout << "1\n"; 664 cout << i - k + 1 << " " << i << '\n'; 665 } else { 666 cout << "2\n"; 667 cout << 1 << " " << i - n << '\n'; 668 cout << i - k + 1 << " " << n << '\n'; 669 } 670 break; 671 } 672 } 673 } 674 } 675 } 676 ``` 677 678 **Feedback** 679 680 * Didn't solve 681 * Good problem 682 * Average problem 683 * Bad problem