codeforces-scrape

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

1437.md (13492B)


      1 Source: https://codeforces.com/blog/entry/84149
      2 
      3 [1437A - Marketing Scheme](/contest/1437/problem/A "Educational Codeforces Round 97 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main() {
     15     repeat(readLine()!!.toInt()) {
     16         val (l, r) = readLine()!!.split(' ').map { it.toInt() }
     17         println(if (2 * l > r) "YES" else "NO");
     18     }
     19 }
     20 ```
     21 
     22 [1437B - Reverse Binary Strings](/contest/1437/problem/B "Educational Codeforces Round 97 (Rated for Div. 2)")
     23 
     24 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (adedalic)**
     31 
     32 ```
     33 #include<bits/stdc++.h>
     34 
     35 using namespace std;
     36 
     37 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     38 #define sz(a) int((a).size())
     39 
     40 const int INF = int(1e9);
     41 
     42 int n;
     43 string s;
     44 
     45 inline bool read() {
     46 	if(!(cin >> n >> s))
     47 		return false;
     48 	return true;
     49 }
     50 
     51 int cntSame(const string &s) {
     52 	int ans = 0;
     53 	fore (i, 1, sz(s))
     54 		ans += (s[i - 1] == s[i]);
     55 	assert(ans % 2 == 0);
     56 	return ans / 2;
     57 }
     58 
     59 inline void solve() {
     60 	int ans = INF;
     61 	fore (k, 0, 2) {
     62 		ans = min(ans, cntSame(string(1, '0' + k) + s + string(1, '1' - k)));
     63 	}
     64 	cout << ans << endl;
     65 }
     66 
     67 int main() {
     68 	ios_base::sync_with_stdio(false);
     69 	cin.tie(0), cout.tie(0);
     70 	cout << fixed << setprecision(15);
     71 	
     72 	int tc; cin >> tc;
     73 	while(tc--) {
     74 		assert(read());
     75 		solve();
     76 	}
     77 	return 0;
     78 }
     79 ```
     80 
     81 [1437C - Chef Monocarp](/contest/1437/problem/C "Educational Codeforces Round 97 (Rated for Div. 2)")
     82 
     83 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution 1 (pikmike)**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 
     94 #define forn(i, n) for (int i = 0; i < int(n); i++)
     95 
     96 using namespace std;
     97 
     98 const int INF = 1e9;
     99 
    100 void solve(){
    101 	int n;
    102 	scanf("%d", &n);
    103 	vector<int> t(n);
    104 	forn(i, n){
    105 		scanf("%d", &t[i]);
    106 		--t[i];
    107 	}
    108 	sort(t.begin(), t.end());
    109 	vector<vector<int>> dp(n + 1, vector<int>(2 * n, INF));
    110 	dp[0][0] = 0;
    111 	forn(i, n + 1) forn(j, 2 * n - 1) if (dp[i][j] < INF){
    112 		if (i < n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j));
    113 		dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
    114 	}
    115 	printf("%d\n", dp[n][2 * n - 1]);
    116 }
    117 
    118 int main() {
    119 	int q;
    120 	scanf("%d", &q);
    121 	forn(_, q) solve();
    122 }
    123 ```
    124 
    125 **Solution 2 (pikmike)**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 
    130 #define forn(i, n) for (int i = 0; i < int(n); i++)
    131 
    132 using namespace std;
    133 
    134 template<typename T>
    135 T hungarian(const vector<vector<T>>& cost) {
    136     const T INF = numeric_limits<T>::max();
    137     int n = cost.size(), m = cost[0].size();
    138     vector<T> u(n + 1), v(m + 1), dist(m + 1);
    139     vector<int> p(m + 1), way(m + 1), used(m + 1);
    140     for (int i = 1; i <= n; ++i) {
    141         p[0] = i;
    142         int j0 = 0;
    143         fill(dist.begin(), dist.end(), INF);
    144         do {
    145             used[j0] = i;
    146             int i0 = p[j0], j1 = -1;
    147             T delta = INF;
    148             for (int j = 1; j <= m; ++j) if (used[j] != i) {
    149                 T cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
    150                 if (cur < dist[j]) dist[j] = cur, way[j] = j0;
    151                 if (dist[j] < delta) delta = dist[j], j1 = j;
    152             }
    153             forn(j, m + 1) {
    154                 if (used[j] == i) u[p[j]] += delta, v[j] -= delta;
    155                 else dist[j] -= delta;
    156             }
    157             j0 = j1;
    158         } while (p[j0] != 0);
    159         for (int j1; j0; j0 = j1)
    160             p[j0] = p[j1 = way[j0]];
    161     }
    162     
    163     return -v[0];
    164 }
    165 
    166 void solve(){
    167 	int n;
    168 	scanf("%d", &n);
    169 	vector<int> t(n);
    170 	forn(i, n){
    171 		scanf("%d", &t[i]);
    172 		--t[i];
    173 	}
    174 	vector<vector<int>> cost(n, vector<int>(2 * n));
    175 	forn(i, n) forn(j, 2 * n) cost[i][j] = abs(t[i] - j);
    176 	printf("%d\n", hungarian(cost));
    177 }
    178 
    179 int main() {
    180 	int q;
    181 	scanf("%d", &q);
    182 	forn(_, q) solve();
    183 }
    184 ```
    185 
    186 [1437D - Minimal Height Tree](/contest/1437/problem/D "Educational Codeforces Round 97 (Rated for Div. 2)")
    187 
    188 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution (adedalic)**
    195 
    196 ```
    197 #include<bits/stdc++.h>
    198 
    199 using namespace std;
    200 
    201 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    202 #define sz(a) int((a).size())
    203 
    204 #define x first
    205 #define y second
    206 
    207 typedef long long li;
    208 typedef pair<int, int> pt;
    209 
    210 const int INF = int(1e9);
    211 const li INF64 = li(1e18);
    212 
    213 int n;
    214 vector<int> a;
    215 
    216 inline bool read() {
    217 	if(!(cin >> n))
    218 		return false;
    219 	a.resize(n);
    220 	fore (i, 0, n)
    221 		cin >> a[i];
    222 	return true;
    223 }
    224 
    225 inline void solve() {
    226 	vector<int> h(n, INF);
    227 	h[0] = 0;
    228 	int lst = 0;
    229 	fore (i, 1, n) {
    230 		if (i - 1 > 0 && a[i - 1] > a[i])
    231 			lst++;
    232 		h[i] = h[lst] + 1;
    233 	}
    234 	cout << h[n - 1] << endl;
    235 }
    236 
    237 int main() {
    238 #ifdef _DEBUG
    239 	freopen("input.txt", "r", stdin);
    240 	int tt = clock();
    241 #endif
    242 	ios_base::sync_with_stdio(false);
    243 	cin.tie(0), cout.tie(0);
    244 	cout << fixed << setprecision(15);
    245 	
    246 	int tc; cin >> tc;
    247 	while(tc--) {
    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 [1437E - Make It Increasing](/contest/1437/problem/E "Educational Codeforces Round 97 (Rated for Div. 2)")
    261 
    262 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Solution (Ne0n25)**
    269 
    270 ```
    271 #include <bits/stdc++.h>
    272 
    273 using namespace std;
    274 
    275 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    276 
    277 const int N = 500 * 1000 + 13;
    278 
    279 int n, k;
    280 int a[N], b[N];
    281 
    282 int main() {
    283 	scanf("%d%d", &n, &k);
    284 	forn(i, n) scanf("%d", &a[i + 1]);
    285 	a[0] = -1e9;
    286 	a[n + 1] = 2e9;
    287 	forn(i, n + 2) a[i] -= i;
    288 	forn(i, k) scanf("%d", &b[i + 1]);
    289 	b[k + 1] = n + 1;
    290 	
    291 	int ans = 0;
    292 	forn(i, k + 1) {
    293 		int l = b[i], r = b[i + 1];
    294 		if (a[l] > a[r]) {
    295 			puts("-1");
    296 			return 0;
    297 		}
    298 		vector<int> lis;
    299 		for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) {
    300 			auto pos = upper_bound(lis.begin(), lis.end(), a[j]);
    301 			if (pos == lis.end()) lis.push_back(a[j]);
    302 			else *pos = a[j];
    303 		}
    304 		ans += (r - l - 1) - int(lis.size());
    305 	}
    306 	
    307 	printf("%d\n", ans);
    308 }
    309 ```
    310 
    311 [1437F - Emotional Fishermen](/contest/1437/problem/F "Educational Codeforces Round 97 (Rated for Div. 2)")
    312 
    313 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution (BledDest)**
    320 
    321 ```
    322 #include<bits/stdc++.h>
    323 
    324 using namespace std;
    325 
    326 const int N = 5043;
    327 const int MOD = 998244353;
    328 
    329 int dp[N][N];
    330 int pdp[N][N];
    331 int cntLess[N];
    332 int lastLess[N];
    333 int a[N];
    334 int n;
    335 
    336 int add(int x, int y)
    337 {
    338  	x += y;
    339  	while(x >= MOD) x -= MOD;
    340  	while(x < 0) x += MOD;
    341  	return x;
    342 }
    343 
    344 int sub(int x, int y)
    345 {
    346  	return add(x, MOD - y);
    347 }
    348 
    349 int mul(int x, int y)
    350 {
    351  	return (x * 1ll * y) % MOD;
    352 }
    353 
    354 int main()
    355 {
    356 	cin >> n;
    357 	for(int i = 0; i < n; i++)
    358 		cin >> a[i];
    359 	sort(a, a + n);
    360 	for(int i = 0; i < n; i++)
    361 	{
    362 	 	cntLess[i] = 0;
    363 	 	lastLess[i] = -1;
    364 	 	for(int j = 0; j < n; j++)
    365 	 		if(a[j] * 2 <= a[i])
    366 	 		{
    367 	 		 	lastLess[i] = j;
    368 	 		 	cntLess[i]++;
    369 	 		}
    370 	}
    371 	for(int i = 0; i < n; i++)
    372 	{
    373 	 	dp[i][1] = 1;
    374 	 	pdp[i + 1][1] = add(pdp[i][1], dp[i][1]);
    375 	}
    376 	for(int k = 2; k <= n; k++)
    377 		for(int i = 0; i < n; i++)
    378 		{
    379 			if(cntLess[i] + 1 >= k)
    380 		 		dp[i][k] = add(mul(dp[i][k - 1], add(cntLess[i], sub(2, k))), pdp[lastLess[i] + 1][k - 1]);
    381 		 	else
    382 		 		dp[i][k] = 0;
    383 		 	//cerr << i << " " << k << " " << dp[i][k] << endl;                                
    384 		 	pdp[i + 1][k] = add(pdp[i][k], dp[i][k]);
    385 		}
    386 
    387 	cout << dp[n - 1][n] << endl;
    388 }
    389 ```
    390 
    391 [1437G - Death DBMS](/contest/1437/problem/G "Educational Codeforces Round 97 (Rated for Div. 2)")
    392 
    393 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    394 
    395 **Tutorial**
    396 
    397 Tutorial is loading...
    398 
    399 **Solution 1 (pikmike)**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 
    404 #define forn(i, n) for (int i = 0; i < int(n); i++)
    405 
    406 using namespace std;
    407 
    408 const int AL = 26;
    409 
    410 vector<int> val;
    411 vector<int> pos;
    412 
    413 struct aho_corasick {
    414 	struct node {
    415 		map<int, int> nxt, go;
    416 		int p, pch;
    417 		int suf, ssuf;
    418 		multiset<int> vals;
    419 		bool term;
    420 		
    421 		node() {
    422 			nxt.clear();
    423 			go.clear();
    424 			suf = ssuf = -1;
    425 			term = false;
    426 			vals.clear();
    427 			p = -1, pch = -1;
    428 		}
    429 	};
    430 
    431 	vector<node> nodes;
    432 	
    433 	aho_corasick() {
    434 		nodes = vector<node>(1, node());
    435 	}
    436 
    437 	int add(const string& s) {
    438 		int v = 0;
    439 		forn(i, s.size()) {
    440 			int c = s[i] - 'a';
    441 			if (!nodes[v].nxt.count(c)) {
    442 				nodes.push_back(node());
    443 				nodes[v].nxt[c] = int(nodes.size()) - 1;
    444 				nodes.back().p = v;
    445 				nodes.back().pch = c;
    446 			}
    447 			v = nodes[v].nxt[c];
    448 		}
    449 		nodes[v].term = true;
    450 		nodes[v].vals.insert(0);
    451 		return v;
    452 	}
    453 	
    454 	int feed(const string &s){
    455 		int v = 0;
    456 		int ans = -1;
    457 		forn(i, s.size()){
    458 			int c = s[i] - 'a';
    459 			v = go(v, c);
    460 			int u = v;
    461 			while (u != 0){
    462 				if (!nodes[u].vals.empty())
    463 					ans = max(ans, *nodes[u].vals.rbegin());
    464 				u = ssuf(u);
    465 			}
    466 		}
    467 		return ans;
    468 	}
    469 	
    470 	int go(int v, int c) {
    471 		if (nodes[v].go.count(c))
    472 			return nodes[v].go[c];
    473 		if (nodes[v].nxt.count(c))
    474 			return nodes[v].go[c] = nodes[v].nxt[c];
    475 		if (v == 0)
    476 			return nodes[v].go[c] = 0;
    477 		return nodes[v].go[c] = go(suf(v), c);
    478 	}
    479 	
    480 	int suf(int v) {
    481 		if (nodes[v].suf != -1)
    482 			return nodes[v].suf;
    483 		if (v == 0 || nodes[v].p == 0)
    484 			return nodes[v].suf = 0;
    485 		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    486 	}
    487 	
    488 	int ssuf(int v) {
    489 		if (nodes[v].ssuf != -1)
    490 			return nodes[v].ssuf;
    491 		if (v == 0 || nodes[v].p == 0)
    492 			return nodes[v].ssuf = 0;
    493 		int s = suf(v);
    494 		if (nodes[s].term)
    495 			return nodes[v].ssuf = s;
    496 		return nodes[v].ssuf = ssuf(s);
    497 	}
    498 };
    499 
    500 aho_corasick ac;
    501 
    502 int main() {
    503 	int n, m;
    504 	ios::sync_with_stdio(!cin.tie(0));
    505 	cin >> n >> m;
    506 	pos.resize(n);
    507 	val.resize(n, 0);
    508 	
    509 	vector<int> tp2;
    510 	
    511 	ac = aho_corasick();
    512 	
    513 	forn(i, n){
    514 		string s;
    515 		cin >> s;
    516 		pos[i] = ac.add(s);
    517 	}
    518 	
    519 	forn(i, m){
    520 		int t;
    521 		cin >> t;
    522 		if (t == 1){
    523 			int j, x;
    524 			cin >> j >> x;
    525 			--j;
    526 			ac.nodes[pos[j]].vals.erase(ac.nodes[pos[j]].vals.find(val[j]));
    527 			val[j] = x;
    528 			ac.nodes[pos[j]].vals.insert(val[j]);
    529 		}
    530 		else{
    531 			string q;
    532 			cin >> q;
    533 			printf("%d\n", ac.feed(q));
    534 		}
    535 	}
    536 	
    537 	return 0;
    538 }
    539 ```
    540 
    541 **Solution 2 (pikmike)**
    542 
    543 ```
    544 #include <bits/stdc++.h>
    545 
    546 #define forn(i, n) for (int i = 0; i < int(n); i++)
    547 
    548 using namespace std;
    549 
    550 const int AL = 26;
    551 vector<vector<pair<int, int>>> upd;
    552 vector<int> ans;
    553 int n, m;
    554 
    555 struct segtree{
    556 	vector<int*> where;
    557 	vector<int> vals;
    558 	vector<int> t;
    559 	int n;
    560 	
    561 	segtree(){}
    562 	
    563 	segtree(int n) : n(n){
    564 		t.assign(4 * n, -1);
    565 		where.clear();
    566 		vals.clear();
    567 	}
    568 	
    569 	void updh(int v, int l, int r, int L, int R, int val){
    570 		if (L >= R)
    571 			return;
    572 		if (l == L && r == R){
    573 			where.push_back(&t[v]);
    574 			vals.push_back(t[v]);
    575 			t[v] = max(t[v], val);
    576 			return;
    577 		}
    578 		int m = (l + r) / 2;
    579 		updh(v * 2, l, m, L, min(m, R), val);
    580 		updh(v * 2 + 1, m, r, max(m, L), R, val);
    581 	}
    582 	
    583 	void upd(int l, int r, int val){
    584 		updh(1, 0, n, l, r, val);
    585 	}
    586 	
    587 	int geth(int v, int l, int r, int pos){
    588 		if (l == r - 1)
    589 			return t[v];
    590 		int m = (l + r) / 2;
    591 		if (pos < m)
    592 			return max(t[v], geth(v * 2, l, m, pos));
    593 		return max(t[v], geth(v * 2 + 1, m, r, pos));
    594 	}
    595 	
    596 	int get(int pos){
    597 		return geth(1, 0, n, pos);
    598 	}
    599 	
    600 	void rollback(){
    601 		*where.back() = vals.back();
    602 		where.pop_back();
    603 		vals.pop_back();
    604 	}
    605 };
    606 
    607 segtree st;
    608 
    609 struct aho_corasick {
    610 	struct node {
    611 		map<int, int> nxt, go;
    612 		int p, pch;
    613 		int suf, ssuf;
    614 		vector<int> term, qs;
    615 		
    616 		node() {
    617 			nxt.clear();
    618 			go.clear();
    619 			suf = ssuf = -1;
    620 			term.clear();
    621 			p = -1, pch = -1;
    622 			qs.clear();
    623 		}
    624 	};
    625 
    626 	vector<node> nodes;
    627 	vector<vector<int>> g;
    628 	
    629 	aho_corasick() {
    630 		nodes = vector<node>(1, node());
    631 	}
    632 
    633 	void add(const string& s, int id) {
    634 		int v = 0;
    635 		forn(i, s.size()) {
    636 			int c = s[i] - 'a';
    637 			if (!nodes[v].nxt.count(c)) {
    638 				nodes.push_back(node());
    639 				nodes[v].nxt[c] = int(nodes.size()) - 1;
    640 				nodes.back().p = v;
    641 				nodes.back().pch = c;
    642 			}
    643 			v = nodes[v].nxt[c];
    644 		}
    645 		nodes[v].term.push_back(id);
    646 	}
    647 	
    648 	void feed(const string &s, int id){
    649 		int v = 0;
    650 		forn(i, s.size()){
    651 			int c = s[i] - 'a';
    652 			v = go(v, c);
    653 			nodes[v].qs.push_back(id);
    654 		}
    655 	}
    656 	
    657 	int go(int v, int c) {
    658 		if (nodes[v].go.count(c))
    659 			return nodes[v].go[c];
    660 		if (nodes[v].nxt.count(c))
    661 			return nodes[v].go[c] = nodes[v].nxt[c];
    662 		if (v == 0)
    663 			return nodes[v].go[c] = 0;
    664 		return nodes[v].go[c] = go(suf(v), c);
    665 	}
    666 	
    667 	int suf(int v) {
    668 		if (nodes[v].suf != -1)
    669 			return nodes[v].suf;
    670 		if (v == 0 || nodes[v].p == 0)
    671 			return nodes[v].suf = 0;
    672 		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    673 	}
    674 	
    675 	void build_tree() {
    676 		g.resize(nodes.size());
    677 		forn(v, nodes.size()) {
    678 			int u = suf(v);
    679 			if (v != u)
    680 				g[u].push_back(v);
    681 		}
    682 	}
    683 	
    684 	void dfs(int v){
    685 		int cur = st.where.size();
    686 		for (auto i : nodes[v].term){
    687 			int lst = m;
    688 			for (auto it : upd[i]){
    689 				st.upd(it.first, lst, it.second);
    690 				lst = it.first;
    691 			}
    692 			st.upd(0, lst, 0);
    693 		}
    694 		for (auto j : nodes[v].qs){
    695 			ans[j] = max(ans[j], st.get(j));
    696 		}
    697 		for (int u : g[v]){
    698 			dfs(u);
    699 		}
    700 		int nw = st.where.size();
    701 		forn(_, nw - cur){
    702 			st.rollback();
    703 		}
    704 	}
    705 };
    706 
    707 aho_corasick ac;
    708 
    709 int main() {
    710 	ios::sync_with_stdio(!cin.tie(0));
    711 	cin >> n >> m;
    712 	upd.resize(n);
    713 	ans.resize(m, -1);
    714 	
    715 	vector<int> tp2;
    716 	
    717 	ac = aho_corasick();
    718 	st = segtree(m);
    719 	
    720 	forn(i, n){
    721 		string s;
    722 		cin >> s;
    723 		ac.add(s, i);
    724 	}
    725 	forn(i, m){
    726 		int t;
    727 		cin >> t;
    728 		if (t == 1){
    729 			int j, x;
    730 			cin >> j >> x;
    731 			--j;
    732 			upd[j].push_back(make_pair(i, x));
    733 		}
    734 		else{
    735 			string q;
    736 			cin >> q;
    737 			ac.feed(q, i);
    738 			tp2.push_back(i);
    739 		}
    740 	}
    741 	forn(i, n){
    742 		reverse(upd[i].begin(), upd[i].end());
    743 	}
    744 	
    745 	ac.build_tree();
    746 	ac.dfs(0);
    747 	for (auto it : tp2)
    748 		cout << ans[it] << "\n";
    749 	return 0;
    750 }
    751 ```