1634.md (11508B)
1 Source: https://codeforces.com/blog/entry/99563 2 3 Thank you for participating, we hope you enjoyed the problems! We kindly ask you to rate each of the round's problems in the corresponding spoiler in order to improve the quality of future contests. 4 5 You can also check video editorials of problems B and C on [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer") [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg). 6 7 All problems were prepared by [Alexdat2000](/profile/Alexdat2000 "International Master Alexdat2000") with the help of coauthors. 8 9 [Why didn't AI participate](https://codeforces.com/blog/entry/99579?#comment-884764) 10 11 [1634A - Reverse and Concatenate](/contest/1634/problem/A "Codeforces Round 770 (Div. 2)") 12 Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777") 13 14 **Hint 1** 15 16 What property will the string have after the first operation (regardless of the type of operation)? 17 18 **Hint 2** 19 20 What happens if you apply an operation to a palindrome? 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution** 27 28 [145468383](/contest/1634/submission/145468383 "Submission 145468383 by sevlll777") 29 30 ``` 31 q = int(input()) 32 33 for _ in range(q): 34 n, k = map(int, input().split()) 35 s = input() 36 if s == s[::-1] or k == 0: 37 print(1) 38 else: 39 print(2) 40 ``` 41 42 **Rate the problem** 43 44 * Didn't solve 45 * Good problem 46 * Average problem 47 * Bad problem 48 49 [1634B - Fortune Telling](/contest/1634/problem/B "Codeforces Round 770 (Div. 2)") 50 Idea: [crazyilian](/profile/crazyilian "Master crazyilian") and [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") 51 52 **Hint 1** 53 54 Can you figure out which of your friends can't get the number $y$ regardless of the order of operations? The answer to the problem would be the other person, since the jury guarantees that exactly one of your friends could get it. 55 56 **Hint 2** 57 58 What do the numbers $a \oplus b$ and $a + b$ have in common for any $a, b$? 59 60 **Hint 3** 61 62 What do all the numbers that can be obtained by all combinations of operations starting with $x$ have in common? Does the set of these numbers intersect with the set of numbers that can be obtained starting with $x + 3$? 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution** 69 70 [145468445](/contest/1634/submission/145468445 "Submission 145468445 by sevlll777") 71 72 ``` 73 def main(): 74 n, x, y = map(int, input().split()) 75 a = list(map(int, input().split())) 76 if (sum(a) + x + y) % 2 == 0: 77 print('Alice') 78 else: 79 print('Bob') 80 81 for _ in range(int(input())): 82 main() 83 ``` 84 85 **Rate the problem** 86 87 * Didn't solve 88 * Good problem 89 * Average problem 90 * Bad problem 91 92 [1634C - OKEA](/contest/1634/problem/C "Codeforces Round 770 (Div. 2)") 93 Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777") 94 95 **Hint 1** 96 97 If $k \gt 1$, for which $n$ is there no solution? 98 99 **Hint 1.1** 100 101 For which $n$ is there no solution when $k = 2$? Does the same rule of thumb hold for other $k \gt 1$? 102 103 **Hint 2** 104 105 Note that the array $[1, 3, 5, 7, 9, ...]$ satisfies the requirements (that is, the arithmetic mean of each subsegment is an integer) because the sum of the first $X$ elements of this array is $X^2$. Try to generalize this special case and find other arrays that satisfy the conditions. 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution** 112 113 [145468509](/contest/1634/submission/145468509 "Submission 145468509 by sevlll777") 114 115 ``` 116 def solve(): 117 n, k = map(int, input().split()) 118 if k == 1: 119 print("YES") 120 for i in range(1, n + 1): 121 print(i) 122 return 123 124 if n % 2 == 1: 125 print("NO") 126 return 127 128 print("YES") 129 for i in range(1, n + 1): 130 print(*[i for i in range(i, n * k + 1, n)]) 131 132 for _ in range(int(input())): 133 solve() 134 ``` 135 136 **Rate the problem** 137 138 * Didn't solve 139 * Good problem 140 * Average problem 141 * Bad problem 142 143 [1634D - Finding Zero](/contest/1634/problem/D "Codeforces Round 770 (Div. 2)") 144 Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777") 145 146 **Hint 1** 147 148 The problem can be reworded as follows: find $n - 2$ indices that definitely can't contain a zero. 149 150 **Hint 2** 151 152 Solve the problem for $n = 4$. 153 154 **Hint 2.1** 155 156 For $n = 4$, denote by $\bar{i}$ the answer to the query for the three indices except $i$. Knowing $\bar{1}$, $\bar{2}$, $\bar{3}$, and $\bar{4}$, can you find two indexes that don't contain zero for certain? Use the fact that there is exactly one zero in the array. 157 158 **Hint 3** 159 160 Solve the problem for even $n$ using the solution for $n = 4$. 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution** 167 168 [145469065](/contest/1634/submission/145469065 "Submission 145469065 by sevlll777") 169 170 ``` 171 #include <bits/stdc++.h> 172 173 #define all(x) (x).begin(), (x).end() 174 #define len(x) (int) (x).size() 175 176 using namespace std; 177 178 179 int get(const vector <int>& x) { 180 cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl; 181 int ans; 182 cin >> ans; 183 return ans; 184 } 185 186 187 signed main() { 188 ios_base::sync_with_stdio(); 189 cin.tie(nullptr); 190 191 int t; 192 cin >> t; 193 194 while(t --> 0) { 195 int n; 196 cin >> n; 197 198 pair <int, int> possible = {0, 1}; 199 for (int i = 2; i < n - 1; i += 2) { 200 vector <pair <int, int>> ch(4); 201 vector <int> now = {possible.first, possible.second, i, i + 1}; 202 for (int j = 0; j < 4; j++) { 203 vector <int> x = now; 204 x.erase(x.begin() + j); 205 ch[j] = {get(x), now[j]}; 206 } 207 sort(all(ch)); 208 possible = {ch[0].second, ch[1].second}; 209 } 210 if (n % 2 == 1) { 211 int other = 0; 212 while (possible.first == other || possible.second == other) { 213 other++; 214 } 215 vector <pair <int, int>> ch(4); 216 vector <int> now = {possible.first, possible.second, n - 1, other}; 217 for (int j = 0; j < 4; j++) { 218 vector <int> x = now; 219 x.erase(x.begin() + j); 220 ch[j] = {get(x), now[j]}; 221 } 222 sort(all(ch)); 223 possible = {ch[0].second, ch[1].second}; 224 } 225 cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl; 226 } 227 228 return 0; 229 } 230 ``` 231 232 **Rate the problem** 233 234 * Didn't solve 235 * Good problem 236 * Average problem 237 * Bad problem 238 239 [1634E - Fair Share](/contest/1634/problem/E "Codeforces Round 770 (Div. 2)") 240 Idea: [sevlll777](/profile/sevlll777 "International Master sevlll777") 241 242 **Hint 1** 243 244 In what cases is the answer definitely NO? 245 246 **Hint 2** 247 248 The lengths of all arrays are even numbers, and each number appears an even number of times in total. There are suspiciously many even numbers... 249 250 **Hint 3** 251 252 An Euler circuit is a circuit that passes through all edges of a graph exactly once (or a union of several circuits if the graph is disconnected). It turns out that an Euler circuit exists if and only if the degree of each vertex is even. 253 254 **Hint 4** 255 256 Construct some graph such that the degree of each of its vertices is even, find a directed Eulerian circuit in it, and reconstruct the answer to the problem using this circuit. What do the edges of such graph correspond to? 257 258 **Tutorial** 259 260 Tutorial is loading... 261 262 **Solution** 263 264 [145468656](/contest/1634/submission/145468656 "Submission 145468656 by sevlll777") 265 266 ``` 267 #include <bits/stdc++.h> 268 269 #define len(x) (int) (x).size() 270 #define all(x) (x).begin(), (x).end() 271 #define endl "\n" 272 273 using namespace std; 274 275 const int N = 4e5 + 100, H = 2e5 + 50; 276 vector <pair <int, int>> g[N]; 277 string ans[N]; 278 int pos[N]; 279 280 void dfs(int v) { 281 if (pos[v] == 0) { 282 ans[v] = string(len(g[v]), 'L'); 283 } 284 285 while (pos[v] < len(g[v])) { 286 auto [i, ind] = g[v][pos[v]]; 287 if (i == -1) { 288 pos[v]++; 289 continue; 290 } 291 g[i][ind].first = -1, g[v][pos[v]].first = -1; 292 if (v < H) { 293 ans[v][pos[v]] = 'R'; 294 } 295 pos[v]++; 296 dfs(i); 297 } 298 } 299 300 signed main() { 301 ios::sync_with_stdio(false); 302 cin.tie(nullptr); 303 304 int m; 305 cin >> m; 306 map <int, int> ind, cnt; 307 int fre_ind = 0; 308 309 vector <vector <int>> nums(m); 310 for (int i = 0; i < m; i++) { 311 int n; 312 cin >> n; 313 for (int _ = 0; _ < n; _++) { 314 int x; 315 cin >> x; 316 if (!ind.count(x)) { 317 ind[x] = fre_ind++; 318 } 319 x = ind[x]; 320 cnt[x]++; 321 nums[i].push_back(x); 322 g[i].emplace_back(x + H, len(g[x + H])); 323 g[x + H].emplace_back(i, len(g[i]) - 1); 324 } 325 } 326 327 for (auto [num, cn] : cnt) { 328 if (cn % 2 == 1) { 329 cout << "NO" << endl; 330 return 0; 331 } 332 } 333 334 for (int i = 0; i < N; i++) { 335 dfs(i); 336 } 337 338 cout << "YES" << endl; 339 for (int i = 0; i < m; i++) { 340 cout << ans[i] << endl; 341 } 342 return 0; 343 } 344 ``` 345 346 **Rate the problem** 347 348 * Didn't solve 349 * Good problem 350 * Average problem 351 * Bad problem 352 353 [1634F - Fibonacci Additions](/contest/1634/problem/F "Codeforces Round 770 (Div. 2)") 354 Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste") 355 356 **Hint 1** 357 358 Let $C_i = A_i - B_i$. Perform all operations on the array $C$. 359 360 **Hint 2** 361 362 Nevermind Fibonacci and suppose the operation was to increase the elements of a given subsegment by a given constant. Can you solve this problem without using heavy data structures like segment tree? 363 364 **Hint 3** 365 366 Generalize the idea from hint 2 using the characteristic property of Fibonacci numbers ($F_i = F_{i-1} + F_{i-2}$). 367 368 **Tutorial** 369 370 Tutorial is loading... 371 372 **Solution** 373 374 [145468716](/contest/1634/submission/145468716 "Submission 145468716 by sevlll777") 375 376 ``` 377 #include <bits/stdc++.h> 378 379 #define all(x) (x).begin(), (x).end() 380 #define len(x) (int) (x).size() 381 #define endl "\n" 382 #define int long long 383 384 using namespace std; 385 386 const int N = 3e5 + 100; 387 int MOD; 388 int fib[N]; 389 390 vector <int> unfib; 391 int notzero = 0; 392 393 void upd(int ind, int delta) { 394 notzero -= (unfib[ind] != 0); 395 unfib[ind] += delta; 396 if (unfib[ind] >= MOD) { 397 unfib[ind] -= MOD; 398 }; 399 notzero += (unfib[ind] != 0); 400 } 401 402 signed main() { 403 ios_base::sync_with_stdio(false); 404 cin.tie(nullptr); 405 cout.tie(nullptr); 406 407 int n, q; 408 cin >> n >> q >> MOD; 409 410 fib[0] = fib[1] = 1; 411 for (int i = 2; i < N; i++) { 412 fib[i] = (fib[i - 1] + fib[i - 2]) % MOD; 413 } 414 415 vector <int> delta(n); 416 for (int& i : delta) { 417 cin >> i; 418 } 419 for (int i = 0; i < n; i++) { 420 int x; 421 cin >> x; 422 delta[i] = (delta[i] - x + MOD) % MOD; 423 } 424 425 unfib.resize(n); 426 unfib[0] = delta[0]; 427 if (len(unfib) >= 2) { 428 unfib[1] = (delta[1] - delta[0] + MOD) % MOD; 429 } 430 for (int i = 2; i < n; i++) { 431 unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD; 432 } 433 for (int i = 0; i < n; i++) { 434 notzero += (unfib[i] != 0); 435 } 436 437 while (q--) { 438 char c; 439 int l, r; 440 cin >> c >> l >> r; 441 if (c == 'A') { 442 upd(l - 1, 1); 443 if (r != n) { 444 upd(r, MOD - fib[r - l + 1]); 445 } 446 if (r < n - 1) { 447 upd(r + 1, MOD - fib[r - l]); 448 } 449 } else { 450 upd(l - 1, MOD - 1); 451 if (r != n) { 452 upd(r, fib[r - l + 1]); 453 } 454 if (r < n - 1) { 455 upd(r + 1, fib[r - l]); 456 } 457 } 458 if (!notzero) { 459 cout << "YES" << endl; 460 } else { 461 cout << "NO" << endl; 462 } 463 } 464 return 0; 465 } 466 ``` 467 468 **Rate the problem** 469 470 * Didn't solve 471 * Good problem 472 * Average problem 473 * Bad problem