codeforces-scrape

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

2025.md (8703B)


      1 Source: https://codeforces.com/blog/entry/135173
      2 
      3 [2025A - Two Screens](/contest/2025/problem/A "Educational Codeforces Round 170 (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 for _ in range(int(input())):
     15 	s = input()
     16 	t = input()
     17 
     18 	lcp = 0
     19 	n = len(s)
     20 	m = len(t)
     21 	for i in range(1, min(n, m) + 1):
     22 		if s[:i] == t[:i]:
     23 			lcp = i
     24 	print(n + m - max(lcp, 1) + 1)
     25 ```
     26 
     27 [2025B - Binomial Coefficients, Kind Of](/contest/2025/problem/B "Educational Codeforces Round 170 (Rated for Div. 2)")
     28 
     29 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution (adedalic)**
     36 
     37 ```
     38 #include<bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 const int MOD = int(1e9) + 7;
     43 
     44 int main() {
     45 	int t; cin >> t;
     46 	vector<int> ks(t);
     47 	for (int _ = 0; _ < 2; _++)
     48 		for (int i = 0; i < t; i++)
     49 			cin >> ks[i];
     50 	
     51 	vector<int> ans(1 + *max_element(ks.begin(), ks.end()), 1);
     52 	for (int i = 1; i < (int)ans.size(); i++)
     53 		ans[i] = (2LL * ans[i - 1]) % MOD;
     54 	
     55 	for (int k : ks)
     56 		cout << ans[k] << '\n';
     57 	return 0;
     58 }
     59 ```
     60 
     61 [2025C - New Game](/contest/2025/problem/C "Educational Codeforces Round 170 (Rated for Div. 2)")
     62 
     63 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (awoo)**
     70 
     71 ```
     72 for _ in range(int(input())):
     73 	n, k = map(int, input().split())
     74 	a = list(map(int, input().split()))
     75 	a.sort()
     76 	ans = 0
     77 	j = 0
     78 	for i in range(n):
     79 		j = max(i, j)
     80 		while j + 1 < n and a[j + 1] - a[j] <= 1 and a[j + 1] - a[i] < k:
     81 			j += 1
     82 		ans = max(ans, j - i + 1)
     83 	print(ans)
     84 ```
     85 
     86 [2025D - Attribute Checks](/contest/2025/problem/D "Educational Codeforces Round 170 (Rated for Div. 2)")
     87 
     88 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution 1 (adedalic)**
     95 
     96 ```
     97 #include<bits/stdc++.h>
     98  
     99 using namespace std;
    100  
    101 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    102 #define sz(a) int((a).size())
    103  
    104 typedef long long li;
    105  
    106 const int INF = int(1e9);
    107 const li INF64 = li(1e18);
    108  
    109 int n, m;
    110 vector<int> rs;
    111  
    112 bool read() {
    113 	if(!(cin >> n >> m))
    114 		return false;
    115 	rs.resize(n);
    116 	fore (i, 0, n)
    117 		cin >> rs[i];
    118 	return true;
    119 }
    120  
    121 struct LazySum {
    122 	vector<int> ps;
    123 	LazySum(int n) : ps(n, 0) {}
    124 	
    125 	//[l, r]
    126 	void add(int l, int r, int val) {
    127 		if (l > r) return;
    128 		ps[l] += val;
    129 		ps[r + 1] -= val;
    130 	}
    131 	void pushToAndClear(vector<int> &d) {
    132 		int sum = 0;
    133 		fore (i, 0, sz(ps)) {
    134 			sum += ps[i];
    135 			ps[i] = 0;
    136 			if (i < sz(d))
    137 				d[i] += sum;
    138 		}
    139 	}
    140 };
    141  
    142 void solve() {
    143 	LazySum ls(m + 2);
    144 	vector<int> d(m + 1, -INF);
    145 	d[0] = 0;
    146  
    147 	int cntP = 0;
    148 	for (int r : rs) {
    149 		if (r == 0) {
    150 			ls.pushToAndClear(d);
    151 			for (int i = m; i > 0; i--)
    152 				d[i] = max(d[i], d[i - 1]);
    153 			cntP++;
    154 			continue;
    155 		}
    156 		if (r > 0)
    157 			ls.add(r, m, 1);
    158 		else
    159 			ls.add(0, cntP + r, 1);
    160 	}
    161 	ls.pushToAndClear(d);
    162 	cout << *max_element(d.begin(), d.end()) << endl;
    163 }
    164  
    165 int main() {
    166 #ifdef _DEBUG
    167 	freopen("input.txt", "r", stdin);
    168 	int tt = clock();
    169 #endif
    170 	ios_base::sync_with_stdio(false);
    171 	cin.tie(0), cout.tie(0);
    172 	cout << fixed << setprecision(15);
    173 	
    174 	if(read()) {
    175 		solve();
    176 		
    177 #ifdef _DEBUG
    178 		cerr << "TIME = " << clock() - tt << endl;
    179 		tt = clock();
    180 #endif
    181 	}
    182 	return 0;
    183 }
    184 ```
    185 
    186 **Solution 2 (adedalic)**
    187 
    188 ```
    189 n, m = map(int, input().split())
    190 rs = map(int, input().split())
    191 
    192 d = [-int(1e9)] * (m + 1)
    193 d[0] = 0
    194 add = [0] * (m + 2)
    195 def addSegment(l, r):
    196     if l <= r:
    197         add[l] += 1
    198         add[r + 1] -= 1
    199 
    200 def pushAll():
    201     sum = 0
    202     for i in range(m + 1):
    203         sum += add[i]
    204         d[i] += sum
    205     for i in range(m + 2):
    206         add[i] = 0
    207 
    208 cntPoints = 0
    209 for r in rs:
    210     if r == 0:
    211         pushAll()
    212         for i in range(m, 0, -1):
    213             d[i] = max(d[i], d[i - 1])
    214         cntPoints += 1
    215     else:
    216         lf, rg = 0, 0
    217         if (r > 0):
    218             lf = min(r, m + 1)
    219             rg = m
    220         else:
    221             lf = 0
    222             rg = max(-1, cntPoints + r)
    223         addSegment(lf, rg)
    224 pushAll()
    225 print(max(d))
    226 ```
    227 
    228 [2025E - Card Game](/contest/2025/problem/E "Educational Codeforces Round 170 (Rated for Div. 2)")
    229 
    230 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution (Neon)**
    237 
    238 ```
    239 #include <bits/stdc++.h>
    240  
    241 using namespace std;
    242  
    243 const int MOD = 998244353;
    244  
    245 int add(int x, int y) {
    246   x += y;
    247   if (x >= MOD) x -= MOD;
    248   return x;
    249 }
    250  
    251 int mul(int x, int y) {
    252   return x * 1LL * y % MOD;
    253 }
    254  
    255 int main() {
    256   int n, m;
    257   cin >> n >> m;
    258   vector<vector<int>> ways(m + 1, vector<int>(m + 1));
    259   ways[0][0] = 1;
    260   for (int i = 0; i < m; ++i) {
    261     for (int j = 0; j <= i; ++j) {
    262       ways[i + 1][j + 1] = add(ways[i + 1][j + 1], ways[i][j]);
    263       if (j) ways[i + 1][j - 1] = add(ways[i + 1][j - 1], ways[i][j]);
    264     }
    265   }
    266   
    267   vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    268   dp[0][0] = 1;
    269   for (int i = 0; i < n; ++i) {
    270     for (int j = 0; j <= m; ++j) {
    271       for (int k = 0; k <= m; ++k) {
    272         int nj = i ? j - k : j + k;
    273         if (0 <= nj && nj <= m) {
    274           dp[i + 1][nj] = add(dp[i + 1][nj], mul(dp[i][j], ways[m][k]));
    275         }
    276       }
    277     }
    278   }
    279   cout << dp[n][0] << '\n';
    280 }
    281 ```
    282 
    283 [2025F - Choose Your Queries](/contest/2025/problem/F "Educational Codeforces Round 170 (Rated for Div. 2)")
    284 
    285 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    286 
    287 **Tutorial**
    288 
    289 Tutorial is loading...
    290 
    291 **Solution (BledDest)**
    292 
    293 ```
    294 #include<bits/stdc++.h>
    295  
    296 using namespace std;
    297  
    298 const int N = 300043;
    299  
    300 string choice = "xy";
    301 string sign = "+-";
    302  
    303 int qs[N][2];
    304 string ans[N];
    305 int n, q;
    306 vector<int> g[N];
    307 int color[N];
    308  
    309 void pair_queries(int q1, int q2)
    310 {
    311  	if(q1 > q2) swap(q1, q2);
    312  	for(int i = 0; i < 2; i++)
    313  		for(int j = 0; j < 2; j++)
    314  			if(qs[q1][i] == qs[q2][j])
    315  			{
    316  			 	ans[q1] = { choice[i], sign[0] };
    317  			 	ans[q2] = { choice[j], sign[1] };
    318  			 	return;
    319  			}
    320 }
    321  
    322 bool dfs(int v, int pe = -1)
    323 {
    324  	// return true if parent edge still exists
    325  	color[v] = 1;
    326  	vector<int> edge_nums;
    327  	for(auto e : g[v])
    328  	{
    329  		int u = v ^ qs[e][0] ^ qs[e][1];
    330  		if(color[u] == 1) continue;
    331  		if(color[u] == 0)
    332  		{
    333  			if(dfs(u, e))
    334  				edge_nums.push_back(e);
    335  		}
    336  		else
    337  			edge_nums.push_back(e);
    338  	}
    339  	bool res = true;
    340  	if(edge_nums.size() % 2 != 0)
    341  	{
    342  		if(pe != -1) edge_nums.push_back(pe);
    343  		else edge_nums.pop_back();
    344  		res = false;
    345  	}
    346  	for(int i = 0; i < edge_nums.size(); i += 2)
    347  		pair_queries(edge_nums[i], edge_nums[i + 1]);
    348  	color[v] = 2;
    349  	return res;
    350 }
    351  
    352 int main()
    353 {
    354 	ios_base::sync_with_stdio(0);
    355 	cin.tie(0);
    356 	cin >> n >> q;
    357 	for(int i = 0; i < q; i++)
    358 	{
    359 	 	cin >> qs[i][0] >> qs[i][1];
    360 	 	--qs[i][0];
    361 	 	--qs[i][1];
    362 	 	g[qs[i][0]].push_back(i);
    363 	 	g[qs[i][1]].push_back(i);
    364 	 	ans[i] = "x+";
    365 	}
    366 	for(int i = 0; i < n; i++)
    367 		if(color[i] == 0)
    368 			dfs(i);
    369 	for(int i = 0; i < q; i++) cout << ans[i] << endl;
    370 }
    371 ```
    372 
    373 [2025G - Variable Damage](/contest/2025/problem/G "Educational Codeforces Round 170 (Rated for Div. 2)")
    374 
    375 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    376 
    377 **Tutorial**
    378 
    379 Tutorial is loading...
    380 
    381 **Solution (awoo)**
    382 
    383 ```
    384 #include <bits/stdc++.h>
    385  
    386 #define forn(i, n) for (int i = 0; i < int(n); i++)
    387  
    388 using namespace std;
    389  
    390 struct query{
    391 	int t, v;
    392 };
    393  
    394 int main() {
    395 	cin.tie(0);
    396 	ios::sync_with_stdio(false);
    397 	int m;
    398 	cin >> m;
    399 	vector<query> q(m);
    400 	forn(i, m) cin >> q[i].t >> q[i].v;
    401 	
    402 	vector<pair<int, int>> xs;
    403 	forn(i, m) xs.push_back({q[i].v, i});
    404 	sort(xs.rbegin(), xs.rend());
    405 	forn(i, m) q[i].v = xs.rend() - lower_bound(xs.rbegin(), xs.rend(), make_pair(q[i].v, i)) - 1;
    406 	
    407 	const int p = sqrt(m + 10);
    408 	const int siz = (m + p - 1) / p;
    409 	
    410 	vector<int> tp(m);
    411 	vector<int> val(m);
    412 	vector<vector<long long>> dp(p, vector<long long>(2 * siz + 1));
    413 	vector<int> blbal(p);
    414 	
    415 	auto upd = [&](const query &q){
    416 		tp[q.v] = q.t;
    417 		val[q.v] = xs[q.v].first;
    418 		blbal[q.v / siz] += q.t == 1 ? 1 : -1;
    419 	};
    420 	
    421 	auto recalc = [&](int b){
    422 		dp[b].assign(2 * siz + 1, 0);
    423 		int bal = 0;
    424 		for (int i = b * siz; i < m && i < (b + 1) * siz; ++i){
    425 			if (tp[i] == 1){
    426 				dp[b][0] += val[i];
    427 				dp[b][0] += val[i];
    428 				dp[b][-bal + siz] -= val[i];
    429 				++bal;
    430 			}
    431 			else if (tp[i] == 2){
    432 				dp[b][-bal + 1 + siz] += val[i];
    433 				--bal;
    434 			}
    435 		}
    436 		forn(i, 2 * siz){
    437 			dp[b][i + 1] += dp[b][i];
    438 		}
    439 	};
    440 	
    441 	auto get = [&](int b, int bal){
    442 		bal += siz;
    443 		if (bal < 0) return dp[b][0];
    444 		if (bal >= 2 * siz + 1) return dp[b].back();
    445 		return dp[b][bal];
    446 	};
    447 	
    448 	for (auto it : q){
    449 		upd(it);
    450 		recalc(it.v / siz);
    451 		int bal = 0;
    452 		long long ans = 0;
    453 		for (int i = 0; i * siz < m; ++i){
    454 			ans += get(i, bal);
    455 			bal += blbal[i];
    456 		}
    457 		cout << ans << '\n';
    458 	}
    459 	
    460 	return 0;
    461 }
    462 ```