1473.md (13951B)
1 Source: https://codeforces.com/blog/entry/86827 2 3 [1473A - Replacing Elements](/contest/1473/problem/A "Educational Codeforces Round 102 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), [adedalic](/profile/adedalic "International Master adedalic") 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 tc; 20 cin >> tc; 21 while (tc--) { 22 int n, d; 23 cin >> n >> d; 24 vector<int> a(n); 25 for (int& x : a) cin >> x; 26 sort(a.begin(), a.end()); 27 cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl; 28 } 29 } 30 ``` 31 32 [1473B - String LCM](/contest/1473/problem/B "Educational Codeforces Round 102 (Rated for Div. 2)") 33 34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (Neon)** 41 42 ``` 43 #include <bits/stdc++.h> 44 45 using namespace std; 46 47 int main() { 48 auto mul = [](string s, int k) -> string { 49 string res = ""; 50 while (k--) res += s; 51 return res; 52 }; 53 54 int tc; 55 cin >> tc; 56 while (tc--) { 57 string s, t; 58 cin >> s >> t; 59 int n = s.length(), m = t.length(); 60 int g = __gcd(n, m); 61 if (mul(s, m / g) == mul(t, n / g)) 62 cout << mul(s, m / g) << endl; 63 else 64 cout << "-1" << endl; 65 } 66 } 67 ``` 68 69 [1473C - No More Inversions](/contest/1473/problem/C "Educational Codeforces Round 102 (Rated for Div. 2)") 70 71 Idea: [adedalic](/profile/adedalic "International Master adedalic") 72 73 **Tutorial** 74 75 Tutorial is loading... 76 77 **Solution (adedalic)** 78 79 ``` 80 fun main() { 81 repeat(readLine()!!.toInt()) { 82 val (n, k) = readLine()!!.split(' ').map { it.toInt() } 83 84 for (i in 1 until (k - (n - k))) 85 print("$i ") 86 for (i in k downTo (k - (n - k))) 87 print("$i ") 88 println("") 89 } 90 } 91 ``` 92 93 [1473D - Program](/contest/1473/problem/D "Educational Codeforces Round 102 (Rated for Div. 2)") 94 95 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution (awoo)** 102 103 ``` 104 #include <bits/stdc++.h> 105 106 #define forn(i, n) for (int i = 0; i < int(n); i++) 107 108 using namespace std; 109 110 int main() { 111 cin.tie(0); 112 ios_base::sync_with_stdio(0); 113 int t; 114 cin >> t; 115 forn(_, t){ 116 int n, m; 117 string s; 118 cin >> n >> m; 119 cin >> s; 120 vector<int> sul(1, 0), sur(1, 0); 121 for (int i = n - 1; i >= 0; --i){ 122 int d = s[i] == '+' ? 1 : -1; 123 sul.push_back(min(0, sul.back() + d)); 124 sur.push_back(max(0, sur.back() + d)); 125 } 126 reverse(sul.begin(), sul.end()); 127 reverse(sur.begin(), sur.end()); 128 vector<int> prl(1, 0), prr(1, 0), pr(1, 0); 129 forn(i, n){ 130 int d = s[i] == '+' ? 1 : -1; 131 pr.push_back(pr.back() + d); 132 prl.push_back(min(prl.back(), pr.back())); 133 prr.push_back(max(prr.back(), pr.back())); 134 } 135 forn(i, m){ 136 int l, r; 137 cin >> l >> r; 138 --l; 139 int l1 = prl[l], r1 = prr[l]; 140 int l2 = sul[r] + pr[l], r2 = sur[r] + pr[l]; 141 printf("%d\n", max(r1, r2) - min(l1, l2) + 1); 142 } 143 } 144 return 0; 145 } 146 ``` 147 148 [1473E - Minimum Path](/contest/1473/problem/E "Educational Codeforces Round 102 (Rated for Div. 2)") 149 150 Idea: [Neon](/profile/Neon "Candidate Master Neon") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution (Neon)** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 const int N = 200 * 1000 + 13; 164 165 int n, m; 166 vector<pair<int, int>> g[N]; 167 long long d[N][2][2]; 168 169 int main() { 170 scanf("%d%d", &n, &m); 171 for (int i = 0; i < m; i++) { 172 int v, u, w; 173 scanf("%d%d%d", &v, &u, &w); 174 --v; --u; 175 g[v].emplace_back(u, w); 176 g[u].emplace_back(v, w); 177 } 178 179 for (int i = 0; i < n; i++) 180 for (int j = 0; j < 2; j++) 181 for (int k = 0; k < 2; k++) 182 d[i][j][k] = (long long)1e18; 183 184 d[0][0][0] = 0; 185 set<pair<long long, array<int, 3>>> q; 186 q.insert({0, {0, 0, 0}}); 187 188 while (!q.empty()) { 189 auto [v, mx, mn] = q.begin()->second; 190 q.erase(q.begin()); 191 for (auto [u, w] : g[v]) { 192 for (int i = 0; i <= 1 - mx; i++) { 193 for (int j = 0; j <= 1 - mn; j++) { 194 if (d[u][mx | i][mn | j] > d[v][mx][mn] + (1 - i + j) * w) { 195 auto it = q.find({d[u][mx | i][mn | j], {u, mx | i, mn | j}}); 196 if (it != q.end()) 197 q.erase(it); 198 d[u][mx | i][mn | j] = d[v][mx][mn] + (1 - i + j) * w; 199 q.insert({d[u][mx | i][mn | j], {u, mx | i, mn | j}}); 200 } 201 } 202 } 203 } 204 } 205 206 for (int i = 1; i < n; i++) { 207 printf("%lld ", d[i][1][1]); 208 } 209 puts(""); 210 } 211 ``` 212 213 [1473F - Strange Set](/contest/1473/problem/F "Educational Codeforces Round 102 (Rated for Div. 2)") 214 215 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution (BledDest)** 222 223 ``` 224 #include<bits/stdc++.h> 225 226 using namespace std; 227 228 template<typename T> 229 struct dinic { 230 struct edge { 231 int u, rev; 232 T cap, flow; 233 }; 234 235 int n, s, t; 236 T flow; 237 vector<int> lst; 238 vector<int> d; 239 vector<vector<edge>> g; 240 241 T scaling_lim; 242 bool scaling; 243 244 dinic() {} 245 246 dinic(int n, int s, int t, bool scaling = false) : n(n), s(s), t(t), scaling(scaling) { 247 g.resize(n); 248 d.resize(n); 249 lst.resize(n); 250 flow = 0; 251 } 252 253 void add_edge(int v, int u, T cap, bool directed = true) { 254 g[v].push_back({u, g[u].size(), cap, 0}); 255 g[u].push_back({v, int(g[v].size()) - 1, directed ? 0 : cap, 0}); 256 } 257 258 T dfs(int v, T flow) { 259 if (v == t) 260 return flow; 261 if (flow == 0) 262 return 0; 263 T result = 0; 264 for (; lst[v] < g[v].size(); ++lst[v]) { 265 edge& e = g[v][lst[v]]; 266 if (d[e.u] != d[v] + 1) 267 continue; 268 T add = dfs(e.u, min(flow, e.cap - e.flow)); 269 if (add > 0) { 270 result += add; 271 flow -= add; 272 e.flow += add; 273 g[e.u][e.rev].flow -= add; 274 } 275 if (flow == 0) 276 break; 277 } 278 return result; 279 } 280 281 bool bfs() { 282 fill(d.begin(), d.end(), -1); 283 queue<int> q({s}); 284 d[s] = 0; 285 while (!q.empty() && d[t] == -1) { 286 int v = q.front(); q.pop(); 287 for (auto& e : g[v]) { 288 if (d[e.u] == -1 && e.cap - e.flow >= scaling_lim) { 289 q.push(e.u); 290 d[e.u] = d[v] + 1; 291 } 292 } 293 } 294 return d[t] != -1; 295 } 296 297 T calc() { 298 T max_lim = numeric_limits<T>::max() / 2 + 1; 299 for (scaling_lim = scaling ? max_lim : 1; scaling_lim > 0; scaling_lim >>= 1) { 300 while (bfs()) { 301 fill(lst.begin(), lst.end(), 0); 302 T add; 303 while((add = dfs(s, numeric_limits<T>::max())) > 0) 304 flow += add; 305 } 306 } 307 return flow; 308 } 309 310 vector<bool> min_cut() { 311 vector<bool> res(n); 312 for(int i = 0; i < n; i++) 313 res[i] = (d[i] != -1); 314 return res; 315 } 316 }; 317 318 int main() { 319 int n; 320 cin >> n; 321 vector<int> a(n), b(n); 322 for(int i = 0; i < n; i++) 323 cin >> a[i]; 324 for(int i = 0; i < n; i++) 325 cin >> b[i]; 326 int s = n; 327 int t = n + 1; 328 dinic<int> d(n + 2, s, t, true); 329 vector<int> last(101, -1); 330 for(int i = 0; i < n; i++){ 331 if(b[i] > 0) 332 d.add_edge(s, i, b[i]); 333 if(b[i] < 0) 334 d.add_edge(i, t, -b[i]); 335 for(int k = 1; k <= 100; k++) 336 if(last[k] != -1 && a[i] % k == 0) 337 d.add_edge(i, last[k], int(1e9)); 338 last[a[i]] = i; 339 } 340 int sum = 0; 341 for(int i = 0; i < n; i++) 342 sum += max(0, b[i]); 343 cout << sum - d.calc() << endl; 344 } 345 ``` 346 347 [1473G - Tiles](/contest/1473/problem/G "Educational Codeforces Round 102 (Rated for Div. 2)") 348 349 Idea: [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic") 350 351 **Tutorial** 352 353 Tutorial is loading... 354 355 **Solution (Neon)** 356 357 ``` 358 #include <bits/stdc++.h> 359 360 using namespace std; 361 362 #define forn(i, n) for (int i = 0; i < int(n); ++i) 363 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 364 #define sz(a) int((a).size()) 365 366 template<const int &MOD> 367 struct _m_int { 368 int val; 369 370 _m_int(int64_t v = 0) { 371 if (v < 0) v = v % MOD + MOD; 372 if (v >= MOD) v %= MOD; 373 val = int(v); 374 } 375 376 _m_int(uint64_t v) { 377 if (v >= MOD) v %= MOD; 378 val = int(v); 379 } 380 381 _m_int(int v) : _m_int(int64_t(v)) {} 382 _m_int(unsigned v) : _m_int(uint64_t(v)) {} 383 384 static int inv_mod(int a, int m = MOD) { 385 int g = m, r = a, x = 0, y = 1; 386 387 while (r != 0) { 388 int q = g / r; 389 g %= r; swap(g, r); 390 x -= q * y; swap(x, y); 391 } 392 393 return x < 0 ? x + m : x; 394 } 395 396 explicit operator int() const { return val; } 397 explicit operator unsigned() const { return val; } 398 explicit operator int64_t() const { return val; } 399 explicit operator uint64_t() const { return val; } 400 explicit operator double() const { return val; } 401 explicit operator long double() const { return val; } 402 403 _m_int& operator+=(const _m_int &other) { 404 val -= MOD - other.val; 405 if (val < 0) val += MOD; 406 return *this; 407 } 408 409 _m_int& operator-=(const _m_int &other) { 410 val -= other.val; 411 if (val < 0) val += MOD; 412 return *this; 413 } 414 415 static unsigned fast_mod(uint64_t x, unsigned m = MOD) { 416 #if !defined(_WIN32) || defined(_WIN64) 417 return unsigned(x % m); 418 #endif 419 // Optimized mod for Codeforces 32-bit machines. 420 // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int. 421 unsigned x_high = unsigned(x >> 32), x_low = unsigned(x); 422 unsigned quot, rem; 423 asm("divl %4\n" 424 : "=a" (quot), "=d" (rem) 425 : "d" (x_high), "a" (x_low), "r" (m)); 426 return rem; 427 } 428 429 _m_int& operator*=(const _m_int &other) { 430 val = fast_mod(uint64_t(val) * other.val); 431 return *this; 432 } 433 434 _m_int& operator/=(const _m_int &other) { 435 return *this *= other.inv(); 436 } 437 438 friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; } 439 friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; } 440 friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; } 441 friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; } 442 443 _m_int& operator++() { 444 val = val == MOD - 1 ? 0 : val + 1; 445 return *this; 446 } 447 448 _m_int& operator--() { 449 val = val == 0 ? MOD - 1 : val - 1; 450 return *this; 451 } 452 453 _m_int operator++(int) { _m_int before = *this; ++*this; return before; } 454 _m_int operator--(int) { _m_int before = *this; --*this; return before; } 455 456 _m_int operator-() const { 457 return val == 0 ? 0 : MOD - val; 458 } 459 460 friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; } 461 friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; } 462 friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; } 463 friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; } 464 friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; } 465 friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; } 466 467 _m_int inv() const { 468 return inv_mod(val); 469 } 470 471 _m_int pow(int64_t p) const { 472 if (p < 0) 473 return inv().pow(-p); 474 475 _m_int a = *this, result = 1; 476 477 while (p > 0) { 478 if (p & 1) 479 result *= a; 480 a *= a; 481 p >>= 1; 482 } 483 484 return result; 485 } 486 487 friend string to_string(_m_int<MOD> x) { 488 return to_string(x.val); 489 } 490 491 friend ostream& operator<<(ostream &os, const _m_int &m) { 492 return os << m.val; 493 } 494 }; 495 496 extern const int MOD = 998244353; 497 using Mint = _m_int<MOD>; 498 499 const int g = 3; 500 const int LOGN = 15; 501 502 vector<Mint> w[LOGN]; 503 vector<int> rv[LOGN]; 504 505 void prepare() { 506 Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN)); 507 forn(st, LOGN - 1) { 508 w[st].assign(1 << st, 1); 509 Mint bw = wb.pow(1 << (LOGN - st - 1)); 510 Mint cw = 1; 511 forn(k, 1 << st) { 512 w[st][k] = cw; 513 cw *= bw; 514 } 515 } 516 forn(st, LOGN) { 517 rv[st].assign(1 << st, 0); 518 if (st == 0) { 519 rv[st][0] = 0; 520 continue; 521 } 522 int h = (1 << (st - 1)); 523 forn(k, 1 << st) 524 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 525 } 526 } 527 528 void ntt(vector<Mint> &a, bool inv) { 529 int n = sz(a); 530 int ln = __builtin_ctz(n); 531 forn(i, n) { 532 int ni = rv[ln][i]; 533 if (i < ni) swap(a[i], a[ni]); 534 } 535 forn(st, ln) { 536 int len = 1 << st; 537 for (int k = 0; k < n; k += (len << 1)) { 538 fore(pos, k, k + len){ 539 Mint l = a[pos]; 540 Mint r = a[pos + len] * w[st][pos - k]; 541 a[pos] = l + r; 542 a[pos + len] = l - r; 543 } 544 } 545 } 546 if (inv) { 547 Mint rn = Mint(n).inv(); 548 forn(i, n) a[i] *= rn; 549 reverse(a.begin() + 1, a.end()); 550 } 551 } 552 553 vector<Mint> mul(vector<Mint> a, vector<Mint> b) { 554 int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1)); 555 a.resize(cnt); 556 b.resize(cnt); 557 ntt(a, false); 558 ntt(b, false); 559 vector<Mint> c(cnt); 560 forn(i, cnt) c[i] = a[i] * b[i]; 561 ntt(c, true); 562 return c; 563 } 564 565 int main() { 566 prepare(); 567 568 vector<Mint> fact(1, 1), ifact(1, 1); 569 auto C = [&](int n, int k) -> Mint { 570 if (k < 0 || k > n) return 0; 571 while (sz(fact) <= n) { 572 fact.push_back(fact.back() * sz(fact)); 573 ifact.push_back(fact.back().inv()); 574 } 575 return fact[n] * ifact[k] * ifact[n - k]; 576 }; 577 578 int n; 579 cin >> n; 580 vector<int> a(n), b(n); 581 forn(i, n) cin >> a[i] >> b[i]; 582 583 vector<Mint> ans(1, 1); 584 forn(i, n) { 585 vector<Mint> Cs; 586 for (int j = b[i] - sz(ans) + 1; j < sz(ans) + a[i]; ++j) 587 Cs.push_back(C(a[i] + b[i], j)); 588 auto res = mul(ans, Cs); 589 int cnt = sz(ans); 590 ans.resize(cnt + a[i] - b[i]); 591 forn(j, sz(ans)) ans[j] = res[cnt + j - 1]; 592 } 593 594 cout << accumulate(ans.begin(), ans.end(), Mint(0)) << endl; 595 } 596 ```