1620.md (10501B)
1 Source: https://codeforces.com/blog/entry/98061 2 3 [1620A - Equal or Not Equal](/contest/1620/problem/A "Educational Codeforces Round 119 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 string s; 23 cin >> s; 24 cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n"); 25 } 26 } 27 ``` 28 29 [1620B - Triangles on a Rectangle](/contest/1620/problem/B "Educational Codeforces Round 119 (Rated for Div. 2)") 30 31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 32 33 **Tutorial** 34 35 Tutorial is loading... 36 37 **Solution (awoo)** 38 39 ``` 40 for _ in range(int(input())): 41 w, h = map(int, input().split()) 42 ans = 0 43 for i in range(4): 44 a = [int(x) for x in input().split()][1:] 45 ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w)) 46 print(ans) 47 ``` 48 49 [1620C - BA-String](/contest/1620/problem/C "Educational Codeforces Round 119 (Rated for Div. 2)") 50 51 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Solution (awoo)** 58 59 ``` 60 for _ in range(int(input())): 61 n, k, x = map(int, input().split()) 62 x -= 1 63 s = input()[::-1] 64 res = [] 65 i = 0 66 while i < n: 67 if s[i] == 'a': 68 res.append(s[i]) 69 else: 70 j = i 71 while j + 1 < n and s[j + 1] == s[i]: 72 j += 1 73 cur = (j - i + 1) * k + 1 74 res.append('b' * (x % cur)) 75 x //= cur 76 i = j 77 i += 1 78 print(''.join(res[::-1])) 79 ``` 80 81 [1620D - Exact Change](/contest/1620/problem/D "Educational Codeforces Round 119 (Rated for Div. 2)") 82 83 Idea: [adedalic](/profile/adedalic "International Master adedalic") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution (adedalic)** 90 91 ``` 92 #include<bits/stdc++.h> 93 94 using namespace std; 95 96 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 97 #define sz(a) int((a).size()) 98 99 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 100 return out << "(" << p.x << ", " << p.y << ")"; 101 } 102 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 103 fore(i, 0, sz(v)) { 104 if(i) out << " "; 105 out << v[i]; 106 } 107 return out; 108 } 109 110 int n; 111 vector<int> a; 112 113 inline bool read() { 114 if(!(cin >> n)) 115 return false; 116 a.resize(n); 117 fore (i, 0, n) 118 cin >> a[i]; 119 return true; 120 } 121 122 bool p(int val, int c1, int c2, int c3) { 123 fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) { 124 if (cur1 + 2 * cur2 > val) 125 continue; 126 if ((val - cur1 - 2 * cur2) % 3 != 0) 127 continue; 128 if ((val - cur1 - 2 * cur2) / 3 <= c3) 129 return true; 130 } 131 return false; 132 } 133 134 bool possible(int c1, int c2, int c3) { 135 for (int v : a) { 136 if (!p(v, c1, c2, c3)) 137 return false; 138 } 139 return true; 140 } 141 142 inline void solve() { 143 int m = *max_element(a.begin(), a.end()); 144 int ans = int(1e9); 145 146 const int MAG = 3; 147 fore (c1, 0, MAG) fore (c2, 0, MAG) { 148 int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3); 149 assert(c1 + 2 * c2 + 3 * c3 >= m); 150 151 if (possible(c1, c2, c3)) 152 ans = min(ans, c1 + c2 + c3); 153 } 154 cout << ans << endl; 155 } 156 157 int main() { 158 #ifdef _DEBUG 159 freopen("input.txt", "r", stdin); 160 #endif 161 int t; cin >> t; 162 while(t--) { 163 read(); 164 solve(); 165 } 166 return 0; 167 } 168 ``` 169 170 [1620E - Replace the Numbers](/contest/1620/problem/E "Educational Codeforces Round 119 (Rated for Div. 2)") 171 172 Idea: [Neon](/profile/Neon "Candidate Master Neon") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution 1 (Neon)** 179 180 ``` 181 #include <bits/stdc++.h> 182 183 using namespace std; 184 185 const int N = 500 * 1000 + 13; 186 187 int main() { 188 int q; 189 scanf("%d", &q); 190 vector<int> t(q), x(q), y(q); 191 for (int i = 0; i < q; ++i) { 192 scanf("%d%d", &t[i], &x[i]); 193 if (t[i] == 2) scanf("%d", &y[i]); 194 } 195 vector<int> p(N); 196 iota(p.begin(), p.end(), 0); 197 vector<int> ans; 198 for (int i = q - 1; i >= 0; --i) { 199 if (t[i] == 1) { 200 ans.push_back(p[x[i]]); 201 } else { 202 p[x[i]] = p[y[i]]; 203 } 204 } 205 reverse(ans.begin(), ans.end()); 206 for (int &x : ans) printf("%d ", x); 207 } 208 ``` 209 210 **Solution 2 (Neon)** 211 212 ``` 213 #include <bits/stdc++.h> 214 215 using namespace std; 216 217 const int N = 500 * 1000 + 13; 218 219 int n, q; 220 vector<int> pos[N]; 221 222 int main() { 223 scanf("%d", &q); 224 while (q--) { 225 int t, x, y; 226 scanf("%d", &t); 227 if (t == 1) { 228 scanf("%d", &x); 229 pos[x].push_back(n++); 230 } else { 231 scanf("%d%d", &x, &y); 232 if (x != y) { 233 if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]); 234 for (int &i : pos[x]) pos[y].push_back(i); 235 pos[x].clear(); 236 } 237 } 238 } 239 vector<int> ans(n); 240 for (int x = 0; x < N; ++x) 241 for (int &i : pos[x]) 242 ans[i] = x; 243 for (int &x : ans) printf("%d ", x); 244 } 245 ``` 246 247 [1620F - Bipartite Array](/contest/1620/problem/F "Educational Codeforces Round 119 (Rated for Div. 2)") 248 249 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [Neon](/profile/Neon "Candidate Master Neon") 250 251 **Tutorial** 252 253 Tutorial is loading... 254 255 **Solution 1 (Neon)** 256 257 ``` 258 #include <bits/stdc++.h> 259 260 using namespace std; 261 262 #define forn(i, n) for (int i = 0; i < int(n); ++i) 263 264 const int INF = 1e9; 265 const int N = 1000 * 1000 + 13; 266 267 int n; 268 int p[N], a[N]; 269 int dp[N][2][2]; 270 pair<int, int> pr[N][2][2]; 271 272 void solve() { 273 scanf("%d", &n); 274 forn(i, n) scanf("%d", &p[i]); 275 forn(i, n) forn(pos, 2) forn(sg, 2) 276 dp[i][pos][sg] = INF; 277 dp[0][0][0] = dp[0][0][1] = -INF; 278 279 forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) { 280 forn(nsg, 2) { 281 int x = sg ? -p[i] : p[i]; 282 int y = dp[i][pos][sg]; 283 if (pos) swap(x, y); 284 int z = nsg ? -p[i + 1] : p[i + 1]; 285 if (z > x) { 286 if (dp[i + 1][0][nsg] > y) { 287 dp[i + 1][0][nsg] = y; 288 pr[i + 1][0][nsg] = make_pair(pos, sg); 289 } 290 } else if (z > y) { 291 if (dp[i + 1][1][nsg] > x) { 292 dp[i + 1][1][nsg] = x; 293 pr[i + 1][1][nsg] = make_pair(pos, sg); 294 } 295 } 296 } 297 } 298 299 int pos = -1, sg = -1; 300 forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF) 301 pos = j, sg = k; 302 if (pos == -1) { 303 puts("NO"); 304 return; 305 } 306 for (int i = n - 1; i >= 0; i--) { 307 a[i] = sg ? -p[i] : p[i]; 308 tie(pos, sg) = pr[i][pos][sg]; 309 } 310 311 puts("YES"); 312 forn(i, n) printf("%d ", a[i]); 313 puts(""); 314 } 315 316 int main() { 317 int t; 318 scanf("%d", &t); 319 while (t--) solve(); 320 } 321 ``` 322 323 **Solution 2 (Neon)** 324 325 ``` 326 #include <bits/stdc++.h> 327 328 using namespace std; 329 330 #define forn(i, n) for (int i = 0; i < int(n); ++i) 331 332 const int INF = 1e9; 333 const int N = 1000 * 1000 + 13; 334 335 int n; 336 int p[N], a[N]; 337 int dp[N][2], pr[N][2]; 338 339 void solve() { 340 scanf("%d", &n); 341 forn(i, n) scanf("%d", &p[i]); 342 forn(i, n) forn(j, 2) dp[i][j] = INF; 343 dp[0][0] = dp[0][1] = -INF; 344 forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) { 345 int x = j ? -p[i] : p[i]; 346 int y = dp[i][j]; 347 if (x < y) swap(x, y); 348 forn(nj, 2) { 349 int z = nj ? -p[i + 1] : p[i + 1]; 350 if (z > x) { 351 if (dp[i + 1][nj] > y) { 352 dp[i + 1][nj] = y; 353 pr[i + 1][nj] = j; 354 } 355 } else if (z > y) { 356 if (dp[i + 1][nj] > x) { 357 dp[i + 1][nj] = x; 358 pr[i + 1][nj] = j; 359 } 360 } 361 } 362 } 363 int j = -1; 364 forn(i, 2) if (dp[n - 1][i] != INF) j = i; 365 if (j == -1) { 366 puts("NO"); 367 return; 368 } 369 for (int i = n - 1; i >= 0; i--) { 370 a[i] = j ? -p[i] : p[i]; 371 j = pr[i][j]; 372 } 373 puts("YES"); 374 forn(i, n) printf("%d ", a[i]); 375 puts(""); 376 } 377 378 int main() { 379 int t; 380 scanf("%d", &t); 381 while (t--) solve(); 382 } 383 ``` 384 385 [1620G - Subsequences Galore](/contest/1620/problem/G "Educational Codeforces Round 119 (Rated for Div. 2)") 386 387 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 388 389 **Tutorial** 390 391 Tutorial is loading... 392 393 **Solution (BledDest)** 394 395 ``` 396 #include<bits/stdc++.h> 397 398 using namespace std; 399 400 const int N = 23; 401 const int A = 26; 402 const int S = 20043; 403 int n; 404 string inp[N]; 405 char buf[S]; 406 int cnt[N][A]; 407 const int MOD = 998244353; 408 409 int add(int x, int y) 410 { 411 x += y; 412 while(x >= MOD) x -= MOD; 413 while(x < 0) x += MOD; 414 return x; 415 } 416 417 int sub(int x, int y) 418 { 419 return add(x, -y); 420 } 421 422 int mul(int x, int y) 423 { 424 return (x * 1ll * y) % MOD; 425 } 426 427 void flip_all(vector<int>& a) 428 { 429 int msk = (1 << n) - 1; 430 for(int i = 0; i < (1 << (n - 1)); i++) 431 swap(a[i], a[i ^ msk]); 432 } 433 434 int val[S]; 435 int* where[S]; 436 int cur = 0; 437 438 void change(int& x, int y) 439 { 440 where[cur] = &x; 441 val[cur] = x; 442 x = y; 443 cur++; 444 } 445 446 void rollback() 447 { 448 --cur; 449 (*where[cur]) = val[cur]; 450 } 451 452 void zeta_transform(vector<int>& a) 453 { 454 for(int i = 0; i < n; i++) 455 { 456 for(int j = 0; j < (1 << n); j++) 457 if((j & (1 << i)) == 0) 458 a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]); 459 } 460 } 461 462 void mobius_transform(vector<int>& a) 463 { 464 for(int i = n - 1; i >= 0; i--) 465 { 466 for(int j = (1 << n) - 1; j >= 0; j--) 467 if((j & (1 << i)) != 0) 468 a[j] = sub(a[j], a[j ^ (1 << i)]); 469 } 470 } 471 472 int cur_max[A]; 473 vector<int> mask_cnt; 474 475 void rec(int depth, int mask) 476 { 477 if(depth == n) 478 { 479 mask_cnt[mask] = 1; 480 for(int i = 0; i < A; i++) 481 mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1); 482 } 483 else 484 { 485 int state = cur; 486 for(int i = 0; i < A; i++) 487 change(cur_max[i], min(cur_max[i], cnt[depth][i])); 488 rec(depth + 1, mask + (1 << depth)); 489 while(state != cur) rollback(); 490 rec(depth + 1, mask); 491 } 492 } 493 494 int main() 495 { 496 scanf("%d", &n); 497 for(int i = 0; i < n; i++) 498 { 499 scanf("%s", buf); 500 inp[i] = buf; 501 for(auto x : inp[i]) 502 cnt[i][x - 'a']++; 503 } 504 505 for(int i = 0; i < A; i++) 506 cur_max[i] = S; 507 mask_cnt.resize(1 << n); 508 rec(0, 0); 509 flip_all(mask_cnt); 510 mobius_transform(mask_cnt); 511 flip_all(mask_cnt); 512 int sum = 0; 513 for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]); 514 zeta_transform(mask_cnt); 515 vector<int> res(1 << n); 516 for(int i = 0; i < (1 << n); i++) 517 res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]); 518 519 long long ans = 0; 520 521 for(int i = 0; i < (1 << n); i++) 522 { 523 int c = 0, s = 0; 524 for(int j = 0; j < n; j++) 525 { 526 if(i & (1 << j)) 527 { 528 c++; 529 s += j + 1; 530 } 531 } 532 ans ^= res[i] * 1ll * c * 1ll * s; 533 } 534 535 //for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]); 536 printf("%lld\n", ans); 537 } 538 ```