1823.md (12278B)
1 Source: https://codeforces.com/blog/entry/115465 2 3 [1823A - A-characteristic](/contest/1823/problem/A "Codeforces Round 868 (Div. 2)") 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Solution C++** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int tt; 18 cin >> tt; 19 while (tt--) { 20 int n, k, x = -1; 21 cin >> n >> k; 22 for (int i = 0; i <= n; i++) { 23 if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) { 24 x = i; 25 } 26 } 27 if (x == -1) 28 cout << "NO\n"; 29 else { 30 cout << "YES\n"; 31 for (int i = 0; i < n; i++) { 32 if (i < x) 33 cout << 1 << ' '; 34 else 35 cout << -1 << ' '; 36 } 37 cout << '\n'; 38 } 39 } 40 41 return 0; 42 } 43 ``` 44 45 **Solution Python** 46 47 ``` 48 for tt in range(int(input())): 49 n, k = map(int, input().split()) 50 x = -1 51 52 for i in range(0, n + 1): 53 if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k: 54 x = i 55 56 if x == -1: 57 print("NO") 58 else: 59 print("YES") 60 for i in range(0, n): 61 if i < x: 62 print("1 ", end = '') 63 else: 64 print("-1 ", end = '') 65 print("") 66 ``` 67 68 [1823B - Sort with Step](/contest/1823/problem/B "Codeforces Round 868 (Div. 2)") 69 70 **Editorial** 71 72 Tutorial is loading... 73 74 **Solution C++** 75 76 ``` 77 #include <bits/stdc++.h> 78 79 using namespace std; 80 81 int main() { 82 int tt; 83 cin >> tt; 84 while (tt--) { 85 int n, k; 86 cin >> n >> k; 87 vector <int> p(n); 88 for (int i = 0; i < n; i++) { 89 cin >> p[i]; 90 p[i]--; 91 } 92 93 int bad = 0; 94 for (int i=0; i<n; i++) { 95 if (p[i] % k != i % k) { 96 bad++; 97 } 98 } 99 100 if(bad == 0) 101 cout << 0 << '\n'; 102 else if(bad == 2) 103 cout << 1 << '\n'; 104 else 105 cout << -1 << '\n'; 106 } 107 108 return 0; 109 } 110 ``` 111 112 **Solution Python** 113 114 ``` 115 for tt in range(int(input())): 116 n, k = map(int, input().split()) 117 p = list(map(int, input().split())) 118 for i in range(0, n): 119 p[i] -= 1 120 121 bad = 0 122 for i in range(0, n): 123 if p[i] % k != i % k: 124 bad += 1 125 126 if bad == 0: 127 print(0) 128 elif bad == 2: 129 print(1) 130 else: 131 print(-1) 132 ``` 133 134 [1823C - Strongly Composite](/contest/1823/problem/C "Codeforces Round 868 (Div. 2)") 135 136 **Editorial** 137 138 Tutorial is loading... 139 140 **Solution C++** 141 142 ``` 143 #include <bits/stdc++.h> 144 145 using namespace std; 146 147 int main() { 148 int tt; 149 cin >> tt; 150 while (tt--) { 151 int n; 152 cin >> n; 153 map <int,int> a; 154 for (int i = 0; i < n; i++) { 155 int x; 156 cin >> x; 157 for (int j = 2; j * j <= x; j++) { 158 while (x % j == 0) { 159 x /= j; 160 a[j]++; 161 } 162 } 163 if (x != 1) { 164 a[x]++; 165 } 166 } 167 168 int res = 0, rem = 0; 169 170 for (pair <int, int> p : a) { 171 int num = p.first; 172 int cnt = p.second; 173 res += cnt / 2; 174 rem += cnt % 2; 175 } 176 177 res += rem / 3; 178 cout << res << '\n'; 179 } 180 181 return 0; 182 } 183 ``` 184 185 **Solution Python** 186 187 ``` 188 def is_prime(x): 189 i = 2 190 while i * i <= x: 191 if x % i == 0: 192 return False 193 i += 1 194 return True 195 196 def is_strongly_composite(x): 197 m = [] 198 i = 2 199 while i * i <= x: 200 while x % i == 0: 201 x = x // i 202 m.append(i) 203 i += 1 204 if not x == 1: 205 m.append(i) 206 return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1])) 207 208 for tt in range(int(input())): 209 n = int(input()) 210 lst = list(map(int, input().split())) 211 a = {} 212 for x in lst: 213 i = 2 214 while i * i <= x: 215 while x % i == 0: 216 x = x // i 217 if i in a: 218 a[i] += 1 219 else: 220 a[i] = 1 221 i += 1 222 if x != 1: 223 if x in a: 224 a[x] += 1 225 else: 226 a[x] = 1 227 228 res, rem = 0, 0 229 230 for num in a: 231 cnt = a[num] 232 res += cnt // 2 233 rem += cnt % 2 234 235 res += rem // 3 236 print(res) 237 ``` 238 239 **Notes** 240 241 There were initially more complex version of this task. Can you solve it? 242 243 You are given $n$ integers $a_1, a_2, \dots, a_n$ ($a_i \gt 1$). You can perform the following operation with array $a$ any number of times: 244 245 1. choose two indices $i$ and $j$ ($i \lt j$); 246 2. erase elements $a_i$ and $a_j$ from $a$; 247 3. insert element $a_i \cdot a_j$ in $a$. 248 249 After performing one such operation, the length of $a$ decreases by one. 250 251 Let's say that array $a$ is good, if it contains only strongly composite numbers. 252 253 What is the minimum number of operation you need to perform to make array $a$ good? 254 255 [1823D - Unique Palindromes](/contest/1823/problem/D "Codeforces Round 868 (Div. 2)") 256 257 **Editorial** 258 259 Tutorial is loading... 260 261 **Solution C++** 262 263 ``` 264 #include <bits/stdc++.h> 265 266 using namespace std; 267 268 int main() { 269 int tt; 270 cin >> tt; 271 while (tt--) { 272 int n, k; 273 cin >> n >> k; 274 vector <int> x(k), c(k); 275 for (int i = 0; i < k; i++) 276 cin >> x[i]; 277 for (int i = 0; i < k; i++) 278 cin >> c[i]; 279 280 if (c[0] < 3 || c[0] > x[0]) { 281 cout << "NO\n"; 282 continue; 283 } 284 285 string s; 286 287 char cur = 'a'; 288 for (int i = 0; i < c[0] - 3; i++) 289 s.push_back('a'); 290 291 for (int i = c[0] - 3; i < x[0]; i++) { 292 s.push_back(cur); 293 cur++; 294 if (cur == 'd') cur = 'a'; 295 } 296 297 bool good = true; 298 for (int j = 1; j < k; j++) { 299 int dx = x[j] - x[j - 1]; 300 int dc = c[j] - c[j - 1]; 301 if (dc > dx) { 302 good = false; 303 break; 304 } 305 306 for (int i = 0; i < dc; i++) 307 s.push_back('c' + j); 308 for (int i = dc; i < dx; i++) { 309 s.push_back(cur); 310 cur++; 311 if (cur == 'd') cur = 'a'; 312 } 313 } 314 315 if (good) 316 cout << "YES" << endl << s << endl; 317 else 318 cout << "NO" << endl; 319 } 320 321 return 0; 322 } 323 ``` 324 325 **Solution Python** 326 327 ``` 328 for tt in range(int(input())): 329 n, k = map(int, input().split()) 330 x = list(map(int, input().split())) 331 c = list(map(int, input().split())) 332 333 if c[0] < 3 or c[0] > x[0]: 334 print("NO") 335 continue 336 337 s = "" 338 cur = 'a' 339 340 for i in range(0, c[0] - 3): 341 s += "a" 342 343 for i in range(c[0] - 3, x[0]): 344 s += cur 345 cur = chr(ord(cur) + 1) 346 if cur == 'd': 347 cur = 'a' 348 349 good = True 350 for j in range(1, k): 351 dx = x[j] - x[j - 1] 352 dc = c[j] - c[j - 1] 353 if dc > dx: 354 good = False 355 break 356 357 for i in range(0, dc): 358 s += chr(ord('c') + j) 359 for i in range(dc, dx): 360 s += cur 361 cur = chr(ord(cur) + 1) 362 if cur == 'd': 363 cur = 'a' 364 365 if good: 366 print("YES") 367 print(s) 368 else: 369 print("NO") 370 ``` 371 372 **Notes** 373 374 There were initially simpler version of this problem with $k = 1$, but it coincided with other problem. 375 376 Also, how does checker in this problem works? 377 378 [1823E - Removing Graph](/contest/1823/problem/E "Codeforces Round 868 (Div. 2)") 379 380 **Editorial** 381 382 Tutorial is loading... 383 384 **Solution C++** 385 386 ``` 387 #include <bits/stdc++.h> 388 389 using namespace std; 390 391 int main() { 392 int n, l, r; 393 cin >> n >> l >> r; 394 vector < vector <int> > g(n); 395 for (int i = 0; i < n; i++) { 396 int a, b; 397 cin >> a >> b; 398 a--, b--; 399 g[a].push_back(b); 400 g[b].push_back(a); 401 } 402 403 int res=0, size; 404 vector <int> used(n); 405 406 function <void(int)> dfs = [&] (int v) { 407 used[v] = true; 408 size++; 409 for (int to : g[v]) { 410 if (!used[to]) 411 dfs(to); 412 } 413 }; 414 415 for (int i = 0; i < n; i++) { 416 if (!used[i]) { 417 size = 0; 418 dfs(i); 419 if (size <= l + r - 1) { 420 res ^= size / l; 421 } 422 } 423 } 424 425 if (res) 426 cout << "Alice\n"; 427 else 428 cout << "Bob\n"; 429 430 return 0; 431 } 432 ``` 433 434 **Solution Python** 435 436 ``` 437 from sys import setrecursionlimit 438 import threading 439 440 def main(): 441 n, l, r = map(int, input().split()) 442 443 g = [[] for i in range(0, n)] 444 for i in range(0, n): 445 a, b = map(int, input().split()) 446 a -= 1 447 b -= 1 448 g[a].append(b) 449 g[b].append(a) 450 451 res = 0 452 used = [False for i in range(0, n)] 453 454 def dfs(v): 455 used[v] = True 456 size = 1 457 for to in g[v]: 458 if not used[to]: 459 size += dfs(to) 460 return size 461 462 for i in range(0, n): 463 if not used[i]: 464 size = dfs(i) 465 if size <= l + r - 1: 466 res ^= size // l 467 468 if res: 469 print("Alice") 470 else: 471 print("Bob") 472 473 setrecursionlimit(10 ** 9) 474 threading.stack_size(2 ** 27) 475 thread = threading.Thread(target=main) 476 thread.start() 477 ``` 478 479 [1823F - Random Walk](/contest/1823/problem/F "Codeforces Round 868 (Div. 2)") 480 481 **Editorial** 482 483 Tutorial is loading... 484 485 **Solution C++** 486 487 ``` 488 #include <bits/stdc++.h> 489 490 using namespace std; 491 492 const int mod = 998244353; 493 494 int main(){ 495 int n, s, t; 496 cin >> n >> s >> t; 497 s--, t--; 498 499 vector < vector <int> > g(n); 500 vector <int> previous(n, -1); 501 vector <int> inPath(n); 502 vector <long long> res(n); 503 504 for (int i = 0; i < n - 1; i++) { 505 int a, b; 506 cin >> a >> b; 507 a--, b--; 508 g[a].push_back(b); 509 g[b].push_back(a); 510 } 511 512 function <void (int, int)> dfs = [&] (int v, int p) { 513 for (int to : g[v]) { 514 if (to == p) continue; 515 previous[to] = v; 516 dfs(to, v); 517 } 518 }; 519 520 function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) { 521 res[v] = k * (long long)g[v].size(); 522 for (int to : g[v]) { 523 if (to == p) continue; 524 dfs2(to, v, k); 525 } 526 }; 527 528 dfs(s, -1); 529 530 int ptr = t; 531 inPath[t] = true; 532 533 while (ptr != s) { 534 res[previous[ptr]] = res[ptr] + 2; 535 ptr = previous[ptr]; 536 inPath[ptr] = true; 537 } 538 539 for (int v = 0; v < n; v++) { 540 if (inPath[v]) { 541 res[v] = res[v] / 2 * (long long)g[v].size(); 542 for (int to : g[v]) { 543 if (!inPath[to]) { 544 dfs2(to, v, res[v] / (int)g[v].size()); 545 } 546 } 547 } 548 } 549 550 res[t]++; 551 552 for (long long i : res) 553 cout << i % mod << ' '; 554 cout<<'\n'; 555 556 return 0; 557 } 558 ``` 559 560 **Solution Python** 561 562 ``` 563 from sys import setrecursionlimit 564 import threading 565 566 mod = 998244353 567 568 def main(): 569 n, s, t = map(int, input().split()) 570 s -= 1 571 t -= 1 572 573 g = [[] for i in range(0, n)] 574 previous = [-1 for i in range(0, n)] 575 inPath = [False for i in range(0, n)] 576 res = [0 for i in range(0, n)] 577 578 for i in range(0, n - 1): 579 a, b = map(int, input().split()) 580 a -= 1 581 b -= 1 582 g[a].append(b) 583 g[b].append(a) 584 585 def dfs(v, p): 586 for to in g[v]: 587 if to == p: 588 continue 589 previous[to] = v 590 dfs(to, v) 591 592 def dfs2(v, p, k): 593 res[v] = k * len(g[v]) 594 for to in g[v]: 595 if to == p: 596 continue 597 dfs2(to, v, k) 598 599 dfs(s, -1) 600 601 ptr = t 602 inPath[t] = True 603 604 while ptr != s: 605 res[previous[ptr]] = res[ptr] + 2 606 ptr = previous[ptr] 607 inPath[ptr] = True 608 609 for v in range(0, n): 610 if inPath[v]: 611 res[v] = res[v] // 2 * len(g[v]) 612 for to in g[v]: 613 if not inPath[to]: 614 dfs2(to, v, res[v] // len(g[v])) 615 616 res[t] += 1 617 618 for i in res: 619 print(i % mod, end = ' ') 620 print("") 621 622 setrecursionlimit(10 ** 9) 623 threading.stack_size(2 ** 27) 624 thread = threading.Thread(target=main) 625 thread.start() 626 ```