1278.md (9699B)
1 Source: https://codeforces.com/blog/entry/72330 2 3 [1278A - Shuffle Hashing](/contest/1278/problem/A "Educational Codeforces Round 78 (Rated for Div. 2)") 4 5 Idea: [Neon](/profile/Neon "Candidate Master Neon") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (pikmike)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 #define forn(i, n) for (int i = 0; i < int(n); i++) 17 18 using namespace std; 19 20 string p, h; 21 22 bool read(){ 23 if (!(cin >> p >> h)) 24 return false; 25 return true; 26 } 27 28 void solve(){ 29 int n = h.size(); 30 vector<int> cntp(26); 31 forn(i, p.size()) 32 ++cntp[p[i] - 'a']; 33 forn(i, n){ 34 vector<int> cnth(26); 35 for (int j = i; j < n; ++j){ 36 ++cnth[h[j] - 'a']; 37 if (cntp == cnth){ 38 puts("YES"); 39 return; 40 } 41 } 42 } 43 puts("NO"); 44 } 45 46 int main() { 47 int tc; 48 scanf("%d", &tc); 49 forn(_, tc){ 50 read(); 51 solve(); 52 } 53 return 0; 54 } 55 ``` 56 57 **Solution 2 (pikmike)** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 #define forn(i, n) for (int i = 0; i < int(n); i++) 63 64 using namespace std; 65 66 const int AL = 26; 67 string p, h; 68 69 bool read(){ 70 if (!(cin >> p >> h)) 71 return false; 72 return true; 73 } 74 75 void solve(){ 76 vector<int> cntp(AL), cnt(AL); 77 vector<bool> eq(AL); 78 int sum = 0; 79 80 auto chg = [&cntp, &cnt, &eq, &sum](int c, int val){ 81 sum -= eq[c]; 82 cnt[c] += val; 83 eq[c] = (cntp[c] == cnt[c]); 84 sum += eq[c]; 85 }; 86 87 forn(i, p.size()) 88 ++cntp[p[i] - 'a']; 89 forn(i, AL){ 90 eq[i] = (cnt[i] == cntp[i]); 91 sum += eq[i]; 92 } 93 94 int m = p.size(); 95 int n = h.size(); 96 forn(i, n){ 97 chg(h[i] - 'a', 1); 98 if (i >= m) chg(h[i - m] - 'a', -1); 99 if (sum == AL){ 100 puts("YES"); 101 return; 102 } 103 } 104 105 puts("NO"); 106 } 107 108 int main() { 109 int tc; 110 scanf("%d", &tc); 111 forn(_, tc){ 112 read(); 113 solve(); 114 } 115 return 0; 116 } 117 ``` 118 119 [1278B - A and B](/contest/1278/problem/B "Educational Codeforces Round 78 (Rated for Div. 2)") 120 121 Idea: [Roms](/profile/Roms "Master Roms") 122 123 **Tutorial** 124 125 Tutorial is loading... 126 127 **Solution (Roms)** 128 129 ``` 130 #include <bits/stdc++.h> 131 132 using namespace std; 133 134 int t, a, b; 135 136 bool ok(int res, int d){ 137 long long sum = res * 1LL * (res + 1) / 2; 138 if(sum < d) return false; 139 return sum % 2 == d % 2; 140 } 141 142 int main() { 143 cin >> t; 144 for(int tc = 0; tc < t; ++tc){ 145 cin >> a >> b; 146 int d = abs(a - b); 147 if(d == 0){ 148 cout << "0\n"; 149 continue; 150 } 151 152 int res = 1; 153 while(!ok(res, d)) ++res; 154 cout << res << endl; 155 156 } 157 return 0; 158 } 159 ``` 160 161 [1278C - Berry Jam](/contest/1278/problem/C "Educational Codeforces Round 78 (Rated for Div. 2)") 162 163 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 164 165 **Tutorial** 166 167 Tutorial is loading... 168 169 **Solution (pikmike)** 170 171 ``` 172 #include <bits/stdc++.h> 173 174 #define forn(i, n) for (int i = 0; i < int(n); i++) 175 176 using namespace std; 177 178 int n; 179 vector<int> a; 180 181 bool read(){ 182 if (scanf("%d", &n) != 1) 183 return false; 184 a.resize(2 * n); 185 forn(i, 2 * n) 186 scanf("%d", &a[i]); 187 return true; 188 } 189 190 void solve(){ 191 int cur = 0; 192 map<int, int> difr; 193 194 difr[0] = 0; 195 cur = 0; 196 for (int i = n; i < 2 * n; ++i){ 197 if (a[i] == 1) 198 ++cur; 199 else 200 --cur; 201 if (!difr.count(cur)) 202 difr[cur] = i - (n - 1); 203 } 204 205 int ans = 2 * n; 206 int dif = count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 2); 207 208 cur = 0; 209 for (int i = n - 1; i >= 0; --i){ 210 if (a[i] == 1) 211 ++cur; 212 else 213 --cur; 214 if (difr.count(dif - cur)) 215 ans = min(ans, n - i + difr[dif - cur]); 216 } 217 if (difr.count(dif)){ 218 ans = min(ans, difr[dif]); 219 } 220 221 printf("%d\n", ans); 222 } 223 224 int main() { 225 int tc; 226 scanf("%d", &tc); 227 forn(_, tc){ 228 read(); 229 solve(); 230 } 231 return 0; 232 } 233 ``` 234 235 [1278D - Segment Tree](/contest/1278/problem/D "Educational Codeforces Round 78 (Rated for Div. 2)") 236 237 Idea: [Neon](/profile/Neon "Candidate Master Neon") 238 239 **Tutorial** 240 241 Tutorial is loading... 242 243 **Solution (Ne0n25)** 244 245 ``` 246 #include <bits/stdc++.h> 247 248 using namespace std; 249 250 #define x first 251 #define y second 252 #define mp make_pair 253 #define pb push_back 254 #define all(a) (a).begin(), (a).end() 255 #define forn(i, n) for (int i = 0; i < int(n); i++) 256 257 typedef long long li; 258 typedef pair<li, li> pt; 259 260 const int N = 500010; 261 262 int n; 263 pt a[N]; 264 vector<int> g[N]; 265 bool used[N]; 266 267 void dfs(int v, int p = -1) { 268 used[v] = true; 269 for (auto to : g[v]) if (to != p) { 270 if (!used[to]) 271 dfs(to, v); 272 } 273 } 274 275 int main() { 276 scanf("%d", &n); 277 forn(i, n) scanf("%d%d", &a[i].x, &a[i].y); 278 279 vector<pt> evs; 280 forn(i, n) { 281 evs.pb(mp(a[i].x, i)); 282 evs.pb(mp(a[i].y, i)); 283 } 284 285 sort(all(evs)); 286 287 int cnt = 0; 288 set<pt> cur; 289 for (auto it : evs) { 290 if (cnt >= n) break; 291 if (cur.count(it)) { 292 cur.erase(it); 293 } else { 294 int i = it.y; 295 int r = a[i].y; 296 for (auto jt : cur) { 297 if (jt.x > r) break; 298 int j = jt.y; 299 g[i].pb(j); 300 g[j].pb(i); 301 cnt++; 302 if (cnt >= n) break; 303 } 304 cur.insert(mp(a[i].y, i)); 305 } 306 } 307 308 dfs(0); 309 puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO"); 310 } 311 ``` 312 313 [1278E - Tests for problem D](/contest/1278/problem/E "Educational Codeforces Round 78 (Rated for Div. 2)") 314 315 Idea: [Neon](/profile/Neon "Candidate Master Neon") 316 317 **Tutorial** 318 319 Tutorial is loading... 320 321 **Solution (Ne0n25)** 322 323 ``` 324 #include <bits/stdc++.h> 325 326 using namespace std; 327 328 #define x first 329 #define y second 330 #define pb push_back 331 #define mp make_pair 332 #define all(a) (a).begin(), (a).end() 333 #define sz(a) int((a).size()) 334 #define forn(i, n) for (int i = 0; i < int(n); i++) 335 336 typedef pair<int, int> pt; 337 338 const int N = 500 * 1000 + 13; 339 340 int n; 341 vector<int> g[N], vs[N]; 342 pt segs[N]; 343 344 void dfs(int v, int p = -1) { 345 int sum = 0; 346 int bst = -1; 347 for (auto to : g[v]) if (to != p) { 348 dfs(to, v); 349 sum += 2 * sz(vs[to]); 350 if (bst == -1 || sz(vs[to]) > sz(vs[bst])) 351 bst = to; 352 } 353 354 if (bst == -1) { 355 vs[v].pb(v); 356 segs[v] = mp(1, 2); 357 return; 358 } 359 360 swap(vs[v], vs[bst]); 361 int lst = segs[bst].y; 362 363 sum -= 2 * sz(vs[v]); 364 sum += 1; 365 segs[bst].y += sum; 366 367 for (auto to : g[v]) if (to != p && to != bst) { 368 int add = lst - 1; 369 for (auto u : vs[to]) { 370 segs[u].x += add; 371 segs[u].y += add; 372 vs[v].pb(u); 373 } 374 lst = segs[to].y; 375 sum -= 2 * sz(vs[to]); 376 segs[to].y += sum; 377 vs[to].clear(); 378 } 379 380 vs[v].pb(v); 381 segs[v] = mp(lst, segs[bst].y + 1); 382 } 383 384 int main() { 385 scanf("%d", &n); 386 forn(i, n - 1) { 387 int x, y; 388 scanf("%d%d", &x, &y); 389 --x; --y; 390 g[x].pb(y); 391 g[y].pb(x); 392 } 393 394 dfs(0); 395 396 for (int i = 0; i < n; i++) 397 printf("%d %d\n", segs[i].x, segs[i].y); 398 399 return 0; 400 } 401 ``` 402 403 [1278F - Cards](/contest/1278/problem/F "Educational Codeforces Round 78 (Rated for Div. 2)") 404 405 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 406 407 **Tutorial** 408 409 ### [1278F - Cards](/contest/1278/problem/F "Educational Codeforces Round 78 (Rated for Div. 2)") 410 411 First of all, I would like to thank [Errichto](/profile/Errichto "International Grandmaster Errichto") for his awesome lecture on expected value: [part 1](https://codeforces.com/blog/entry/62690), [part 2](https://codeforces.com/blog/entry/62792). This problem was invented after I learned the concept of estimating the square of expected value from that lecture — and the editorial uses some ideas that were introduced there. 412 413 Okay, now for the editorial itself. We call a number $a$ as good if $1 \le a \le n$, and the $a$-th shuffle of the deck resulted in a joker on top. $x$ from our problem is the number of such good numbers $a$. We can represent $x^2$ as the number of pairs $(a_1, a_2)$ such that every element of the pair is a good number, $x^3$ as the number of triples, and so on — $x^k$ is the number of $k$-tuples $(a_1, a_2, \dots, a_k)$ such that each element of a tuple is a good number. 414 415 So we can rewrite the expected value of $x^k$ as the expected number of such tuples, or the sum of $P(t)$ over all tuples $t$, where $P(t)$ is the probability that $t$ consists of good numbers. How to calculate the probability that $t$ is a good tuple? Since all shuffles of the deck result in a joker with probability $\frac{1}{m}$, $P(t)$ should be equal to $\frac{1}{m^k}$ — but that is true only if all elements in $t$ are unique. How to deal with tuples with repeating elements? Since all occurences of the same element are either good or bad (with probability $\frac{1}{m}$ of being good), the correct formula for $P(t)$ is $P(t) = \frac{1}{m^d}$, where $d$ is the number of distinct elements in the tuple. 416 417 Okay, then for each $d \in [1, k]$ we have to calculate the number of $k$-tuples with exactly $d$ distinct elements. To do that, we use dynamic programming: let $dp_{i, j}$ be the number of $i$-tuples with exactly $j$ distinct elements. Each transition in this dynamic programming solution models adding an element to the tuple; if we want to compute the transitions leading from $dp_{i, j}$, we either add a new element to the tuple (there are $n - j$ ways to choose it, and we enter the state $dp_{i + 1, j + 1}$), or we add an already existing element (there are $j$ ways to choose it, and we enter the state $dp_{i + 1, j}$). 418 419 Overall complexity is $O(k^2 \log MOD)$ or $O(k^2 + \log MOD)$, depending on your implementation. 420 421 **Solution (BledDest)** 422 423 ``` 424 #include<bits/stdc++.h> 425 426 using namespace std; 427 428 const int MOD = 998244353; 429 const int N = 5043; 430 431 int add(int x, int y) 432 { 433 x += y; 434 while(x >= MOD) x -= MOD; 435 while(x < 0) x += MOD; 436 return x; 437 } 438 439 int mul(int x, int y) 440 { 441 return (x * 1ll * y) % MOD; 442 } 443 444 int binpow(int x, int y) 445 { 446 int z = 1; 447 while(y > 0) 448 { 449 if(y % 2 == 1) 450 z = mul(z, x); 451 x = mul(x, x); 452 y /= 2; 453 } 454 return z; 455 } 456 457 int inv(int x) 458 { 459 return binpow(x, MOD - 2); 460 } 461 462 int n, m, k; 463 464 int dp[N][N]; 465 466 int main() 467 { 468 cin >> n >> m >> k; 469 dp[0][0] = 1; 470 for(int i = 0; i < k; i++) 471 for(int j = 0; j < k; j++) 472 { 473 dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j)); 474 dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], n - j)); 475 } 476 int ans = 0; 477 for(int i = 1; i <= k; i++) 478 ans = add(ans, mul(dp[k][i], binpow(inv(m), i))); 479 cout << ans << endl; 480 } 481 ```