codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```