codeforces-scrape

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

1550.md (11056B)


      1 Source: https://codeforces.com/blog/entry/92864
      2 
      3 [1550A - Find The Array](/contest/1550/problem/A "Educational Codeforces Round 111 (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 def maxSum(x):
     15 	return x ** 2
     16 
     17 def getAns(x):
     18 	res = 1
     19 	while maxSum(res) < x:
     20 		res += 1
     21 	return res
     22 
     23 def main():
     24 	t = int(input())
     25 	for i in range(t):
     26 		print(getAns(int(input())))
     27 
     28 main()
     29 ```
     30 
     31 [1550B - Maximum Cost Deletion](/contest/1550/problem/B "Educational Codeforces Round 111 (Rated for Div. 2)")
     32 
     33 Idea: [Neon](/profile/Neon "Candidate Master Neon")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (Neon)**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 
     44 using namespace std;
     45 
     46 int main() {
     47   int t;
     48   cin >> t;
     49   while (t--) {
     50     int n, a, b;
     51     string s;
     52     cin >> n >> a >> b >> s;
     53     int m = unique(s.begin(), s.end()) - s.begin();
     54     cout << n * a + max(n * b, (m / 2 + 1) * b) << '\n'; 
     55   }
     56 }
     57 ```
     58 
     59 [1550C - Manhattan Subarrays](/contest/1550/problem/C "Educational Codeforces Round 111 (Rated for Div. 2)")
     60 
     61 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution (adedalic)**
     68 
     69 ```
     70 #include<bits/stdc++.h>
     71 
     72 using namespace std;
     73 
     74 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     75 #define sz(a) int((a).size())
     76 
     77 #define x first
     78 #define y second
     79 
     80 typedef long long li;
     81 typedef long double ld;
     82 typedef pair<li, li> pt;
     83 
     84 const int INF = int(1e9);
     85 const li INF64 = li(1e18);
     86 const ld EPS = 1e-9;
     87 
     88 int n;
     89 vector<li> a;
     90 
     91 inline bool read() {
     92 	if(!(cin >> n))
     93 		return false;
     94 	a.resize(n);
     95 	fore (i, 0, n)
     96 		cin >> a[i];
     97 	return true;
     98 }
     99 
    100 li d(const pt &a, const pt &b) {
    101 	return abs(a.x - b.x) + abs(a.y - b.y);
    102 }
    103 
    104 inline void solve() {
    105 	li ans = 0;
    106 	fore (i, 0, n) {
    107 		fore (j, i, n) {
    108 			if (i + 2 <= j) {
    109 				bool ok = true;
    110 				fore (i1, i, j) fore (i2, i1 + 1, j) {
    111 					if (d(pt(a[i1], i1), pt(a[j], j)) == d(pt(a[i1], i1), pt(a[i2], i2)) + d(pt(a[i2], i2), pt(a[j], j)))
    112 						ok = false;
    113 				}
    114 				if (!ok)
    115 					break;
    116 			}
    117 			ans++;
    118 		}
    119 	}
    120 	cout << ans << endl;
    121 }
    122 
    123 int main() {
    124 #ifdef _DEBUG
    125 	freopen("input.txt", "r", stdin);
    126 	int tt = clock();
    127 #endif
    128 	ios_base::sync_with_stdio(false);
    129 	cin.tie(0), cout.tie(0);
    130 	cout << fixed << setprecision(15);
    131 
    132 	int t; cin >> t;
    133 	
    134 	while(t--) {
    135 		read();
    136 		solve();
    137 		
    138 #ifdef _DEBUG
    139 		cerr << "TIME = " << clock() - tt << endl;
    140 		tt = clock();
    141 #endif
    142 	}
    143 	return 0;
    144 }
    145 ```
    146 
    147 [1550D - Excellent Arrays](/contest/1550/problem/D "Educational Codeforces Round 111 (Rated for Div. 2)")
    148 
    149 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    150 
    151 **Tutorial**
    152 
    153 Tutorial is loading...
    154 
    155 **Solution (adedalic)**
    156 
    157 ```
    158 #include<bits/stdc++.h>
    159 
    160 using namespace std;
    161 
    162 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    163 #define sz(a) int((a).size())
    164 
    165 const int MOD = int(1e9) + 7;
    166 
    167 int norm(int a) {
    168 	while (a >= MOD)
    169 		a -= MOD;
    170 	while (a < 0)
    171 		a += MOD;
    172 	return a;
    173 }
    174 int mul(int a, int b) {
    175 	return int(a * 1ll * b % MOD);
    176 }
    177 int binPow(int a, int k) {
    178 	int ans = 1;
    179 	while (k > 0) {
    180 		if (k & 1)
    181 			ans = mul(ans, a);
    182 		a = mul(a, a);
    183 		k >>= 1;
    184 	}
    185 	return ans;
    186 }
    187 
    188 const int N = 200 * 1000 + 55;
    189 int f[N], inf[N];
    190 
    191 void precalc() {
    192 	f[0] = inf[0] = 1;
    193 	fore (i, 1, N) {
    194 		f[i] = mul(f[i - 1], i);
    195 		inf[i] = binPow(f[i], MOD - 2);
    196 	}
    197 }
    198 
    199 int C(int n, int k) {
    200 	if (k < 0 || n < k)
    201 		return 0;
    202 	return mul(f[n], mul(inf[n - k], inf[k]));
    203 }
    204 
    205 int n, l, r;
    206 
    207 inline bool read() {
    208 	if(!(cin >> n >> l >> r))
    209 		return false;
    210 	return true;
    211 }
    212 
    213 inline void solve() {
    214 	int half = n / 2;
    215 	int st = min(1 - l, r - n);
    216 	
    217 	int ans = mul(st, C(n, half));
    218 	if (n & 1)
    219 		ans = norm(ans + mul(st, C(n, half + 1)));
    220 	
    221 	for (int k = st + 1; ; k++) {
    222 		int lf = max(1, l + k);
    223 		int rg = min(n, r - k);
    224 		
    225 		if (rg + 1 - lf < 0)
    226 			break;
    227 		
    228 		ans = norm(ans + C(rg + 1 - lf, half - (lf - 1)));
    229 		if (n & 1)
    230 			ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1)));
    231 	}
    232 	
    233 	cout << ans << endl;
    234 }
    235 
    236 int main() {
    237 #ifdef _DEBUG
    238 	freopen("input.txt", "r", stdin);
    239 	int tt = clock();
    240 #endif
    241 	ios_base::sync_with_stdio(false);
    242 	cin.tie(0), cout.tie(0);
    243 	cout << fixed << setprecision(15);
    244 	
    245 	precalc();
    246 	int t; cin >> t;
    247 	while (t--) {
    248 		read();
    249 		solve();
    250 		
    251 #ifdef _DEBUG
    252 		cerr << "TIME = " << clock() - tt << endl;
    253 		tt = clock();
    254 #endif
    255 	}
    256 	return 0;
    257 }
    258 ```
    259 
    260 [1550E - Stringforces](/contest/1550/problem/E "Educational Codeforces Round 111 (Rated for Div. 2)")
    261 
    262 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Solution (awoo)**
    269 
    270 ```
    271 #include <bits/stdc++.h>
    272 
    273 #define forn(i, n) for (int i = 0; i < int(n); i++)
    274 
    275 using namespace std;
    276 
    277 int n, k;
    278 string s;
    279 
    280 bool check(int d){
    281 	vector<int> lst(k, n);
    282 	vector<vector<int>> pos(n + 1, vector<int>(k, n + 1));
    283 	for (int i = n - 1; i >= 0; --i){
    284 		if (s[i] != '?'){
    285 			lst[s[i] - 'a'] = i;
    286 		}
    287 		int cur = n;
    288 		forn(j, k){
    289 			pos[i][j] = (i + d <= cur ? i + d : pos[i + 1][j]);
    290 			cur = min(cur, lst[j]);
    291 		}
    292 		cur = n;
    293 		for (int j = k - 1; j >= 0; --j){
    294 			if (i + d > cur) pos[i][j] = pos[i + 1][j];
    295 			cur = min(cur, lst[j]);
    296 		}
    297 	}
    298 	vector<int> dp(1 << k, n + 1);
    299 	dp[0] = 0;
    300 	forn(mask, 1 << k) if (dp[mask] < n + 1){
    301 		forn(i, k) if (!((mask >> i) & 1))
    302 			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], pos[dp[mask]][i]);
    303 	}
    304 	return dp[(1 << k) - 1] <= n;
    305 }
    306 
    307 int main() {
    308 	cin >> n >> k;
    309 	cin >> s;
    310 	int l = 1, r = n;
    311 	int res = 0;
    312 	while (l <= r){
    313 		int m = (l + r) / 2;
    314 		if (check(m)){
    315 			res = m;
    316 			l = m + 1;
    317 		}
    318 		else{
    319 			r = m - 1;
    320 		}
    321 	}
    322 	cout << res << endl;
    323 	return 0;
    324 }
    325 ```
    326 
    327 [1550F - Jumping Around](/contest/1550/problem/F "Educational Codeforces Round 111 (Rated for Div. 2)")
    328 
    329 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    330 
    331 **Tutorial**
    332 
    333 Tutorial is loading...
    334 
    335 **Solution 1 (awoo)**
    336 
    337 ```
    338 #include <bits/stdc++.h>
    339 
    340 #define forn(i, n) for (int i = 0; i < int(n); i++)
    341 
    342 using namespace std;
    343 
    344 const int INF = 1e9;
    345 
    346 struct edge2{
    347 	int u, w;
    348 };
    349 
    350 vector<vector<edge2>> g;
    351 
    352 struct edge3{
    353 	int v, u, w;
    354 };
    355 
    356 bool operator <(const edge3 &a, const edge3 &b){
    357 	if (a.w != b.w)
    358 		return a.w < b.w;
    359 	if (min(a.v, a.u) != min(b.v, b.u))
    360 		return min(a.v, a.u) < min(b.v, b.u);
    361 	return max(a.v, a.u) < max(b.v, b.u);
    362 }
    363 
    364 vector<vector<int>> comps;
    365 vector<int> p;
    366 
    367 bool unite(int a, int b){
    368 	a = p[a], b = p[b];
    369 	if (a == b) return false;
    370 	if (comps[a].size() < comps[b].size()) swap(a, b);
    371 	for (int v : comps[b]){
    372 		p[v] = a;
    373 		comps[a].push_back(v);
    374 	}
    375 	comps[b].clear();
    376 	return true;
    377 }
    378 
    379 vector<int> mn;
    380 
    381 void dfs(int v, int p, int d){
    382 	mn[v] = d;
    383 	for (auto e : g[v]) if (e.u != p)
    384 		dfs(e.u, v, max(d, e.w));
    385 }
    386 
    387 int main() {
    388 	int n, q, s, d;
    389 	scanf("%d%d%d%d", &n, &q, &s, &d);
    390 	--s;
    391 	vector<int> a(n);
    392 	forn(i, n) scanf("%d", &a[i]);
    393 	vector<int> idx(a[n - 1] + 1);
    394 	forn(i, n) idx[a[i]] = i;
    395 	comps.resize(n);
    396 	p.resize(n);
    397 	forn(i, n) comps[i] = vector<int>(1, i), p[i] = i;
    398 	g.resize(n);
    399 	set<int> pos(a.begin(), a.end());
    400 	int cnt = n;
    401 	while (cnt > 1){
    402 		vector<edge3> es;
    403 		for (const vector<int> &comp : comps) if (!comp.empty()){
    404 			for (int i : comp)
    405 				pos.erase(a[i]);
    406 			edge3 mn = {-1, -1, INF};
    407 			for (int i : comp){
    408 				for (int dx : {-d, d}){
    409 					auto it = pos.lower_bound(a[i] + dx);
    410 					if (it != pos.end())
    411 						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
    412 					if (it != pos.begin()){
    413 						--it;
    414 						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
    415 					}
    416 				}
    417 			}
    418 			for (int i : comp)
    419 				pos.insert(a[i]);
    420 			assert(mn.v != -1);
    421 			es.push_back(mn);
    422 		}
    423 		for (auto e : es){
    424 			if (unite(e.v, e.u)){
    425 				--cnt;
    426 				g[e.v].push_back({e.u, e.w});
    427 				g[e.u].push_back({e.v, e.w});
    428 			}
    429 		}
    430 	}
    431 	mn.resize(n);
    432 	dfs(s, -1, 0);
    433 	forn(_, q){
    434 		int i, k;
    435 		scanf("%d%d", &i, &k);
    436 		--i;
    437 		puts(mn[i] <= k ? "Yes" : "No");
    438 	}
    439 	return 0;
    440 }
    441 ```
    442 
    443 **Solution 2 (awoo)**
    444 
    445 ```
    446 #include <bits/stdc++.h>
    447 
    448 #define forn(i, n) for (int i = 0; i < int(n); i++)
    449 
    450 using namespace std;
    451 
    452 const int INF = 1e9;
    453 
    454 struct edge2{
    455 	int u, w;
    456 };
    457 
    458 vector<vector<edge2>> g;
    459 
    460 struct edge3{
    461 	int v, u, w;
    462 	edge3(){}
    463 	edge3(int v, int u, int w) : v(v), u(u), w(w) {
    464 		if (v > u) swap(v, u);
    465 	}
    466 };
    467 
    468 bool operator <(const edge3 &a, const edge3 &b){
    469 	if (a.w != b.w)
    470 		return a.w < b.w;
    471 	if (a.v != b.v)
    472 		return a.v < b.v;
    473 	return a.u < b.u;
    474 }
    475 
    476 vector<int> p, rk;
    477 
    478 int getp(int a){
    479 	return a == p[a] ? a : p[a] = getp(p[a]);
    480 }
    481 
    482 bool unite(int a, int b){
    483 	a = getp(a), b = getp(b);
    484 	if (a == b) return false;
    485 	if (rk[a] < rk[b]) swap(a, b);
    486 	rk[a] += rk[b];
    487 	p[b] = a;
    488 	return true;
    489 }
    490 
    491 vector<int> mn;
    492 
    493 void dfs(int v, int p, int d){
    494 	mn[v] = d;
    495 	for (auto e : g[v]) if (e.u != p)
    496 		dfs(e.u, v, max(d, e.w));
    497 }
    498 
    499 int main() {
    500 	int n, q, s, d;
    501 	scanf("%d%d%d%d", &n, &q, &s, &d);
    502 	--s;
    503 	vector<int> a(n);
    504 	forn(i, n) scanf("%d", &a[i]);
    505 	p.resize(n);
    506 	rk.resize(n);
    507 	forn(i, n) rk[i] = 1, p[i] = i;
    508 	g.resize(n);
    509 	int cnt = n;
    510 	int iter = 0;
    511 	while (cnt > 1){
    512 		++iter;
    513 		vector<edge3> es(n, edge3(-1, -1, INF));
    514 		int j, mn1, mn2;
    515 		j = 0, mn1 = -1, mn2 = -1;
    516 		forn(i, n) getp(i);
    517 		forn(i, n){
    518 			while (j < n && a[i] - a[j] > d){
    519 				if (mn1 == -1 || p[mn1] == p[j])
    520 					mn1 = j;
    521 				else{
    522 					mn2 = mn1;
    523 					mn1 = j;
    524 				}
    525 				++j;
    526 			}
    527 			if (mn1 != -1 && p[mn1] != p[i]){
    528 				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
    529 			}
    530 			if (mn2 != -1 && p[mn2] != p[i]){
    531 				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
    532 			}
    533 		}
    534 		j = 0, mn1 = -1, mn2 = -1;
    535 		forn(i, n){
    536 			while (j < n && a[j] - a[i] <= d){
    537 				if (mn1 == -1 || p[mn1] == p[j])
    538 					mn1 = j;
    539 				else{
    540 					mn2 = mn1;
    541 					mn1 = j;
    542 				}
    543 				++j;
    544 			}
    545 			if (mn1 != -1 && p[mn1] != p[i]){
    546 				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
    547 			}
    548 			if (mn2 != -1 && p[mn2] != p[i]){
    549 				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
    550 			}
    551 		}
    552 		j = n - 1, mn1 = -1, mn2 = -1;
    553 		for (int i = n - 1; i >= 0; --i){
    554 			while (j >= 0 && a[j] - a[i] > d){
    555 				if (mn1 == -1 || p[mn1] == p[j])
    556 					mn1 = j;
    557 				else{
    558 					mn2 = mn1;
    559 					mn1 = j;
    560 				}
    561 				--j;
    562 			}
    563 			if (mn1 != -1 && p[mn1] != p[i]){
    564 				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
    565 			}
    566 			if (mn2 != -1 && p[mn2] != p[i]){
    567 				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
    568 			}
    569 		}
    570 		j = n - 1, mn1 = -1, mn2 = -1;
    571 		for (int i = n - 1; i >= 0; --i){
    572 			while (j >= 0 && a[i] - a[j] <= d){
    573 				if (mn1 == -1 || p[mn1] == p[j])
    574 					mn1 = j;
    575 				else{
    576 					mn2 = mn1;
    577 					mn1 = j;
    578 				}
    579 				--j;
    580 			}
    581 			if (mn1 != -1 && p[mn1] != p[i]){
    582 				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
    583 			}
    584 			if (mn2 != -1 && p[mn2] != p[i]){
    585 				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
    586 			}
    587 		}
    588 		for (auto e : es) if (e.v != -1){
    589 			if (unite(e.v, e.u)){
    590 				--cnt;
    591 				g[e.v].push_back({e.u, e.w});
    592 				g[e.u].push_back({e.v, e.w});
    593 			}
    594 		}
    595 	}
    596 	mn.resize(n);
    597 	dfs(s, -1, 0);
    598 	forn(_, q){
    599 		int i, k;
    600 		scanf("%d%d", &i, &k);
    601 		--i;
    602 		puts(mn[i] <= k ? "Yes" : "No");
    603 	}
    604 	return 0;
    605 }
    606 ```