codeforces-scrape

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

1694.md (12447B)


      1 Source: https://codeforces.com/blog/entry/103952
      2 
      3 ### [1694A - Жуть](/contest/1694/problem/A "Codeforces Round 800 (Div. 2)")
      4 
      5 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Implementation**
     12 
     13 ```
     14 # include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int t, A, B;
     19 
     20 int main(){
     21 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     22 
     23 	cin >> t;
     24 	while (t --){
     25 		cin >> A >> B;
     26 		for (int i = 0; i < min(A, B); ++ i)
     27 			cout << "01";
     28 		for (int i = 0; i < abs(A - B); ++ i)
     29 			cout << (A < B ? 1 : 0);
     30 		cout << '\n';
     31 	}
     32 
     33 	return 0;
     34 }
     35 ```
     36 
     37 ### [1694B - Параноидальная строка](/contest/1694/problem/B "Codeforces Round 800 (Div. 2)")
     38 
     39 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ")
     40 
     41 **Solution**
     42 
     43 Tutorial is loading...
     44 
     45 **Implementation**
     46 
     47 ```
     48 # include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 int t, n;
     53 string S;
     54 long long ans;
     55 
     56 int main(){
     57 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     58 
     59 	cin >> t;
     60 	while (t --){
     61 		cin >> n >> S, ans = n;
     62 		for (int i = 1; i < n; ++ i)
     63 			if (S[i] != S[i - 1])
     64 				ans += i;
     65 		cout << ans << '\n';
     66 	}
     67 
     68 	return 0;
     69 }
     70 ```
     71 
     72 ### [1693A - Ориентированное увеличение](/contest/1693/problem/A "Codeforces Round 800 (Div. 1)")
     73 
     74 Idea: [alireza_kaviani](/profile/alireza_kaviani "Гроссмейстер alireza_kaviani")
     75 
     76 **Solution**
     77 
     78 Tutorial is loading...
     79 
     80 **Implementation**
     81 
     82 ```
     83 //In the name of God
     84 #include <bits/stdc++.h>
     85 using namespace std;
     86 
     87 const int maxn = 2e5 + 100;
     88 
     89 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     90 
     91 int n, t, a[maxn];
     92 long long ps[maxn];
     93 
     94 int main(){
     95 	fast_io;
     96 	
     97 	cin >> t;
     98 	while(t--){
     99 		cin >> n;
    100 		for(int i = 1; i <= n; i++){
    101 			cin >> a[i];
    102 			ps[i] = ps[i - 1] + a[i];
    103 		}
    104 		if(ps[n] != 0){
    105 			cout << "No\n";
    106 			continue;
    107 		}
    108 		bool ok = 1;
    109 		for(int i = 1; i <= n; i++){
    110 			if(ps[i] < 0) ok = 0;
    111 		}
    112 		bool visited_zero = 0;
    113 		for(int i = 1; i <= n; i++){
    114 			if(ps[i] == 0) visited_zero = 1;
    115 			else if(visited_zero) ok = 0;
    116 		}
    117 		if(ok) cout << "Yes\n";
    118 		else cout << "No\n";
    119 	}
    120 	
    121 	return 0;
    122 }
    123 ```
    124 
    125 ### [1693B - Фейковые пластиковые деревья](/contest/1693/problem/B "Codeforces Round 800 (Div. 1)")
    126 
    127 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ"), [alireza_kaviani](/profile/alireza_kaviani "Гроссмейстер alireza_kaviani")
    128 
    129 **Solution**
    130 
    131 Tutorial is loading...
    132 
    133 **Implementation**
    134 
    135 ```
    136 # include <bits/stdc++.h>
    137 
    138 using namespace std;
    139 
    140 typedef long long ll;
    141 
    142 const int N = 2e5 + 10;
    143 
    144 int t, n, l[N], r[N], ans;
    145 vector <int> adj[N];
    146 
    147 ll DFS(int v){
    148 	ll sum = 0;
    149 	for (int u : adj[v]){
    150 		sum += DFS(u);
    151 	}
    152 	if (sum < ll(l[v])){
    153 		++ ans;
    154 		return r[v];
    155 	}
    156 	return min(ll(r[v]), sum);
    157 }
    158 
    159 int main(){
    160 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    161 
    162 	cin >> t;
    163 	while (t --){
    164 		cin >> n;
    165 		for (int i = 2; i <= n; ++ i){
    166 			int par;
    167 			cin >> par;
    168 			adj[par].push_back(i);
    169 		}
    170 		for (int i = 1; i <= n; ++ i){
    171 			cin >> l[i] >> r[i];
    172 		}
    173 		ans = 0;
    174 		DFS(1);
    175 		cout << ans << "\n";
    176 		for (int i = 1; i <= n; ++ i){
    177 			adj[i].clear();
    178 		}
    179 	}
    180 
    181 	return 0;
    182 }
    183 ```
    184 
    185 ### [1693C - Keshi ищет AmShZ](/contest/1693/problem/C "Codeforces Round 800 (Div. 1)")
    186 
    187 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ")
    188 
    189 **Solution**
    190 
    191 Tutorial is loading...
    192 
    193 **Implementation**
    194 
    195 ```
    196 # include <bits/stdc++.h>
    197 
    198 using namespace std;
    199 
    200 const int N = 2e5 + 10;
    201 
    202 int n, m, d[N], dist[N];
    203 priority_queue <pair <int, int> > pq;
    204 vector <int> adj[N];
    205 bool mark[N];
    206 
    207 int main(){
    208 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    209 
    210 	cin >> n >> m;
    211 	fill(dist, dist + n + 1, m);
    212 	while (m --){
    213 		int v, u;
    214 		cin >> v >> u;
    215 		adj[u].push_back(v);
    216 		++ d[v];
    217 	}
    218 	dist[n] = 0;
    219 	pq.push({0, n});
    220 	while (!pq.empty()){
    221 		int v = pq.top().second;
    222 		pq.pop();
    223 		if (mark[v])
    224 			continue;
    225 		mark[v] = true;
    226 		for (int u : adj[v]){
    227 			if (dist[v] + d[u] < dist[u]){
    228 				dist[u] = dist[v] + d[u];
    229 				pq.push({- dist[u], u});
    230 			}
    231 			-- d[u];
    232 		}
    233 	}
    234 	cout << dist[1] << '\n';
    235 
    236 	return 0;
    237 }
    238 ```
    239 
    240 ### [1693D - Разбиение на возрастающую и спадающую](/contest/1693/problem/D "Codeforces Round 800 (Div. 1)")
    241 
    242 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ")
    243 
    244 **Solution 1**
    245 
    246 Tutorial is loading...
    247 
    248 Thanks to [Koosha_Mv](/profile/Koosha_Mv "Гроссмейстер Koosha_Mv")
    249 
    250 **Solution 2**
    251 
    252 It can be proven that a permutation is **Decinc** if and only if it's $3412$-avoiding and $2143$-avoiding.
    253 
    254 **Implementation 1**
    255 
    256 ```
    257 # include <bits/stdc++.h>
    258  
    259 using namespace std;
    260  
    261 const int N = 2e5 + 10;
    262  
    263 int n, a[N], dp[N], pd[N], f[N];
    264 long long ans;
    265  
    266 inline void upd(int i){
    267 	if (n < i)
    268 		return;
    269 	int inc = 0, dec = n + 1;
    270 	if (pd[i - 1] < a[i])
    271 		inc = max(inc, a[i - 1]);
    272 	if (a[i - 1] < a[i])
    273 		inc = max(inc, dp[i - 1]);
    274 	if (a[i] < dp[i - 1])
    275 		dec = min(dec, a[i - 1]);
    276 	if (a[i] < a[i - 1])
    277 		dec = min(dec, pd[i - 1]);
    278 	if (inc == dp[i] && dec == pd[i])
    279 		return;
    280 	dp[i] = inc, pd[i] = dec;
    281 	f[i] = 0;
    282 	if (dec <= n || inc){
    283 		upd(i + 1);
    284 		f[i] = f[i + 1] + 1;
    285 	}
    286 	return;
    287 }
    288  
    289 int main(){
    290 	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    291  
    292 	cin >> n;
    293 	for (int i = 1; i <= n; ++ i)
    294 		cin >> a[i];
    295 	for (int i = n; 1 <= i; -- i){
    296 		dp[i] = n + 1;
    297 		pd[i] = 0;
    298 		upd(i + 1);
    299 		f[i] = f[i + 1] + 1;
    300 		ans += f[i];
    301 	}
    302 	cout << ans << '\n';
    303  
    304 	return 0;
    305 }
    306 ```
    307 
    308 **Implementation 2**
    309 
    310 ```
    311 # include <bits/stdc++.h>
    312 
    313 using namespace std;
    314 
    315 const int N = 2e5 + 10;
    316 
    317 int n, a[N], min_r[N], fen[N];
    318 long long ans;
    319 stack <int> sk;
    320 vector <int> vec[2][N];
    321 
    322 void mofen(int pos, int val){
    323 	for (pos += 5; pos < N; pos += pos & - pos)
    324 		fen[pos] = min(fen[pos], val);
    325 }
    326 int gefen(int pos){
    327 	int res = n + 1;
    328 	for (pos += 5; 0 < pos; pos -= pos & - pos)
    329 		res = min(res, fen[pos]);
    330 	return res;
    331 }
    332 
    333 void find_3412(){
    334 	fill(fen, fen + n + 10, n + 1);
    335 	while (!sk.empty())
    336 		sk.pop();
    337 	for (int i = 1; i <= n; ++ i){
    338 		while (!sk.empty() && a[i] < a[sk.top()])
    339 			sk.pop();
    340 		if (!sk.empty())
    341 			vec[0][sk.top()].push_back(i);
    342 		sk.push(i);
    343 	}
    344 	while (!sk.empty())
    345 		sk.pop();
    346 	for (int i = n; 1 <= i; -- i){
    347 		while (!sk.empty() && a[sk.top()] < a[i])
    348 			sk.pop();
    349 		if (!sk.empty())
    350 			vec[1][sk.top()].push_back(i);
    351 		sk.push(i);
    352 	}
    353 	for (int i = n; 1 <= i; -- i){
    354 		for (int ind : vec[0][i])
    355 			mofen(a[ind], ind);
    356 		for (int ind : vec[1][i])
    357 			min_r[ind] = min(min_r[ind], gefen(a[ind] - 1));
    358 		vec[0][i].clear(), vec[1][i].clear();
    359 	}
    360 }
    361 
    362 int main(){
    363 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    364 
    365 	cin >> n;
    366 	for (int i = 1; i <= n; ++ i)
    367 		cin >> a[i];
    368 	fill(min_r, min_r + n + 2, n + 1);
    369 	find_3412();
    370 	for (int i = 1; i <= n; ++ i)
    371 		a[i] = n + 1 - a[i];
    372 	find_3412();
    373 	for (int i = n; 1 <= i; -- i){
    374 		min_r[i] = min(min_r[i], min_r[i + 1]);
    375 		ans += min_r[i] - i;
    376 	}
    377 	cout << ans << '\n';
    378 
    379 	return 0;
    380 }
    381 ```
    382 
    383 ### [1693E - Крайние максимумы](/contest/1693/problem/E "Codeforces Round 800 (Div. 1)")
    384 
    385 Idea: [Keshi](/profile/Keshi "Гроссмейстер Keshi")
    386 
    387 **Solution**
    388 
    389 Tutorial is loading...
    390 
    391 **Implementation**
    392 
    393 ```
    394 //In the name of God
    395 #include <bits/stdc++.h>
    396 using namespace std;
    397 
    398 typedef long long ll;
    399 typedef pair<int, int> pii;
    400 typedef pair<ll, ll> pll;
    401 
    402 const ll maxn = 2e5 + 100;
    403 const ll mod = 1e9 + 7;
    404 const int inf = 1e9;
    405 const ll INF = 1e18;
    406 
    407 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    408 #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
    409 #define pb push_back
    410 #define Mp make_pair
    411 #define F first
    412 #define S second
    413 #define Sz(x) ll((x).size())
    414 #define all(x) (x).begin(), (x).end()
    415 #define lc (id << 1)
    416 #define rc (lc | 1)
    417 
    418 ll pw(ll a, ll b){
    419 	ll c = 1;
    420 	while(b){
    421 		if(b & 1) c = c * a % mod;
    422 		a = a * a % mod;
    423 		b >>= 1;
    424 	}
    425 	return c;
    426 }
    427 
    428 struct cost{
    429 	int c[2][2];
    430 	cost(){
    431 		memset(c, 0, sizeof c);
    432 	}
    433 };
    434 
    435 cost cst[2][2];
    436 
    437 int n, a[maxn], dp[maxn], cnl[maxn], cnr[maxn];
    438 ll s, ans, ans2;
    439 cost seg[maxn << 2];
    440 
    441 inline cost mrg(cost l, cost r){
    442 	cost mid;
    443 	for(int i = 0; i < 2; i++){
    444 		for(int j = 0; j < 2; j++){
    445 			mid.c[i][j] = min(r.c[i][0] + l.c[0][j], r.c[i][1] + l.c[1][j]);
    446 		}
    447 	}
    448 	return mid;
    449 }
    450 
    451 void bld(int id, int s, int e){
    452 	if(e - s == 1){
    453 		seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
    454 		return;
    455 	}
    456 	int mid = (s + e) >> 1;
    457 	bld(lc, s, mid);
    458 	bld(rc, mid, e);
    459 	seg[id] = mrg(seg[lc], seg[rc]);
    460 	return;
    461 }
    462 
    463 void upd(int id, int s, int e, int l, int r){
    464 	if(r <= s || e <= l) return;
    465 	if(l <= s && e <= r){
    466 		seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
    467 		return;
    468 	}
    469 	int mid = (s + e) >> 1;
    470 	upd(lc, s, mid, l, r);
    471 	upd(rc, mid, e, l, r);
    472 	seg[id] = mrg(seg[lc], seg[rc]);
    473 	return;
    474 }
    475 cost get(int id, int s, int e, int l, int r){
    476 	if(r <= s || e <= l) return cost();
    477 	if(l <= s && e <= r) return seg[id];
    478 	int mid = (s + e) >> 1;
    479 	return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
    480 }
    481 
    482 int main(){
    483 	fast_io;
    484 	srand(time(NULL));
    485 	
    486 	cst[0][0].c[0][0] = cst[0][0].c[1][1] = 0;
    487 	cst[0][0].c[0][1] = cst[0][0].c[1][0] = inf;
    488 	
    489 	cst[0][1].c[1][0] = cst[0][1].c[1][1] = 1;
    490 	cst[0][1].c[0][0] = 0;
    491 	cst[0][1].c[0][1] = inf;
    492 	
    493 	cst[1][0].c[0][1] = cst[1][0].c[0][0] = 1;
    494 	cst[1][0].c[1][1] = 0;
    495 	cst[1][0].c[1][0] = inf;
    496 	
    497 	cst[1][1].c[0][0] = cst[1][1].c[1][1] = 1;
    498 	cst[1][1].c[0][1] = cst[1][1].c[1][0] = 1;
    499 	
    500 	cin >> n;
    501 	cnr[0] = cnl[0] = 1;
    502 	for(int i = 1; i <= n; i++){
    503 		cin >> a[i];
    504 		cnr[a[i]]++;
    505 		s += a[i];
    506 	}
    507 	bld(1, 0, n + 1);
    508 	for(int i = 1; i <= n; i++){
    509 		cost cs = get(1, 0, n + 1, 0, a[i]);
    510 		cnr[a[i]]--;
    511 		cnl[a[i]]++;
    512 		upd(1, 0, n + 1, a[i], a[i] + 1);
    513 		dp[i] = min({cs.c[0][0], cs.c[0][1], cs.c[1][0], cs.c[1][1]});
    514 		ans += dp[i];
    515 	}
    516 	
    517 	cout << ans << "\n";
    518 	
    519 	return 0;
    520 }
    521 ```
    522 
    523 Check out [this](https://codeforces.com/blog/entry/103952?#comment-923531) solution by [ecnerwala](/profile/ecnerwala "Легендарный гроссмейстер ecnerwala")
    524 
    525 ### [1693F - Я могу ошибаться](/contest/1693/problem/F "Codeforces Round 800 (Div. 1)")
    526 
    527 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ")
    528 
    529 Thanks to [antontrygubO_o](/profile/antontrygubO_o "Международный гроссмейстер antontrygubO_o") for proof
    530 
    531 **Solution**
    532 
    533 Tutorial is loading...
    534 
    535 **Implementation by Um_nik**
    536 
    537 ```
    538 #include <iostream>
    539 #include <cstdio>
    540 #include <cstdlib>
    541 #include <algorithm>
    542 #include <cmath>
    543 #include <vector>
    544 #include <set>
    545 #include <map>
    546 #include <unordered_set>
    547 #include <unordered_map>
    548 #include <queue>
    549 #include <ctime>
    550 #include <cassert>
    551 #include <complex>
    552 #include <string>
    553 #include <cstring>
    554 #include <chrono>
    555 #include <random>
    556 #include <bitset>
    557 #include <array>
    558 using namespace std;
    559  
    560 #ifdef LOCAL
    561 	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
    562 #else
    563 	#define eprintf(...) 42
    564 #endif
    565  
    566 using ll = long long;
    567 using ld = long double;
    568 using uint = unsigned int;
    569 using ull = unsigned long long;
    570 template<typename T>
    571 using pair2 = pair<T, T>;
    572 using pii = pair<int, int>;
    573 using pli = pair<ll, int>;
    574 using pll = pair<ll, ll>;
    575 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    576 ll myRand(ll B) {
    577 	return (ull)rng() % B;
    578 }
    579  
    580 #define pb push_back
    581 #define mp make_pair
    582 #define all(x) (x).begin(),(x).end()
    583 #define fi first
    584 #define se second
    585  
    586 clock_t startTime;
    587 double getCurrentTime() {
    588 	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
    589 }
    590  
    591 const int N = 200200;
    592 int n;
    593 char s[N];
    594 int bal[N];
    595 int pos[N];
    596  
    597 void solve() {
    598 	scanf("%d %s", &n, s);
    599 	int b = 0;
    600 	for (int i = 0; i < n; i++) {
    601 		if (s[i] == '0')
    602 			b++;
    603 		else
    604 			b--;
    605 	}
    606 	if (b < 0) {
    607 		for (int i = 0; i < n; i++)
    608 			s[i] ^= 1;
    609 		reverse(s, s + n);
    610 		b *= -1;
    611 	}
    612 	bal[0] = (n + b) / 2;
    613 	for (int i = 0; i < n; i++)
    614 		bal[i + 1] = bal[i] + (s[i] == '0' ? -1 : 1);
    615 	assert(bal[n] == (n - b) / 2);
    616 	for (int i = 0; i <= n; i++)
    617 		pos[i] = -1;
    618 	for (int i = 0; i <= n; i++)
    619 		pos[bal[i]] = i;
    620 	int ans = 0;
    621 	int l = 0;
    622 	while(l < (n + b) / 2) {
    623 		if (bal[l + 1] < bal[l]) {
    624 			l++;
    625 			continue;
    626 		}
    627 		if (bal[l] <= (n - b) / 2) {
    628 			ans++;
    629 			break;
    630 		}
    631 		int r = pos[bal[l]];
    632 		assert(r > l);
    633 		ans++;
    634 		for (int i = l + 1; i < r; i++) {
    635 			if (2 * i > l + r) {
    636 				bal[i] = bal[l] - (r - i);
    637 			} else {
    638 				bal[i] = bal[l] - (i - l);
    639 			}
    640 			pos[bal[i]] = max(pos[bal[i]], i);
    641 		}
    642 	}
    643 	printf("%d\n", ans);
    644 }
    645  
    646 int main()
    647 {
    648 	startTime = clock();
    649 //	freopen("input.txt", "r", stdin);
    650 //	freopen("output.txt", "w", stdout);
    651 	int t;
    652 	scanf("%d", &t);
    653 	while(t--) solve();
    654  
    655 	return 0;
    656 }
    657 ```
    658 
    659 Thanks to [Um_nik](/profile/Um_nik "Легендарный гроссмейстер Um_nik")