codeforces-scrape

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

1187.md (11085B)


      1 Source: https://codeforces.com/blog/entry/68111
      2 
      3 [1187A - Stickers and Toys](/contest/1187/problem/A "Educational Codeforces Round 67 (Rated for Div. 2)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main(args: Array<String>) {
     15     val tc = readLine()!!.toInt()
     16     for (i in 1..tc) {
     17         val (n, s, t) = readLine()!!.split(' ').map { it.toInt() }
     18         println(maxOf(n - s, n - t) + 1)
     19     }
     20 }
     21 ```
     22 
     23 [1187B - Letters Shop](/contest/1187/problem/B "Educational Codeforces Round 67 (Rated for Div. 2)")
     24 
     25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (PikMike)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 
     36 #define forn(i, n) for (int i = 0; i < int(n); i++)
     37 
     38 using namespace std;
     39 
     40 int n, m;
     41 string s, t;
     42 vector<int> pos[26];
     43 
     44 int main() {
     45 	cin >> n >> s;
     46 	forn(i, n)
     47 		pos[s[i] - 'a'].push_back(i + 1);
     48 	
     49 	cin >> m;
     50 	forn(i, m){
     51 		cin >> t;
     52 		vector<int> cnt(26);
     53 		for (auto &c : t)
     54 			++cnt[c - 'a'];
     55 		int ans = -1;
     56 		forn(j, 26) if (cnt[j] > 0)
     57 			ans = max(ans, pos[j][cnt[j] - 1]);
     58 		cout << ans << "\n";
     59 	}
     60 	return 0;
     61 }
     62 ```
     63 
     64 [1187C - Vasya And Array](/contest/1187/problem/C "Educational Codeforces Round 67 (Rated for Div. 2)")
     65 
     66 Idea: [Roms](/profile/Roms "Master Roms")
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution (Roms)**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 
     77 using namespace std;
     78 
     79 const int N = int(3e5) + 99;
     80 
     81 int n, m;
     82 int l[N], r[N], s[N];
     83 int d[N];
     84 int dx[N];
     85 int res[N];
     86 int nxt[N];
     87 
     88 int main() {
     89 	scanf("%d %d", &n, &m);
     90 	for(int i = 0; i < m; ++i){
     91 		scanf("%d %d %d", s + i, l + i, r + i);
     92 		--l[i], --r[i];
     93 		if(s[i] == 1)
     94 			++d[l[i]], --d[r[i]];
     95 	}
     96 
     97 	memset(dx, -1, sizeof dx);
     98 	int sum = 0;
     99 	for(int i = 0; i < n - 1; ++i){
    100 		sum += d[i];
    101 		if(sum > 0)	
    102 			dx[i] = 0;
    103 	}		
    104 
    105 	res[0] = n;
    106 	for(int i = 1; i < n; ++i)
    107 		res[i] = res[i - 1] + dx[i - 1];	
    108 
    109 	nxt[n - 1] = n - 1;
    110 	for(int i = n - 2; i >= 0; --i){
    111 		if(res[i] <= res[i + 1])
    112 			nxt[i] = nxt[i + 1];
    113 		else 
    114 			nxt[i] = i;
    115 	}			
    116 
    117 	for(int i = 0; i < m; ++i){
    118 		if(s[i] != (nxt[l[i]] >= r[i])){
    119 			puts("NO");
    120 			return 0;		
    121 		}
    122 	}	
    123 
    124 	puts("YES");
    125 	for(int i = 0; i < n; ++i)
    126 		printf("%d ", res[i]);
    127 	puts("");
    128 
    129 	return 0;
    130 }                             	
    131 ```
    132 
    133 [1187D - Subarray Sorting](/contest/1187/problem/D "Educational Codeforces Round 67 (Rated for Div. 2)")
    134 
    135 Idea: [Roms](/profile/Roms "Master Roms")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution (Roms)**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145 
    146 using namespace std;
    147 
    148 const int N = int(3e5) + 99;
    149 const int INF = int(1e9) + 99;
    150 
    151 int t, n;
    152 int a[N], b[N];
    153 vector <int> p[N];
    154 int st[4 * N + 55];
    155 
    156 int getMin(int v, int l, int r, int L, int R){
    157 	if(L >= R) return INF;
    158 	if(l == L && r == R)
    159 		return st[v];
    160 
    161 	int mid = (l + r) / 2;
    162 	return min(getMin(v * 2 + 1, l, mid, L, min(R, mid)),
    163 		getMin(v * 2 + 2, mid, r, max(mid, L), R));	
    164 }
    165 
    166 void upd(int v, int l, int r, int pos, int x){
    167 	if(r - l == 1){
    168 		st[v] = x;
    169 		return;
    170 	}
    171 
    172 	int mid = (l + r) / 2;
    173 	if(pos < mid) upd(v * 2 + 1, l, mid, pos, x);
    174 	else upd(v * 2 + 2, mid, r, pos, x);
    175 		
    176 	st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
    177 }
    178 
    179 int main() {
    180 	scanf("%d", &t);
    181 	for(int tc = 0; tc < t; ++tc){
    182 		scanf("%d", &n);
    183 		for(int i = 0; i < n; ++i)
    184 			p[i].clear();					
    185 		for(int i = 0; i < n; ++i){
    186 			scanf("%d", a + i);
    187 			--a[i];
    188 			p[a[i]].push_back(i);	
    189 		}	
    190 		for(int i = 0; i < n; ++i){
    191 			scanf("%d", b + i);	
    192 			--b[i];		
    193 		}
    194 
    195 		for(int i = 0; i < 4 * n; ++i) st[i] = INF;
    196 		for(int i = 0; i < n; ++i){
    197 			reverse(p[i].begin(), p[i].end());
    198 			if(!p[i].empty()) upd(0, 0, n, i, p[i].back());
    199 		}
    200 
    201 		bool ok = true;
    202 		for(int i = 0; i < n; ++i){
    203 			if(p[b[i]].empty()){
    204 				ok = false;
    205 				break;
    206 			}
    207 
    208 			int pos = p[b[i]].back();
    209 			if(getMin(0, 0, n, 0, b[i]) < pos){
    210 				ok = false;
    211 				break;
    212 			}
    213 
    214 			p[b[i]].pop_back();
    215 			upd(0, 0, n, b[i], p[b[i]].empty()? INF : p[b[i]].back());			
    216 		}
    217 
    218 		if(ok) puts("YES");
    219 		else puts("NO");
    220 	}	
    221 	
    222 	return 0;
    223 }
    224 ```
    225 
    226 [1187E - Tree Painting](/contest/1187/problem/E "Educational Codeforces Round 67 (Rated for Div. 2)")
    227 
    228 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Solution (Vovuh)**
    235 
    236 ```
    237 #include <bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 int n;
    242 long long ans;
    243 vector<int> siz;
    244 vector<long long> dp;
    245 vector<vector<int>> g;
    246 
    247 int calcsize(int v, int p = -1) {
    248 	siz[v] = 1;
    249 	for (auto to : g[v]) {
    250 		if (to == p) continue;
    251 		siz[v] += calcsize(to, v);
    252 	}
    253 	return siz[v];
    254 }
    255 
    256 long long calcdp(int v, int p = -1) {
    257 	dp[v] = siz[v];
    258 	for (auto to : g[v]) {
    259 		if (to == p) continue;
    260 		dp[v] += calcdp(to, v);
    261 	}
    262 	return dp[v];
    263 }
    264 
    265 void dfs(int v, int p = -1) {
    266 	ans = max(ans, dp[v]);
    267 	for (auto to : g[v]) {
    268 		if (to == p) continue;
    269 		
    270 		dp[v] -= dp[to];
    271 		dp[v] -= siz[to];
    272 		siz[v] -= siz[to];
    273 		siz[to] += siz[v];
    274 		dp[to] += siz[v];
    275 		dp[to] += dp[v];
    276 		
    277 		dfs(to, v);
    278 		
    279 		dp[to] -= dp[v];
    280 		dp[to] -= siz[v];
    281 		siz[to] -= siz[v];
    282 		siz[v] += siz[to];
    283 		dp[v] += siz[to];
    284 		dp[v] += dp[to];
    285 	}
    286 }
    287 
    288 int main() {
    289 #ifdef _DEBUG
    290 	freopen("input.txt", "r", stdin);
    291 //	freopen("output.txt", "w", stdout);
    292 #endif
    293 	
    294 	cin >> n;
    295 	g = vector<vector<int>>(n);
    296 	for (int i = 0; i < n - 1; ++i) {
    297 		int x, y;
    298 		cin >> x >> y;
    299 		--x, --y;
    300 		g[x].push_back(y);
    301 		g[y].push_back(x);
    302 	}
    303 	
    304 	ans = 0;
    305 	siz = vector<int>(n);
    306 	dp = vector<long long>(n);
    307 	
    308 	calcsize(0);
    309 	calcdp(0);
    310 	dfs(0);
    311 	
    312 	cout << ans << endl;
    313 	
    314 	return 0;
    315 }
    316 ```
    317 
    318 **Alternative solution (PikMike)**
    319 
    320 ```
    321 #include <bits/stdc++.h>
    322 
    323 #define forn(i, n) for (int i = 0; i < int(n); i++)
    324 
    325 typedef long long li;
    326 
    327 using namespace std;
    328 
    329 const int N = 200 * 1000 + 13;
    330 
    331 int n;
    332 vector<int> g[N];
    333 
    334 int siz[N];
    335 li sum[N];
    336 
    337 void init(int v, int p = -1){
    338 	siz[v] = 1;
    339 	sum[v] = 0;
    340 	for (auto u : g[v]) if (u != p){
    341 		init(u, v);
    342 		siz[v] += siz[u];
    343 		sum[v] += sum[u];
    344 	}
    345 	sum[v] += (siz[v] - 1);
    346 }
    347 
    348 li dp[N];
    349 
    350 void dfs(int v, int p = -1){
    351 	dp[v] = 0;
    352 	li tot = 0;
    353 	for (auto u : g[v]) if (u != p)
    354 		tot += sum[u];
    355 	for (auto u : g[v]) if (u != p){
    356 		dfs(u, v);
    357 		dp[v] = max(dp[v], (n - siz[u] - 1) + dp[u] + (tot - sum[u]));
    358 	}
    359 	if (g[v].size() == 1){
    360 		dp[v] = n - 1;
    361 	}
    362 }
    363 
    364 int main() {
    365 	scanf("%d", &n);
    366 	forn(i, n - 1){
    367 		int v, u;
    368 		scanf("%d%d", &v, &u);
    369 		--v, --u;
    370 		g[v].push_back(u);
    371 		g[u].push_back(v);
    372 	}
    373 	
    374 	if (n == 2) {
    375 		cout << 3 << endl;
    376 		return 0;
    377 	}
    378 	
    379 	forn(i, n) if (int(g[i].size()) > 1){
    380 		init(i);
    381 		dfs(i);
    382 		printf("%lld\n", dp[i] + n);
    383 		break;
    384 	}
    385 	
    386 	return 0;
    387 }
    388 ```
    389 
    390 [1187F - Expected Square Beauty](/contest/1187/problem/F "Educational Codeforces Round 67 (Rated for Div. 2)")
    391 
    392 Idea: [Roms](/profile/Roms "Master Roms") and [adedalic](/profile/adedalic "International Master adedalic")
    393 
    394 **Tutorial**
    395 
    396 Tutorial is loading...
    397 
    398 **Solution (adedalic)**
    399 
    400 ```
    401 #include<bits/stdc++.h>
    402 
    403 using namespace std;
    404 
    405 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    406 #define sz(a) int((a).size())
    407 
    408 #define x first
    409 #define y second
    410 
    411 typedef long long li;
    412 typedef pair<int, int> pt;
    413 
    414 const int MOD = int(1e9) + 7;
    415 
    416 int norm(int a) {
    417 	while(a >= MOD) a -= MOD;
    418 	while(a < 0) a += MOD;
    419 	return a;
    420 }
    421 int mul(int a, int b) {
    422 	return int(a * 1ll * b % MOD);
    423 }
    424 int binPow(int a, int k) {
    425 	int ans = 1;
    426 	for(; k > 0; k >>= 1) {
    427 		if(k & 1)
    428 			ans = mul(ans, a);
    429 		a = mul(a, a);
    430 	}
    431 	return ans;
    432 }
    433 int inv(int a) {
    434 	int b = binPow(a, MOD - 2);
    435 	assert(mul(a, b) == 1);
    436 	return b;
    437 }
    438 
    439 int n;
    440 vector<int> l, r;
    441 
    442 inline bool read() {
    443 	if(!(cin >> n))
    444 		return false;
    445 	l.resize(n);
    446 	r.resize(n);
    447 	
    448 	fore(i, 0, n)
    449 		cin >> l[i];
    450 	fore(i, 0, n) {
    451 		cin >> r[i];
    452 		r[i]++;
    453 	}
    454 	return true;
    455 }
    456 
    457 vector<int> p;
    458 
    459 int calcEq(int i0) { 
    460 	int i1 = i0 + 1;
    461 	int pSame = 0;
    462 	if(i0 > 0) {
    463 		int cnt = max(0, min({r[i0 - 1], r[i0], r[i1]}) - max({l[i0 - 1], l[i0], l[i1]}));
    464 		pSame = mul(cnt, inv(mul(mul(r[i0 - 1] - l[i0 - 1], r[i0] - l[i0]), r[i1] - l[i1])));
    465 	}
    466 	return norm(1 - norm(2 - p[i0] - p[i1]) + pSame);
    467 }
    468 
    469 inline void solve() {
    470 	p.assign(n, 0);
    471 	p[0] = 1;
    472 	fore(i, 1, n) {
    473 		int cnt = max(0, min(r[i - 1], r[i]) - max(l[i - 1], l[i]));
    474 		p[i] = norm(1 - mul(cnt, inv(mul(r[i - 1] - l[i - 1], r[i] - l[i]))));
    475 	}
    476 	
    477 	int sum = 0;
    478 	fore(i, 0, n)
    479 		sum = norm(sum + p[i]);
    480 	
    481 	int ans = 0;
    482 	fore(i, 0, n) {
    483 		int curS = sum;
    484 		for(int j = max(0, i - 1); j < min(n, i + 2); j++)
    485 			curS = norm(curS - p[j]);
    486 		
    487 		ans = norm(ans + mul(p[i], curS));
    488 		
    489 		if(i > 0)
    490 			ans = norm(ans + calcEq(i - 1));
    491 		ans = norm(ans + p[i]);
    492 		if(i + 1 < n)
    493 			ans = norm(ans + calcEq(i));
    494 	}
    495 	
    496 	cout << ans << endl;
    497 }
    498 
    499 int main() {
    500 #ifdef _DEBUG
    501 	freopen("input.txt", "r", stdin);
    502 	int tt = clock();
    503 #endif
    504 	ios_base::sync_with_stdio(false);
    505 	cin.tie(0), cout.tie(0);
    506 	cout << fixed << setprecision(15);
    507 	
    508 	if(read()) {
    509 		solve();
    510 		
    511 #ifdef _DEBUG
    512 		cerr << "TIME = " << clock() - tt << endl;
    513 		tt = clock();
    514 #endif
    515 	}
    516 	return 0;
    517 }
    518 ```
    519 
    520 [1187G - Gang Up](/contest/1187/problem/G "Educational Codeforces Round 67 (Rated for Div. 2)")
    521 
    522 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    523 
    524 **Tutorial**
    525 
    526 Tutorial is loading...
    527 
    528 **Solution (BledDest)**
    529 
    530 ```
    531 #include<bits/stdc++.h>
    532 
    533 using namespace std;
    534 
    535 struct edge
    536 {
    537 	int y, c, f, cost;
    538 	edge() {};
    539 	edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
    540 };
    541 
    542 vector<edge> e;
    543 
    544 const int N = 14043;
    545 vector<int> g[N];
    546 
    547 long long ans = 0;
    548 long long d[N];
    549 int p[N];
    550 int pe[N];
    551 int inq[N];
    552 
    553 const long long INF64 = (long long)(1e18);
    554 
    555 int s = N - 2;
    556 int t = N - 1;
    557 
    558 int rem(int x)
    559 {
    560 	return e[x].c - e[x].f;
    561 }
    562 
    563 void push_flow()
    564 {
    565 	for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0;
    566 	d[s] = 0;
    567 	queue<int> q;
    568 	q.push(s);
    569 	inq[s] = 1;
    570 	while(!q.empty())
    571 	{
    572 		int k = q.front();
    573 		q.pop();
    574 		inq[k] = 0;
    575 		for(auto x : g[k])
    576 		{
    577 			if(!rem(x)) continue;
    578 			int c = e[x].cost;
    579 			int y = e[x].y;
    580 			if(d[y] > d[k] + c)
    581 			{
    582 				d[y] = d[k] + c;
    583 				p[y] = k;
    584 				pe[y] = x;
    585 				if(inq[y] == 0)
    586 				{
    587 					inq[y] = 1;
    588 					q.push(y);
    589 				}
    590 			}
    591 		}
    592 	}
    593 	int cur = t;
    594 //	vector<int> zz(1, cur);
    595 	while(cur != s)
    596 	{
    597 		e[pe[cur]].f++;
    598 		e[pe[cur] ^ 1].f--;
    599 		cur = p[cur];
    600 //		zz.push_back(cur);
    601 	}
    602 //	reverse(zz.begin(), zz.end());
    603 //	for(auto x : zz) cerr << x << " ";
    604 //	cerr << endl;
    605 	ans += d[t];
    606 }
    607 
    608 void add_edge(int x, int y, int c, int cost)
    609 {
    610 	g[x].push_back(e.size());
    611 	e.push_back(edge(y, c, 0, cost));
    612 	g[y].push_back(e.size());
    613 	e.push_back(edge(x, 0, 0, -cost));
    614 }
    615 
    616 int main()
    617 {
    618 	int n, m, k, c, d;
    619 	cin >> n >> m >> k >> c >> d;
    620 	for(int i = 0; i < k; i++)
    621 	{
    622 		int x;
    623 		cin >> x;
    624 		--x;
    625 		add_edge(s, x, 1, 0);
    626 	}
    627 	int tt = 101;
    628 	for(int i = 0; i < tt; i++)
    629 		add_edge(0 + i * n, t, k, i * c);
    630 	for(int i = 0; i < m; i++)
    631 	{
    632 		int x, y;
    633 		cin >> x >> y;
    634 		--x;
    635 		--y;
    636 		for(int i = 0; i < tt - 1; i++)
    637 			for(int j = 0; j < k; j++)
    638 				add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1));
    639 		for(int i = 0; i < tt - 1; i++)
    640 			for(int j = 0; j < k; j++)
    641 				add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1));
    642  	}
    643  	for(int i = 0; i < n; i++)
    644  		for(int j = 0; j < tt - 1; j++)
    645  			add_edge(i + j * n, i + j * n + n, k, 0);
    646  	for(int i = 0; i < k; i++)
    647  		push_flow();
    648  	cout << ans << endl;
    649 }
    650 ```