codeforces-scrape

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

1073.md (11954B)


      1 Source: https://codeforces.com/blog/entry/62742
      2 
      3 [1073A - Diverse Substring](/contest/1073/problem/A "Educational Codeforces Round 53 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (PikMike)**
     10 
     11 ```
     12 n = int(input())
     13 s = input()
     14 for i in range(n - 1):
     15 	if (s[i] != s[i + 1]):
     16 		print("YES")
     17 		print(s[i], s[i + 1], sep="")
     18 		exit(0)
     19 print("NO")
     20 ```
     21 
     22 [1073B - Vasya and Books](/contest/1073/problem/B "Educational Codeforces Round 53 (Rated for Div. 2)")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (Ajosteen)**
     29 
     30 ```
     31 #include <bits/stdc++.h>
     32 
     33 using namespace std;
     34 
     35 const int N = int(2e5) + 9;
     36 
     37 int n;
     38 int a[N];
     39 int b[N];
     40 bool u[N];
     41 
     42 int main() {
     43 //	freopen("input.txt", "r", stdin);
     44 	scanf("%d", &n);
     45     for(int i = 0; i < n; ++i) {
     46     	scanf("%d", a + i);
     47     }
     48     for(int i = 0; i < n; ++i){
     49     	scanf("%d", b + i);
     50     }
     51 	
     52 	int pos = 0;
     53 	for(int i = 0; i < n; ++i){
     54 		int x = b[i];
     55 		if(u[x]){
     56 			printf("0 ");
     57 			continue;
     58 		}
     59 		
     60 		int cnt = 0;
     61 		while(true){
     62 			++cnt;
     63 			u[a[pos]] = true;
     64 			if(a[pos] == x) break;
     65 			++pos;
     66 		} 
     67 		
     68 		++pos;
     69 		printf("%d ", cnt);
     70 	}    
     71 	
     72 	puts("");
     73     return 0;
     74 }
     75 ```
     76 
     77 [1073C - Vasya and Robot](/contest/1073/problem/C "Educational Codeforces Round 53 (Rated for Div. 2)")
     78 
     79 **Tutorial**
     80 
     81 Tutorial is loading...
     82 
     83 **Solution (Ajosteen)**
     84 
     85 ```
     86 #include <bits/stdc++.h>
     87 
     88 using namespace std;
     89 
     90 const int N = int(1e5) + 9;
     91 
     92 string s;
     93 int n;
     94 int x, y;
     95 
     96 void upd(pair<int, int> &pos, char mv, int d){
     97 	if(mv == 'U')
     98 		pos.second += d;
     99 	if(mv == 'D')
    100 		pos.second -= d;
    101 	if(mv == 'L')
    102 		pos.first -= d;
    103 	if(mv == 'R')
    104 		pos.first += d;
    105 }
    106 
    107 bool can(pair<int, int> u, pair<int, int> v, int len){
    108 	int d = abs(u.first - v.first) + abs(u.second - v.second);
    109 	if(d % 2 != len % 2) return false;
    110 	return len >= d;
    111 }
    112 
    113 bool ok(int len){
    114 	pair<int, int> pos = make_pair(0, 0);
    115 	for(int i = len; i < n; ++i)
    116 		upd(pos, s[i], 1);
    117 
    118 	int l = 0, r = len;
    119 	while(true){
    120 		if(can(pos, make_pair(x, y), len))
    121 			return true;
    122 		
    123 		if(r == n) break;
    124 		upd(pos, s[l++], 1);
    125 		upd(pos, s[r++], -1);		
    126 	}
    127 	
    128 	return false;
    129 }
    130 
    131 int main() {
    132 	//freopen("input.txt", "r", stdin);
    133 	
    134 	cin >> n;
    135 	cin >> s;
    136 	cin >> x >> y;
    137 	
    138 	if(!ok(n)){
    139 		puts("-1");
    140 		return 0;
    141 	}
    142 	
    143 	int l = -1, r = n;
    144 	while(r - l > 1){
    145 		int mid = (l + r) / 2;
    146 		if(ok(mid)) r = mid;
    147 		else l = mid;
    148 	}
    149 	
    150 	cout << r << endl;
    151     return 0;
    152 }
    153 ```
    154 
    155 [1073D - Berland Fair](/contest/1073/problem/D "Educational Codeforces Round 53 (Rated for Div. 2)")
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution (PikMike)**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 
    166 #define forn(i, n) for (int i = 0; i < int(n); i++)
    167 
    168 using namespace std;
    169 
    170 const int N = 200 * 1000 + 13;
    171 
    172 typedef long long li;
    173 
    174 int n;
    175 int a[N];
    176 
    177 void get(li T, li& pr, li& cnt){
    178 	pr = 0, cnt = 0;
    179 	forn(i, n){
    180 		if (T >= a[i]){
    181 			T -= a[i];
    182 			pr += a[i];
    183 			++cnt;
    184 		}
    185 	}
    186 }
    187 
    188 int main() {
    189 	li T;
    190 	scanf("%d%lld", &n, &T);
    191 	forn(i, n)
    192 		scanf("%d", &a[i]);
    193 	
    194 	int mn = *min_element(a, a + n);
    195 	li ans = 0;
    196 	while (T >= mn){
    197 		li pr, cnt;
    198 		get(T, pr, cnt);
    199 		ans += cnt * (T / pr);
    200 		T %= pr;
    201 	}
    202 	printf("%lld\n", ans);
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1073E - Segment Sum](/contest/1073/problem/E "Educational Codeforces Round 53 (Rated for Div. 2)")
    208 
    209 **Tutorial**
    210 
    211 Tutorial is loading...
    212 
    213 **Solution (Vovuh)**
    214 
    215 ```
    216 #include <bits/stdc++.h>
    217 
    218 using namespace std;
    219 
    220 #define x first
    221 #define y second
    222 
    223 typedef pair<long long, int> pt;
    224 
    225 const int N = 20;
    226 const int M = 1 << 10;
    227 const int MOD = 998244353;
    228 
    229 int k;
    230 int pw10[N];
    231 int bitCnt[M];
    232 
    233 pt dp[N][M][2];
    234 
    235 int add(int a, int b) {
    236 	a += b;
    237 	if (a >= MOD) a -= MOD;
    238 	if (a < 0) a += MOD;
    239 	return a;
    240 }
    241 
    242 int mul(int a, int b) {
    243 	return a * 1ll * b % MOD;
    244 }
    245 
    246 int calc(const string &s) {
    247 	for (int i = 0; i < N; ++i) {
    248 		for (int j = 0; j < M; ++j) {
    249 			dp[i][j][0] = dp[i][j][1] = { 0ll, 0 };
    250 		}
    251 	}
    252 	
    253 	int len = s.size();
    254 	dp[0][0][1] = { 1ll, 0 };
    255 	for (int i = 0; i < len; ++i) {
    256 		int cdig = s[i] - '0';
    257 		for (int mask = 0; mask < M; ++mask) {
    258 			if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue;
    259 			for (int dig = (i == 0); dig <= 9; ++dig) {
    260 				int nmask = mask | (1 << dig);
    261 				long long cnt = dp[i][mask][0].x;
    262 				int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
    263 				dp[i + 1][nmask][0].x += cnt;
    264 				dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum);
    265 			}
    266 			
    267 			for (int dig = (i == 0); dig <= cdig; ++dig) {
    268 				int nmask = mask | (1 << dig);
    269 				long long cnt = dp[i][mask][1].x;
    270 				int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
    271 				dp[i + 1][nmask][dig == cdig].x += cnt;
    272 				dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum);
    273 			}
    274 		}
    275 	}
    276 	
    277 	int ans = 0;
    278 	for (int mask = 0; mask < M; ++mask) {
    279 		if (bitCnt[mask] > k) continue;
    280 		ans = add(ans, dp[len][mask][0].y);
    281 		ans = add(ans, dp[len][mask][1].y);
    282 	}
    283 	return ans;
    284 }
    285 
    286 int calc(long long n) {
    287 	int len = to_string(n).size();
    288 	int ans = 0;
    289 	for (int l = 1; l < len; ++l) {
    290 		ans = add(ans, calc(string(l, '9')));
    291 	}
    292 	ans = add(ans, calc(to_string(n)));
    293 	return ans;
    294 }
    295 
    296 int main() {
    297 #ifdef _DEBUG
    298 	freopen("input.txt", "r", stdin);
    299 //	freopen("output.txt", "w", stdout);
    300 #endif
    301 
    302 	pw10[0] = 1;
    303 	for (int i = 1; i < N; ++i) {
    304 		pw10[i] = mul(pw10[i - 1], 10);
    305 	}
    306 	for (int i = 0; i < M; ++i) {
    307 		bitCnt[i] = __builtin_popcount(i);
    308 	}
    309 	
    310 	long long l, r;
    311 	cin >> l >> r >> k;
    312 	int ans = add(calc(r), -calc(l - 1));
    313 	cout << ans << endl;
    314 	
    315 	return 0;
    316 }
    317 ```
    318 
    319 [1073F - Choosing Two Paths](/contest/1073/problem/F "Educational Codeforces Round 53 (Rated for Div. 2)")
    320 
    321 **Tutorial**
    322 
    323 Tutorial is loading...
    324 
    325 **Solution (Vovuh)**
    326 
    327 ```
    328 #include <bits/stdc++.h>
    329 
    330 using namespace std;
    331 
    332 #define x first
    333 #define y second
    334 #define size(a) int((a).size())
    335 
    336 typedef pair<int, int> pt;
    337 
    338 const int N = 200 * 1000 + 11;
    339 
    340 int n;
    341 vector<int> g[N];
    342 
    343 int p[N];
    344 int dist[N];
    345 
    346 bool bad[N];
    347 int value[N];
    348 pt res[N];
    349 vector<pt> best[N];
    350 
    351 void dfs(int v, int par = -1, int d = 0) {
    352 	p[v] = par;
    353 	dist[v] = d;
    354 	for (auto to : g[v]) {
    355 		if (to == par) {
    356 			continue;
    357 		}
    358 		dfs(to, v, d + 1);
    359 	}
    360 }
    361 
    362 int getFarthest(int v) {
    363 	dfs(v);
    364 	int res = v;
    365 	for (int i = 0; i < n; ++i) {
    366 		if (bad[i]) {
    367 			continue;
    368 		}
    369 		if (dist[res] < dist[i]) {
    370 			res = i;
    371 		}
    372 	}
    373 	return res;
    374 }
    375 
    376 pt get(int v) {
    377 	return { dist[v], value[v] };
    378 }
    379 
    380 int getBetter(int v, int u) {
    381 	if (get(v) > get(u)) {
    382 		return v;
    383 	}
    384 	return u;
    385 }
    386 
    387 int getBest(int v, int par) {
    388 	int res = v;
    389 	for (auto to : g[v]) {
    390 		if (to == par || bad[to]) {
    391 			continue;
    392 		}
    393 		res = getBetter(res, getBest(to, v));
    394 	}
    395 	return res;
    396 }
    397 
    398 pt calc(int v) {
    399 	dfs(v);
    400 	
    401 	vector<int> ch;
    402 	for (auto to : g[v]) {
    403 		if (!bad[to]) {
    404 			ch.push_back(to);
    405 		}
    406 	}
    407 	if (size(ch) == 1) {
    408 		return { v, ch[0] };
    409 	}
    410 	
    411 	vector<int> pref(size(ch));
    412 	vector<int> suf(size(ch));
    413 	vector<int> best(size(ch));
    414 	for (int i = 0; i < size(ch); ++i) {
    415 		int to = ch[i];
    416 		best[i] = pref[i] = suf[i] = getBest(to, v);
    417 	}
    418 	for (int i = 1; i < size(ch); ++i) {
    419 		pref[i] = getBetter(pref[i], pref[i - 1]);
    420 		suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]);
    421 	}
    422 	
    423 	pt ans = { -1, -1 };
    424 	pt res = { 0, 0 };
    425 	for (int i = 0; i < size(ch); ++i) {
    426 		int bst = -1;
    427 		if (i == 0) {
    428 			bst = suf[i + 1];
    429 		} else if (i + 1 == size(ch)) {
    430 			bst = pref[i - 1];
    431 		} else {
    432 			bst = getBetter(pref[i - 1], suf[i + 1]);
    433 		}
    434 		pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] };
    435 		if (res < curRes) {
    436 			res = curRes;
    437 			ans = { best[i], bst };
    438 		}
    439 	}
    440 	
    441 	return ans;
    442 }
    443 
    444 int main() {
    445 #ifdef _DEBUG
    446 	freopen("input.txt", "r", stdin);
    447 //	freopen("output.txt", "w", stdout);
    448 #endif
    449 
    450 	cin >> n;
    451 	for (int i = 0; i < n - 1; ++i) {
    452 		int x, y;
    453 		cin >> x >> y;
    454 		--x, --y;
    455 		g[x].push_back(y);
    456 		g[y].push_back(x);
    457 	}
    458 	
    459 	int root = -1;
    460 	for (int i = 0; i < n; ++i) {
    461 		if (size(g[i]) > 2) {
    462 			root = i;
    463 			dfs(i);
    464 			break;
    465 		}
    466 	}
    467 	
    468 	for (int i = 0; i < n; ++i) {
    469 		if (size(g[i]) != 1) {
    470 			continue;
    471 		}
    472 		int v = i;
    473 		while (size(g[v]) < 3) {
    474 			bad[v] = true;
    475 			v = p[v];
    476 		}
    477 		best[v].push_back({dist[i] - dist[v], i});
    478 	}
    479 	
    480 	for (int i = 0; i < n; ++i) {
    481 		if (size(best[i]) >= 2) {
    482 			sort(best[i].rbegin(), best[i].rend());
    483 			value[i] = best[i][0].first + best[i][1].first;
    484 			res[i] = { best[i][0].second, best[i][1].second };
    485 		}
    486 	}
    487 	
    488 	int u = getFarthest(root);
    489 	int v = getFarthest(u);
    490 	vector<int> path;
    491 	while (v != u) {
    492 		path.push_back(v);
    493 		v = p[v];
    494 	}
    495 	path.push_back(u);
    496 	
    497 	pt ans = calc(path[size(path) / 2]);
    498 	
    499 	printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1);
    500 	printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 1);
    501 	
    502 	return 0;
    503 }
    504 ```
    505 
    506 [1073G - Yet Another LCP Problem](/contest/1073/problem/G "Educational Codeforces Round 53 (Rated for Div. 2)")
    507 
    508 **Tutorial**
    509 
    510 Tutorial is loading...
    511 
    512 **Solution (adedalic)**
    513 
    514 ```
    515 #include<bits/stdc++.h>
    516 using namespace std;
    517 
    518 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    519 #define sz(a) int((a).size())
    520 
    521 #define x first
    522 #define y second
    523 
    524 typedef long long li;
    525 typedef pair<int, int> pt;
    526 
    527 template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) {
    528 	return out << "(" << p.x << ", " << p.y << ")";
    529 }
    530 template<class A> ostream& operator <<(ostream &out, const vector<A> &v) {
    531 	out << "[";
    532 	fore(i, 0, sz(v)) {
    533 		if(i) out << ", ";
    534 		out << v[i];
    535 	}
    536 	return out << "]";
    537 }
    538 
    539 const int N = 200 * 1000 + 555;
    540 const int LOGN = 18;
    541 
    542 int n, q;
    543 char s[N];
    544 
    545 bool read() {
    546 	if(!(cin >> n >> q))
    547 		return false;
    548 	assert(scanf("%s", s) == 1);
    549 	return true;
    550 }
    551 
    552 int c[N], id[N], lcp[N];
    553 int mn[LOGN][N];
    554 int lg2[N];
    555 
    556 void buildSuffArray() {
    557 	s[n++] = '$';
    558 	
    559 	for(int l = 1; l < 2 * n; l <<= 1) {
    560 		vector< pair<pt, int> > d;
    561 		fore(i, 0, n)
    562 			d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i);
    563 		stable_sort(d.begin(), d.end());
    564 		
    565 		c[d[0].y] = 0;
    566 		fore(i, 1, n)
    567 			c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x);
    568 		if(c[d.back().y] == n - 1)
    569 			break;
    570 	}
    571 	
    572 	fore(i, 0, n)
    573 		id[c[i]] = i;
    574 		
    575 	int l = 0;
    576 	fore(i, 0, n) {
    577 		if(c[i] == n - 1)
    578 			continue;
    579 		l = max(0, l - 1);
    580 		int j = id[c[i] + 1];
    581 		
    582 		while(i + l < n && j + l < n && s[i + l] == s[j + l])
    583 			l++;
    584 		lcp[c[i]] = l;
    585 	}
    586 	
    587 	n--;
    588 	lg2[0] = lg2[1] = 0;
    589 	fore(i, 2, N) {
    590 		lg2[i] = lg2[i - 1];
    591 		if((1 << (lg2[i] + 1)) <= i)
    592 			lg2[i]++;
    593 	}
    594 	
    595 	fore(i, 0, n)
    596 		mn[0][i] = lcp[i];
    597 	fore(pw, 1, LOGN) fore(i, 0, n) {
    598 		mn[pw][i] = mn[pw - 1][i];
    599 		if(i + (1 << (pw - 1)) < n)
    600 			mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]);
    601 	}
    602 }
    603 
    604 int getMin(int l, int r) {
    605 	int ln = lg2[r - l];
    606 	return min(mn[ln][l], mn[ln][r - (1 << ln)]);
    607 }
    608 
    609 int getLCP(int i, int j) {
    610 	if(i == j) return n - i;
    611 	i = c[i], j = c[j];
    612 	return getMin(min(i, j), max(i, j));
    613 }
    614 
    615 bool cmp(const pt &a, const pt &b) {
    616 	if(a.x == b.x)
    617 		return a.y < b.y;
    618 	int l = getLCP(a.x, b.x);
    619 	return s[a.x + l] < s[b.x + l];
    620 }
    621 
    622 void solve() {
    623 	buildSuffArray();
    624 	
    625 	fore(_, 0, q) {
    626 		int k, l;
    627 		assert(scanf("%d%d", &k, &l) == 2);
    628 		vector<int> a(k), b(l);
    629 		fore(i, 0, k)
    630 			assert(scanf("%d", &a[i]) == 1), a[i]--;
    631 		fore(j, 0, l)
    632 			assert(scanf("%d", &b[j]) == 1), b[j]--;
    633 			
    634 		li ans = 0;
    635 		vector<pt> c;
    636 		for(auto v : a)
    637 			c.emplace_back(v, 1);
    638 		for(auto v : b)
    639 			c.emplace_back(v, 0);
    640 		sort(c.begin(), c.end(), cmp);
    641 		
    642 		fore(k, 0, 2) {
    643 			li sum = 0;
    644 			map<int, int> cnt;
    645 			
    646 			fore(i, 0, sz(c)) {
    647 				int id = c[i].x, tp = c[i].y;
    648 				if(tp == 0)
    649 					ans += sum;
    650 				else {
    651 					cnt[n - id]++;
    652 					sum += (n - id);
    653 				}
    654 				if(i + 1 < sz(c)) {
    655 					int len = getLCP(c[i].x, c[i + 1].x);
    656 					while(!cnt.empty()) {
    657 						auto it = --cnt.end();
    658 						if(it->x <= len)
    659 							break;
    660 						
    661 						sum -= it->x * 1ll * it->y;
    662 						cnt[len] += it->y;
    663 						sum += it->y * 1ll * len;
    664 						cnt.erase(it);
    665 					}
    666 				}
    667 			}
    668 			reverse(c.begin(), c.end());
    669 		}
    670 		printf("%lld\n", ans);
    671 	}
    672 }
    673 
    674 int main() {
    675 #ifdef _DEBUG
    676 	freopen("input.txt", "r", stdin);
    677 	int tt = clock();
    678 #endif
    679 	cout << fixed << setprecision(15);
    680 	
    681 	if(read()) {
    682 		solve();
    683 		
    684 #ifdef _DEBUG
    685 		cerr << "TIME = " << clock() - tt << endl;
    686 #endif
    687 	}
    688 	return 0;
    689 }
    690 ```