924.md (15121B)
1 Source: https://codeforces.com/blog/entry/58544 2 3 Long time no see! 4 5 As [VK Cup Round 2](//codeforces.com/contest/924) and its two parallel rounds ([Div. 1](//codeforces.com/contest/956) and [Div. 2](//codeforces.com/contest/957)) comes to a close, we're here to congratulate on all who did well on the contest and cheer for everyone who participated — the queue won't stop you! 6 7 Here are the detailed tutorials for the problems. Feel free to discuss in the comments! 8 9 Kudos to [arsor](/profile/arsor "Specialist arsor") for translating the tutorials into Russian! 10 11 --- 12 13 Tutorial is loading... 14 15 **Model solution** 16 17 ``` 18 _, s = input(), input() 19 print('Yes' if 20 ('??' in s or 'C?C' in s or 'M?M' in s or 'Y?Y' in s or s[0] == '?' or s[-1] == '?') and 21 not ('CC' in s or 'MM' in s or 'YY' in s) 22 else 'No') 23 ``` 24 25 **Alternative solution (Errichto)** 26 27 ``` 28 #include <bits/stdc++.h> 29 using namespace std; 30 31 void NO() { 32 puts("No"); 33 exit(0); 34 } 35 void YES() { 36 puts("Yes"); 37 exit(0); 38 } 39 40 int main() { 41 int n; 42 cin >> n; 43 string s; 44 cin >> s; 45 for(int i = 0; i < n - 1; ++i) 46 if(s[i] != '?' && s[i] == s[i+1]) 47 NO(); 48 for(int i = 0; i < n; ++i) if(s[i] == '?') { 49 if(i == 0 || i == n - 1) YES(); 50 if(s[i+1] == '?') YES(); 51 if(s[i-1] == s[i+1]) YES(); 52 } 53 NO(); 54 } 55 ``` 56 57 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")) 58 59 Tutorial is loading... 60 61 **Model solution** 62 63 ``` 64 #include <cstdio> 65 66 typedef long long int64; 67 static const int MAXN = 53; 68 69 static int n, m; 70 static bool a[MAXN][MAXN]; 71 static int64 b[MAXN]; 72 73 int main() 74 { 75 scanf("%d%d", &n, &m); getchar(); 76 for (int i = 0; i < n; ++i) 77 for (int j = 0; j <= m; ++j) a[i][j] = (getchar() == '#'); 78 79 for (int i = 0; i < n - 1; ++i) 80 for (int j = i + 1; j < n; ++j) { 81 bool all_same = true, no_intersect = true; 82 for (int k = 0; k < m; ++k) { 83 if (a[i][k] != a[j][k]) all_same = false; 84 if (a[i][k] && a[j][k]) no_intersect = false; 85 } 86 if (!all_same && !no_intersect) { 87 puts("No"); return 0; 88 } 89 } 90 91 puts("Yes"); return 0; 92 } 93 ``` 94 95 **Alternative solution with DSU in O(nm alpha(n)) (skywalkert)** 96 97 ``` 98 #include <bits/stdc++.h> 99 using namespace std; 100 const int maxn = 5001, maxm = maxn << 1 | 1; 101 int n, m, dsu[maxm], cB[maxm], cW[maxm], cE[maxm]; 102 char buf[maxn]; 103 int dsu_find(int u) { 104 return dsu[u] < 0 ? u : (dsu[u] = dsu_find(dsu[u])); 105 } 106 void dsu_merge(int u, int v) { 107 u = dsu_find(u); 108 v = dsu_find(v); 109 if(u == v) { 110 ++cE[u]; 111 return; 112 } 113 if(dsu[u] < dsu[v]) 114 swap(u, v); 115 dsu[v] -= dsu[u] == dsu[v]; 116 dsu[u] = v; 117 cB[v] += cB[u]; 118 cW[v] += cW[u]; 119 cE[v] += cE[u] + 1; 120 } 121 int main() { 122 scanf("%d%d", &n, &m); 123 memset(dsu, -1, (n + m) * sizeof(int)); 124 for(int i = 0; i < n; ++i) 125 cB[i] = 1; 126 for(int i = 0; i < m; ++i) 127 cW[n + i] = 1; 128 for(int i = 0; i < n; ++i) { 129 scanf("%s", buf); 130 for(int j = 0; j < m; ++j) 131 if(buf[j] != '.') 132 dsu_merge(i, n + j); 133 } 134 for(int i = 0; i < n + m; ++i) 135 if(dsu_find(i) == i && cB[i] * cW[i] != cE[i]) { 136 puts("No"); 137 return 0; 138 } 139 puts("Yes"); 140 return 0; 141 } 142 ``` 143 144 **Alternative solution in O(nm)** 145 146 ``` 147 #include <cstdio> 148 #include <algorithm> 149 #include <vector> 150 static const int MAXN = 1004; 151 152 static int n, m; 153 static bool g[MAXN][MAXN]; 154 // c[i] = set of rows where the i-th column is coloured 155 static std::vector<int> c[MAXN]; 156 static bool checked[MAXN] = { false }; 157 158 int main() 159 { 160 scanf("%d%d", &n, &m); getchar(); 161 for (int i = 0; i < n; ++i) 162 for (int j = 0; j <= m; ++j) { 163 g[i][j] = (getchar() == '#'); 164 if (g[i][j]) c[j].push_back(i); 165 } 166 167 for (int i = 0; i < n; ++i) if (!checked[i]) { 168 std::vector<int> r; 169 for (int j = 0; j < m; ++j) if (g[i][j]) 170 for (int k : c[j]) r.push_back(k); 171 std::sort(r.begin(), r.end()); 172 r.resize(std::unique(r.begin(), r.end()) - r.begin()); 173 174 for (int k : r) { 175 if (checked[k]) { puts("No"); return 0; } 176 checked[k] = true; 177 for (int p = 0; p < m; ++p) 178 if (g[i][p] != g[k][p]) { puts("No"); return 0; } 179 } 180 } 181 182 puts("Yes"); return 0; 183 } 184 ``` 185 186 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")) 187 188 Tutorial is loading... 189 190 **Model solution** 191 192 ``` 193 #include <iostream> 194 #include <sstream> 195 #include <cstdio> 196 #include <vector> 197 #include <cmath> 198 #include <queue> 199 #include <string> 200 #include <cstring> 201 #include <cassert> 202 #include <iomanip> 203 #include <algorithm> 204 #include <set> 205 #include <map> 206 #include <ctime> 207 #include <cmath> 208 209 #define forn(i, n) for(int i=0;i<n;++i) 210 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i) 211 #define sz(v) int(v.size()) 212 #define all(v) v.begin(), v.end() 213 #define pb push_back 214 #define mp make_pair 215 #define x first 216 #define y1 ________y1 217 #define y second 218 #define ft first 219 #define sc second 220 #define pt pair<int, int> 221 222 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; } 223 template<typename X> inline X sqr(const X& a) { return a * a; } 224 225 typedef long long li; 226 typedef long double ld; 227 228 using namespace std; 229 230 const int INF = 1000 * 1000 * 1000; 231 const ld EPS = 1e-9; 232 const ld PI = acos(-1.0); 233 234 const int N = 100 * 1000 + 13; 235 236 int n, u; 237 int a[N]; 238 int idx1 = -1, idx2, idx3; 239 240 inline void read() { 241 scanf("%d%d", &n, &u); 242 for (int i = 0; i < n; i++) { 243 scanf("%d", &a[i]); 244 } 245 } 246 247 inline void solve() { 248 int k = 0; 249 for (int i = 0; i < n; i++) { 250 k = max(k, i); 251 while (k + 1 < n && a[k + 1] - a[i] <= u) { 252 k++; 253 } 254 if (k - i - 1 <= 0) { 255 continue; 256 } 257 int j = i + 1; 258 259 if (idx1 == -1 || (a[k] - a[j]) * 1ll * (a[idx3] - a[idx1]) > (a[idx3] - a[idx2]) * 1ll * (a[k] - a[i])) { 260 idx1 = i, idx2 = j, idx3 = k; 261 } 262 } 263 264 if (idx1 == -1) { 265 cout << -1 << endl; 266 return; 267 } 268 269 cout.precision(20); 270 cout << (double)(a[idx3] - a[idx2]) / (a[idx3] - a[idx1]) << endl; 271 } 272 273 int main () { 274 #ifdef fcspartakm 275 freopen("input.txt", "r", stdin); 276 //freopen("output.txt", "w", stdout); 277 #endif 278 srand(time(NULL)); 279 cerr << setprecision(10) << fixed; 280 281 read(); 282 solve(); 283 284 //cerr << "TIME: " << clock() << endl; 285 } 286 ``` 287 288 (by [KAN](/profile/KAN "Grandmaster KAN"), prepared by [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")) 289 290 Tutorial is loading... 291 292 **Model solution** 293 294 ``` 295 #include <cstdio> 296 #include <algorithm> 297 298 typedef long long int64; 299 static const int MAXN = 1e5 + 4; 300 301 static int n, m[MAXN]; 302 static int t[MAXN]; 303 304 int main() 305 { 306 scanf("%d", &n); 307 for (int i = 0; i < n; ++i) scanf("%d", &m[i]); 308 309 for (int i = n - 1, cur = 0; i >= 0; --i) { 310 cur = std::max(0, cur - 1); 311 cur = std::max(cur, m[i] + 1); 312 t[i] = cur; 313 } 314 315 int64 ans = 0; 316 for (int i = 0, cur = 0; i < n; ++i) { 317 cur = std::max(cur, t[i]); 318 ans += cur; 319 } 320 321 for (int i = 0; i < n; ++i) ans -= (m[i] + 1); 322 printf("%lld\n", ans); 323 324 return 0; 325 } 326 ``` 327 328 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")) 329 330 Tutorial is loading... 331 332 **Model solution** 333 334 ``` 335 #include <cstdio> 336 #include <algorithm> 337 #include <utility> 338 339 typedef long long int64; 340 static const int MAXN = 1e5 + 4; 341 static const int MAXX = 1e8 + 4; 342 343 static int n, w; 344 static int x[MAXN], v[MAXN]; 345 346 struct fraction { 347 template <typename T> static inline T gcd(const T a, const T b) { 348 return (b == 0) ? a : gcd(b, a % b); 349 } 350 351 int64 num, deno; 352 inline void simplify() { 353 if (deno < 0) { num *= -1; deno *= -1; } 354 int64 g = gcd(num < 0 ? -num : num, deno); num /= g; deno /= g; 355 } 356 357 fraction() { } 358 fraction(int64 num, int64 deno) : num(num), deno(deno) { simplify(); } 359 360 inline bool operator < (const fraction &rhs) const { 361 return num * rhs.deno < deno * rhs.num; 362 } 363 inline bool operator != (const fraction &rhs) const { 364 return num * rhs.deno != deno * rhs.num; 365 } 366 }; 367 368 // Time bounds at which clouds can arrive at the origin 369 static std::pair<fraction, fraction> t[MAXN]; 370 // Used at discretization 371 static std::pair<fraction, int> d[MAXN]; 372 static int p[MAXN]; 373 374 struct bit { 375 static const int MAXN = ::MAXN; 376 int f[MAXN]; 377 bit() { std::fill(f, f + MAXN, 0); } 378 inline void add(int pos, int inc) { 379 for (++pos; pos < MAXN; pos += (pos & -pos)) f[pos] += inc; 380 } 381 inline int sum(int rg) { 382 int ans = 0; 383 for (++rg; rg; rg -= (rg & -rg)) ans += f[rg]; 384 return ans; 385 } 386 inline int sum(int lf, int rg) { 387 return sum(rg) - sum(lf - 1); 388 } 389 } arkady; 390 391 int main() 392 { 393 scanf("%d%d", &n, &w); 394 for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &v[i]); 395 396 for (int i = 0; i < n; ++i) { 397 int64 v1 = v[i] - w, v2 = v[i] + w; 398 t[i] = {fraction(-x[i], v1), fraction(-x[i], v2)}; 399 } 400 401 for (int i = 0; i < n; ++i) t[i].second.num *= -1; 402 std::sort(t, t + n); 403 for (int i = 0; i < n; ++i) t[i].second.num *= -1; 404 for (int i = 0; i < n; ++i) d[i] = {t[i].second, i}; 405 std::sort(d, d + n); 406 for (int i = 0, rk = -1; i < n; ++i) { 407 if (i == 0 || d[i].first != d[i - 1].first) ++rk; 408 p[d[i].second] = rk; 409 } 410 /*for (int i = 0; i < n; ++i) 411 printf("%.4lf %.4lf | %d\n", 412 (double)t[i].first.num / t[i].first.deno, 413 (double)t[i].second.num / t[i].second.deno, p[i]);*/ 414 415 int64 ans = 0; 416 for (int i = 0; i < n; ++i) { 417 ans += arkady.sum(p[i], MAXN - 1); 418 arkady.add(p[i], 1); 419 } 420 421 printf("%lld\n", ans); 422 423 return 0; 424 } 425 ``` 426 427 (by [KAN](/profile/KAN "Grandmaster KAN"), prepared by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")) 428 429 Tutorial is loading... 430 431 **Model solution** 432 433 ``` 434 /** 435 * This is a solution for problem wardrobe 436 * This is nk_ok.cpp 437 * 438 * @author: Nikolay Kalinin 439 * @date: Tue, 20 Mar 2018 21:48:33 +0300 440 */ 441 #include <bits/stdc++.h> 442 443 using namespace std; 444 445 using ll = long long; 446 using ld = long double; 447 using D = double; 448 using uint = unsigned int; 449 template<typename T> 450 using pair2 = pair<T, T>; 451 452 #ifdef WIN32 453 #define LLD "%I64d" 454 #else 455 #define LLD "%lld" 456 #endif 457 458 #define pb push_back 459 #define mp make_pair 460 #define all(x) (x).begin(),(x).end() 461 #define fi first 462 #define se second 463 464 struct tbox 465 { 466 int h, t; 467 }; 468 469 inline bool operator<(const tbox &a, const tbox &b) 470 { 471 if (a.t != b.t) return a.t < b.t; 472 return a.h > b.h; 473 } 474 475 const int maxn = 10005; 476 const int inf = 1e9; 477 478 tbox b[maxn]; 479 int ans[maxn]; 480 int n, l, r; 481 482 int main() 483 { 484 scanf("%d%d%d", &n, &l, &r); 485 int sumh = 0; 486 for (int i = 0; i < n; i++) 487 { 488 scanf("%d", &b[i].h); 489 sumh += b[i].h; 490 } 491 tie(l, r) = pair{sumh - r, sumh - l}; 492 for (int i = 0; i < n; i++) scanf("%d", &b[i].t); 493 sort(b, b + n); 494 for (int i = 0; i <= sumh; i++) ans[i] = -inf; 495 ans[0] = 0; 496 for (int i = 0; i < n; i++) 497 { 498 for (int h = sumh - b[i].h; h >= 0; h--) ans[h + b[i].h] = max(ans[h + b[i].h], ans[h] + b[i].t * (h + b[i].h >= l && h + b[i].h <= r)); 499 } 500 cout << *max_element(ans, ans + sumh + 1) << endl; 501 return 0; 502 } 503 ``` 504 505 (by [KAN](/profile/KAN "Grandmaster KAN")) 506 507 Tutorial is loading... 508 509 **Model solution** 510 511 ``` 512 #include <bits/stdc++.h> 513 using namespace std; 514 typedef long long LL; 515 const int maxd = 10, maxl = 18, maxs = 81, BLEN = 5, BMSK = 31; 516 struct States { 517 vector<LL> keys, vals[maxd + 1]; 518 void insert(LL key) { 519 keys.push_back(key); 520 } 521 void initialize(LL val = 0) { 522 sort(keys.begin(), keys.end()); 523 keys.erase(unique(keys.begin(), keys.end()), keys.end()); 524 for(int i = 0; i < maxd; ++i) 525 vals[i].assign(keys.size(), val); 526 } 527 void summation() { 528 for(int i = 1; i < maxd; ++i) 529 for(vector<LL>::iterator it = vals[i - 1].begin(), jt = vals[i].begin(); jt != vals[i].end(); ++it, ++jt) 530 *jt += *it; 531 } 532 size_t size() const { 533 return keys.size(); 534 } 535 void update(int upp, LL key, LL adt) { 536 vals[upp][lower_bound(keys.begin(), keys.end(), key) - keys.begin()] += adt; 537 } 538 LL find(int upp, LL key) { 539 vector<LL>::iterator it = lower_bound(keys.begin(), keys.end(), key); 540 if(it == keys.end() || *it != key) 541 return 0; 542 return vals[upp][it - keys.begin()]; 543 } 544 } f[maxd + 1][maxl + 1]; 545 LL c[2][maxl + 1], bit[maxd + 1]; 546 bitset<maxs + 1> vis[maxd + 1]; 547 void dfs(int dep, int cnt, int sum, LL msk) { 548 if(dep == maxd) { 549 for(int i = sum >> 1; i >= 0; --i) 550 if(vis[dep - 1].test(i)) { 551 int dif = sum - i - i; 552 if(dif > 1) 553 f[dif][0].insert(msk); 554 break; 555 } 556 return; 557 } 558 vis[dep] = vis[dep - 1]; 559 dfs(dep + 1, cnt, sum, msk); 560 while(cnt < maxl) { 561 vis[dep] |= vis[dep] << dep; 562 dfs(dep + 1, ++cnt, sum += dep, msk += bit[dep]); 563 } 564 } 565 LL solve(int dif, LL lim) { 566 char dig[maxl + 3]; 567 int len = sprintf(dig, "%lld", lim); 568 LL ret = 0, msk = 0; 569 States *F = f[dif]; 570 for(int i = 0; i < len; ++i) { 571 dig[i] -= '0'; 572 if(len - i > maxl) { 573 for(int j = 0; j < dig[i]; ++j) 574 ret += F[len - i - 1].find(maxd - 1, msk); 575 } else if(dig[i]) { 576 ret += F[len - i].find(dig[i] - 1, msk); 577 msk += bit[dig[i]]; 578 } 579 } 580 return ret; 581 } 582 LL solve2(LL lim) { 583 char dig[maxl + 3]; 584 int len = sprintf(dig, "%lld", lim), part = 0; 585 LL ret = 0; 586 for(int i = 0; i < len; ++i) { 587 dig[i] -= '0'; 588 int odd = dig[i] >> 1, even = (dig[i] + 1) >> 1; 589 ret += c[part][len - 1 - i] * odd + c[part ^ 1][len - 1 - i] * even; 590 part ^= dig[i] & 1; 591 } 592 return ret; 593 } 594 int main() { 595 c[0][0] = 1; 596 for(int i = 0; i < maxl; ++i) { 597 int odd = maxd >> 1, even = (maxd + 1) >> 1; 598 c[0][i + 1] = c[0][i] * even + c[1][i] * odd; 599 c[1][i + 1] = c[0][i] * odd + c[1][i] * even; 600 } 601 bit[1] = 1; 602 for(int i = 2; i < maxd; ++i) 603 bit[i] = bit[i - 1] << BLEN; 604 vis[0].set(0); 605 dfs(1, 0, 0, 0); 606 for(int i = 2; i < maxd; ++i) { 607 f[i][0].initialize(1); 608 for(int j = 0; j < maxl; ++j) { 609 States &cur = f[i][j], &nxt = f[i][j + 1]; 610 for(int idx = 0, sz = cur.size(); idx < sz; ++idx) { 611 int cnt = j; 612 LL msk = cur.keys[idx], tmp = msk; 613 for(int k = 1; k < maxd; ++k, tmp >>= BLEN) { 614 int rem = tmp & BMSK; 615 if(!rem) 616 continue; 617 cnt += rem; 618 nxt.insert(msk - bit[k]); 619 } 620 if(cnt < maxl) 621 nxt.insert(msk); 622 } 623 nxt.initialize(0); 624 for(int idx = 0, sz = cur.size(); idx < sz; ++idx) { 625 int cnt = j; 626 LL msk = cur.keys[idx], ways = cur.vals[maxd - 1][idx], tmp = msk; 627 for(int k = 1; k < maxd; ++k, tmp >>= BLEN) { 628 int rem = tmp & BMSK; 629 if(!rem) 630 continue; 631 cnt += rem; 632 nxt.update(k, msk - bit[k], ways); 633 } 634 if(cnt < maxl) 635 nxt.update(0, msk, ways); 636 } 637 nxt.summation(); 638 } 639 } 640 int t; 641 scanf("%d", &t); 642 for(int Case = 1; Case <= t; ++Case) { 643 LL L, R; 644 int k; 645 scanf("%lld%lld%d", &L, &R, &k); 646 LL ans = R + 1 - L; 647 if(!k) { 648 ans -= solve2(R + 1) - solve2(L); 649 for(int i = 2; i < maxd; i += 2) 650 ans -= solve(i, R + 1) - solve(i, L); 651 } else { 652 for(int i = k + 1; i < maxd; ++i) 653 ans -= solve(i, R + 1) - solve(i, L); 654 } 655 printf("%lld\n", ans); 656 } 657 return 0; 658 } 659 ``` 660 661 (by [Claris](/profile/Claris "International Master Claris") and [skywalkert](/profile/skywalkert "Master skywalkert")) 662 663 --- 664 665 My gratitude to the coordinators, problem authors, testers, and every participant. You made all this possible! Cheers \(^ ^)/