codeforces-scrape

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

1389.md (10241B)


      1 Source: https://codeforces.com/blog/entry/80809
      2 
      3 [1389A - LCM Problem](/contest/1389/problem/A "Educational Codeforces Round 92 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     l, r = map(int, input().split())
     17     if l * 2 > r:
     18         print(-1, -1)
     19     else:
     20         print(l, l * 2)
     21 ```
     22 
     23 [1389B - Array Walk](/contest/1389/problem/B "Educational Codeforces Round 92 (Rated for Div. 2)")
     24 
     25 Idea: [Roms](/profile/Roms "Master Roms")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution 1 (pikmike)**
     32 
     33 ```
     34 for _ in range(int(input())):
     35 	n, k, z = map(int, input().split())
     36 	a = [int(x) for x in input().split()]
     37 	ans = 0
     38 	s = 0
     39 	mx = 0
     40 	for t in range(z + 1):
     41 		pos = k - 2 * t
     42 		if pos < 0:
     43 			continue
     44 		mx = 0
     45 		s = 0
     46 		for i in range(pos + 1):
     47 			if i < n - 1:
     48 				mx = max(mx, a[i] + a[i + 1])
     49 			s += a[i]
     50 		ans = max(ans, s + mx * t)
     51 	print(ans)
     52 ```
     53 
     54 **Solution 2 (pikmike)**
     55 
     56 ```
     57 for _ in range(int(input())):
     58 	n, k, z = map(int, input().split())
     59 	a = [int(x) for x in input().split()]
     60 	ans = 0
     61 	s = 0
     62 	mx = 0
     63 	for i in range(k + 1):
     64 		if i < n - 1:
     65 			mx = max(mx, a[i] + a[i + 1])
     66 		s += a[i]
     67 		if i % 2 == k % 2:
     68 			tmp = (k - i) // 2
     69 			if tmp <= z:
     70 				ans = max(ans, s + mx * tmp)
     71 	print(ans)
     72 ```
     73 
     74 [1389C - Good String](/contest/1389/problem/C "Educational Codeforces Round 92 (Rated for Div. 2)")
     75 
     76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (Ne0n25)**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 
     87 using namespace std;
     88 
     89 #define sz(a) int((a).size())
     90 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     91 
     92 int solve(const string& s, int x, int y) {
     93 	int res = 0;
     94 	for (auto c : s) if (c - '0' == x) {
     95 		++res;
     96 		swap(x, y);
     97 	}
     98 	if (x != y && res % 2 == 1)
     99 		--res;
    100 	return res;
    101 }
    102 
    103 void solve() {
    104 	string s;
    105 	cin >> s;
    106 	int ans = 0;
    107 	forn(x, 10) forn(y, 10)
    108 		ans = max(ans, solve(s, x, y));
    109 	cout << sz(s) - ans << endl;
    110 }
    111 
    112 int main() {
    113 	int T;
    114 	cin >> T;
    115 	while (T--) solve();
    116 }
    117 ```
    118 
    119 [1389D - Segment Intersections](/contest/1389/problem/D "Educational Codeforces Round 92 (Rated for Div. 2)")
    120 
    121 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution (adedalic)**
    128 
    129 ```
    130 import kotlin.math.*
    131 
    132 fun main() {
    133     repeat(readLine()!!.toInt()) {
    134         val (n, k) = readLine()!!.split(' ').map { it.toLong() }
    135         val (l1, r1) = readLine()!!.split(' ').map { it.toLong() }
    136         val (l2, r2) = readLine()!!.split(' ').map { it.toLong() }
    137 
    138         var ans = 1e18.toLong()
    139         if (max(l1, l2) <= min(r1, r2)) {
    140             val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2)))
    141             val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2))
    142             ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2
    143         } else {
    144             val invest = max(l1, l2) - min(r1, r2)
    145             for (cntInv in 1..n) {
    146                 var curAns = invest * cntInv
    147                 val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv
    148                 curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2
    149                 ans = min(ans, curAns)
    150             }
    151         }
    152         println(ans)
    153     }
    154 }
    155 ```
    156 
    157 [1389E - Calendar Ambiguity](/contest/1389/problem/E "Educational Codeforces Round 92 (Rated for Div. 2)")
    158 
    159 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    160 
    161 **Tutorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Solution (pikmike)**
    166 
    167 ```
    168 fun gcd(a: Long, b: Long): Long {
    169 	if (a == 0L) return b
    170 	return gcd(b % a, a)
    171 }
    172 
    173 fun main() {
    174 	repeat(readLine()!!.toInt()) {
    175 		val (m, d, w) = readLine()!!.split(' ').map { it.toLong() }
    176 		val w2 = w / gcd(d - 1, w)
    177 		val mn = minOf(m, d)
    178 		var cnt = mn / w2
    179 		println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2)
    180 	}
    181 }
    182 ```
    183 
    184 [1389F - Bicolored Segments](/contest/1389/problem/F "Educational Codeforces Round 92 (Rated for Div. 2)")
    185 
    186 Idea: [Roms](/profile/Roms "Master Roms")
    187 
    188 **Tutorial**
    189 
    190 Tutorial is loading...
    191 
    192 **Solution 1 (Ne0n25)**
    193 
    194 ```
    195 #include <bits/stdc++.h>
    196 
    197 using namespace std;
    198 
    199 #define x first
    200 #define y second
    201 #define pb push_back
    202 #define mp make_pair
    203 #define all(a) (a).begin(), (a).end()
    204 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    205 
    206 typedef pair<int, int> pt;
    207 
    208 const int N = 200 * 1000;
    209 
    210 int n;
    211 int l[N], r[N], t[N];
    212 set<pt> st[2];
    213 
    214 int main() {
    215 	scanf("%d", &n);
    216 	forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i];
    217 	
    218 	vector<pair<int, pt>> ev;
    219 	forn(i, n) {
    220 		ev.pb(mp(l[i], mp(0, i)));
    221 		ev.pb(mp(r[i], mp(1, i)));
    222 	}
    223 
    224 	sort(all(ev));
    225 	
    226 	int ans = 0;
    227 	for (auto it : ev) {
    228 		int i = it.y.y;
    229 		if (it.y.x) {
    230 			int j = t[i];
    231 			int k = j ^ 1;
    232 			if (st[j].count(mp(r[i], i)) && !st[k].empty()) {
    233 				++ans;
    234 				st[k].erase(st[k].begin());
    235 			}
    236 			if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i));
    237 		} else {
    238 			st[t[i]].insert(mp(r[i], i));
    239 		}
    240 	}
    241 	
    242 	printf("%d\n", n - ans);
    243 }
    244 ```
    245 
    246 **Solution 2 (Ne0n25)**
    247 
    248 ```
    249 #include <bits/stdc++.h>
    250 
    251 using namespace std;
    252 
    253 #define x first
    254 #define y second
    255 #define pb push_back
    256 #define mp make_pair
    257 #define sz(a) int((a).size())
    258 #define all(a) (a).begin(), (a).end()
    259 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    260 
    261 typedef pair<int, int> pt;
    262 
    263 const int INF = 1e9;
    264 const int N = 200 * 1000;
    265 
    266 int n;
    267 vector<pt> a[2];
    268 
    269 struct segtree {
    270 	int n;
    271 	vector<int> t, ps;
    272 	segtree(int n) : n(n) {
    273 		t.resize(4 * n, -INF);
    274 		ps.resize(4 * n, 0);
    275 	}
    276 	
    277 	void push(int v, int l, int r) {
    278 		if (l + 1 != r) {
    279 			ps[v * 2 + 1] += ps[v];
    280 			ps[v * 2 + 2] += ps[v];
    281 		}
    282 		t[v] += ps[v];
    283 		ps[v] = 0;
    284 	}
    285 	
    286 	void upd(int v, int l, int r, int pos, int val) {
    287 		push(v, l, r);
    288 		if (l + 1 == r) {
    289 			t[v] = val;
    290 			return;
    291 		}
    292 		int m = (l + r) >> 1;
    293 		if (pos < m) upd(v * 2 + 1, l, m, pos, val);
    294 		else upd(v * 2 + 2, m, r, pos, val);
    295 		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    296 	}
    297 	
    298 	void add(int v, int l, int r, int L, int R, int val) {
    299 		push(v, l, r);
    300 		if (L >= R) return;
    301 		if (l == L && r == R) {
    302 			ps[v] += val;
    303 			push(v, l, r);
    304 			return;
    305 		}
    306 		int m = (l + r) >> 1;
    307 		add(v * 2 + 1, l, m, L, min(m, R), val);
    308 		add(v * 2 + 2, m, r, max(m, L), R, val);
    309 		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    310 	}
    311 	
    312 	int get(int v, int l, int r, int L, int R) {
    313 		push(v, l, r);
    314 		if (L >= R) return -INF;
    315 		if (l == L && r == R) 
    316 			return t[v];
    317 		int m = (l + r) >> 1;
    318 		int r1 = get(v * 2 + 1, l, m, L, min(m, R));
    319 		int r2 = get(v * 2 + 2, m, r, max(m, L), R);
    320 		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    321 		return max(r1, r2);
    322 	}
    323 	
    324 	void upd(int pos, int val) {
    325 		return upd(0, 0, n, pos, val);
    326 	}
    327 	
    328 	void add(int l, int r, int val) {
    329 		return add(0, 0, n, l, r, val);
    330 	}
    331 	
    332 	int get(int l, int r) {
    333 		return get(0, 0, n, l, r);
    334 	}
    335 };
    336 
    337 int main() {
    338 	scanf("%d", &n);
    339 	forn(i, n) {
    340 		int l, r, t;
    341 		scanf("%d%d%d", &l, &r, &t);
    342 		a[t - 1].pb(mp(r, l));
    343 	}
    344 	
    345 	forn(i, 2) sort(all(a[i]), [](pt a, pt b) {
    346 		if (a.x == b.x) return a.y > b.y;
    347 		return a.x < b.x;
    348 	});
    349 	
    350 	segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1);
    351 	t1.upd(0, 0);
    352 	t2.upd(0, 0);
    353 		
    354 	int ans = 0;
    355 	for (int i = 0, j = 0; i + j < n; ) {
    356 		if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) {
    357 			int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1; 
    358 			int cur = t2.get(0, pos) + 1;
    359 			ans = max(ans, cur);
    360 			t1.upd(i + 1, cur);
    361 			t2.add(0, pos, 1);
    362 			++i;
    363 		} else {
    364 			int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1; 
    365 			int cur = t1.get(0, pos) + 1;
    366 			ans = max(ans, cur);
    367 			t2.upd(j + 1, cur);
    368 			t1.add(0, pos, 1);
    369 			++j;
    370 		}
    371 	}
    372 	
    373 	printf("%d\n", ans);
    374 }
    375 ```
    376 
    377 [1389G - Directing Edges](/contest/1389/problem/G "Educational Codeforces Round 92 (Rated for Div. 2)")
    378 
    379 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    380 
    381 **Tutorial**
    382 
    383 Tutorial is loading...
    384 
    385 **Solution (BledDest)**
    386 
    387 ```
    388 #include<bits/stdc++.h>
    389 
    390 using namespace std;
    391 
    392 typedef long long li;
    393 
    394 const int N = 300043;
    395 
    396 bool is_bridge[N];
    397 int w[N];
    398 int c[N];
    399 int v[N];
    400 vector<pair<int, int> > g[N];
    401 
    402 vector<pair<int, int> > g2[N];
    403 int comp[N];
    404 li sum[N];
    405 li dp[N];
    406 int cnt[N];
    407 int fup[N];
    408 int tin[N];
    409 int T = 0;
    410 li ans[N];
    411 int v1[N], v2[N];
    412 
    413 int n, m, k;
    414 
    415 int dfs1(int x, int e)
    416 {
    417 	tin[x] = T++;
    418 	fup[x] = tin[x];
    419 	for(auto p : g[x])
    420 	{
    421 		int y = p.first;
    422 		int i = p.second;
    423 		if(i == e)
    424 			continue;
    425 		if(tin[y] != -1)
    426 			fup[x] = min(fup[x], tin[y]);
    427 		else
    428 		{
    429 			fup[x] = min(fup[x], dfs1(y, i));
    430 			if(fup[y] > tin[x])
    431 				is_bridge[i] = true;
    432 		}
    433 	}
    434 	return fup[x];
    435 }
    436 
    437 void dfs2(int x, int cc)
    438 {
    439 	if(comp[x] != -1)
    440 		return;
    441 	comp[x] = cc;
    442 	cnt[cc] += v[x];
    443 	sum[cc] += c[x];
    444 	for(auto y : g[x])
    445 		if(!is_bridge[y.second])
    446 			dfs2(y.first, cc);
    447 }
    448 
    449 void process_edge(int x, int y, int m, int weight)
    450 {
    451 	li add_dp = dp[y];
    452 	if(cnt[y] > 0 && cnt[y] < k)
    453 		add_dp = max(0ll, add_dp - weight);
    454 	
    455 	cnt[x] += m * cnt[y];
    456 	dp[x] += m * add_dp;
    457 }
    458 
    459 void link(int x, int y, int weight)
    460 {
    461 	process_edge(x, y, 1, weight);
    462 }
    463 
    464 void cut(int x, int y, int weight)
    465 {
    466 	process_edge(x, y, -1, weight);
    467 }
    468 
    469 void dfs3(int x, int p)
    470 {
    471     dp[x] = sum[x];
    472 	for(auto e : g2[x])
    473 	{
    474 		int i = e.second;
    475 		int y = e.first;
    476 		if(y == p)
    477 			continue;
    478 		dfs3(y, x);
    479 		link(x, y, w[i]);
    480 	}
    481 }
    482 
    483 void dfs4(int x, int p)
    484 {
    485 	ans[x] = dp[x];
    486 	for(auto e : g2[x])
    487 	{
    488 		int i = e.second;
    489 		int y = e.first;
    490 		if(y == p)
    491 			continue;
    492 		cut(x, y, w[i]);
    493 		link(y, x, w[i]);
    494 		dfs4(y, x);
    495 		cut(y, x, w[i]);
    496 		link(x, y, w[i]);
    497 	}
    498 }
    499 
    500 int main()
    501 {
    502 	scanf("%d %d %d", &n, &m, &k);
    503 	for(int  i = 0; i < k; i++)
    504 	{
    505 		int x;
    506 		scanf("%d", &x);
    507 		--x;
    508 		v[x] = 1;
    509 	}
    510 	for(int i = 0; i < n; i++)
    511 		scanf("%d", &c[i]);
    512 	for(int i = 0; i < m; i++)
    513 		scanf("%d", &w[i]);
    514 	for(int i = 0; i < m; i++)
    515 	{
    516 		scanf("%d %d", &v1[i], &v2[i]);
    517 		--v1[i];
    518 		--v2[i];
    519 		g[v1[i]].push_back(make_pair(v2[i], i));
    520 		g[v2[i]].push_back(make_pair(v1[i], i));
    521 	}
    522 	
    523 	for(int i = 0; i < n; i++)
    524 	{
    525 		tin[i] = -1;
    526 		comp[i] = -1;
    527 	}
    528 	dfs1(0, -1);
    529 	int cc = 0;
    530 	for(int i = 0; i < n; i++)
    531 		if(comp[i] == -1)
    532 			dfs2(i, cc++);
    533 	for(int i = 0; i < m; i++)
    534 		if(is_bridge[i])
    535 		{
    536 			g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
    537 			g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
    538 		}
    539 	dfs3(0, 0);
    540 	dfs4(0, 0);
    541 	for(int i = 0; i < n; i++)
    542 		printf("%lld ", ans[comp[i]]);
    543 	puts("");
    544 }
    545 ```