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 ```