1303.md (11492B)
1 Source: https://codeforces.com/blog/entry/73872 2 3 [1303A - Erasing Zeroes](/contest/1303/problem/A "Educational Codeforces Round 82 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for t in range(int(input())): 15 print(input().strip('0').count('0')) 16 ``` 17 18 [1303B - National Project](/contest/1303/problem/B "Educational Codeforces Round 82 (Rated for Div. 2)") 19 20 Idea: [adedalic](/profile/adedalic "International Master adedalic") 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution (adedalic)** 27 28 ``` 29 fun main() { 30 val t = readLine()!!.toInt() 31 for (tc in 1..t) { 32 val (n, g, b) = readLine()!!.split(' ').map { it.toLong() } 33 34 val needG = (n + 1) / 2 35 var totalG = needG / g * (b + g) 36 totalG += if (needG % g == 0L) -b else needG % g 37 println(maxOf(n, totalG)) 38 } 39 } 40 ``` 41 42 [1303C - Perfect Keyboard](/contest/1303/problem/C "Educational Codeforces Round 82 (Rated for Div. 2)") 43 44 Idea: [Roms](/profile/Roms "Master Roms") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution (Ne0n25)** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 #define sz(a) int((a).size()) 58 #define all(a) (a).begin(), (a).end() 59 #define forn(i, n) for (int i = 0; i < int(n); ++i) 60 61 void solve() { 62 string s; 63 cin >> s; 64 65 vector<bool> used(26); 66 used[s[0] - 'a'] = true; 67 string t(1, s[0]); 68 69 int pos = 0; 70 for (int i = 1; i < sz(s); i++) { 71 if (used[s[i] - 'a']) { 72 if (pos > 0 && t[pos - 1] == s[i]) { 73 pos--; 74 } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) { 75 pos++; 76 } else { 77 cout << "NO" << endl; 78 return; 79 } 80 } else { 81 if (pos == 0) { 82 t = s[i] + t; 83 } else if (pos == sz(t) - 1) { 84 t += s[i]; 85 pos++; 86 } else { 87 cout << "NO" << endl; 88 return; 89 } 90 } 91 used[s[i] - 'a'] = true; 92 } 93 94 forn(i, 26) if (!used[i]) 95 t += char(i + 'a'); 96 cout << "YES" << endl << t << endl; 97 } 98 99 int main() { 100 int tc; 101 cin >> tc; 102 103 forn(i, tc) solve(); 104 } 105 ``` 106 107 [1303D - Fill The Bag](/contest/1303/problem/D "Educational Codeforces Round 82 (Rated for Div. 2)") 108 109 Idea: [Roms](/profile/Roms "Master Roms") 110 111 **Tutorial** 112 113 Tutorial is loading... 114 115 **Solution (Roms)** 116 117 ``` 118 from math import log2 119 120 for t in range(int(input())): 121 n, m = map(int, input().split()) 122 c = [0] * 61 123 s = 0 124 for x in map(int, input().split()): 125 c[int(log2(x))] += 1 126 s += x 127 128 if s < n: 129 print(-1) 130 continue 131 132 i, res = 0, 0 133 while i < 60: 134 if (1<<i)&n != 0: 135 if c[i] > 0: 136 c[i] -= 1 137 else: 138 while i < 60 and c[i] == 0: 139 i += 1 140 res += 1 141 c[i] -= 1 142 continue 143 c[i + 1] += c[i] // 2 144 i += 1 145 146 print(res) 147 ``` 148 149 [1303E - Erase Subsequences](/contest/1303/problem/E "Educational Codeforces Round 82 (Rated for Div. 2)") 150 151 Idea: [adedalic](/profile/adedalic "International Master adedalic") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution (adedalic)** 158 159 ``` 160 #include<bits/stdc++.h> 161 162 using namespace std; 163 164 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 165 #define sz(a) int((a).size()) 166 167 #define x first 168 #define y second 169 170 typedef long long li; 171 typedef pair<int, int> pt; 172 173 const int INF = int(1e9); 174 const li INF64 = li(1e18); 175 176 string s, t; 177 178 inline bool read() { 179 if(!(cin >> s >> t)) 180 return false; 181 for(auto &c : s) 182 c -= 'a'; 183 for(auto &c : t) 184 c -= 'a'; 185 return true; 186 } 187 188 vector< vector<int> > nxt; 189 190 bool calc(const string &a, const string &b) { 191 vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF)); 192 dp[0][0] = 0; 193 fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) { 194 if(dp[i][j] > sz(s)) 195 continue; 196 197 int len = dp[i][j]; 198 if(i < sz(a) && nxt[len][a[i]] < INF) { 199 dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1); 200 } 201 if(j < sz(b) && nxt[len][b[j]] < INF) { 202 dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1); 203 } 204 } 205 return dp[sz(a)][sz(b)] < INF; 206 } 207 208 inline void solve() { 209 nxt.assign(sz(s) + 1, vector<int>(26, INF)); 210 for(int i = sz(s) - 1; i >= 0; i--) { 211 nxt[i] = nxt[i + 1]; 212 nxt[i][s[i]] = i; 213 } 214 215 for(int i = 0; i < sz(t); i++) { 216 if(calc(t.substr(0, i), t.substr(i, sz(t)))) { 217 cout << "YES" << endl; 218 return; 219 } 220 } 221 cout << "NO" << endl; 222 } 223 224 int main() { 225 #ifdef _DEBUG 226 freopen("input.txt", "r", stdin); 227 int tt = clock(); 228 #endif 229 ios_base::sync_with_stdio(false); 230 cin.tie(0), cout.tie(0); 231 cout << fixed << setprecision(15); 232 233 int tc; cin >> tc; 234 235 while(tc--) { 236 read(); 237 solve(); 238 239 #ifdef _DEBUG 240 cerr << "TIME = " << clock() - tt << endl; 241 tt = clock(); 242 #endif 243 } 244 return 0; 245 } 246 ``` 247 248 [1303F - Number of Components](/contest/1303/problem/F "Educational Codeforces Round 82 (Rated for Div. 2)") 249 250 Idea: [Neon](/profile/Neon "Candidate Master Neon") 251 252 **Tutorial** 253 254 Tutorial is loading... 255 256 **Solution (Ne0n25)** 257 258 ``` 259 #include <bits/stdc++.h> 260 261 using namespace std; 262 263 #define x first 264 #define y second 265 #define pb push_back 266 #define mp make_pair 267 #define sqr(a) ((a) * (a)) 268 #define sz(a) int((a).size()) 269 #define all(a) (a).begin(), (a).end() 270 #define forn(i, n) for (int i = 0; i < int(n); ++i) 271 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 272 #define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i) 273 274 typedef pair<int, int> pt; 275 276 const int M = 310; 277 const int N = 2000 * 1000 + 13; 278 279 int n, m, q; 280 int a[M][M]; 281 282 int dx[] = {-1, 0, 1, 0}; 283 int dy[] = {0, -1, 0, 1}; 284 285 bool in(int x, int y) { 286 return 0 <= x && x < n && 0 <= y && y < m; 287 } 288 289 int p[M * M], rk[M * M]; 290 291 int getp(int v) { 292 return p[v] == v ? v : p[v] = getp(p[v]); 293 } 294 295 bool unite(int a, int b) { 296 a = getp(a); b = getp(b); 297 if (a == b) return false; 298 if (rk[a] < rk[b]) swap(a, b); 299 p[b] = a; 300 rk[a] += rk[b]; 301 return true; 302 } 303 304 int dif[N]; 305 vector<pt> add[N], del[N]; 306 307 void recalc(const vector<pt>& ev, int coeff) { 308 forn(i, n) forn(j, m) a[i][j] = 0; 309 forn(i, n * m) p[i] = i, rk[i] = 1; 310 311 for (auto it : ev) { 312 int cur = 1; 313 int x = it.x / m, y = it.x % m; 314 a[x][y] = 1; 315 316 forn(k, 4) { 317 int nx = x + dx[k]; 318 int ny = y + dy[k]; 319 if (in(nx, ny) && a[nx][ny] == 1) 320 cur -= unite(nx * m + ny, x * m + y); 321 } 322 323 dif[it.y] += cur * coeff; 324 } 325 } 326 327 int main() { 328 scanf("%d%d%d", &n, &m, &q); 329 int clrs = 1; 330 forn(i, q) { 331 int x, y, c; 332 scanf("%d%d%d", &x, &y, &c); 333 --x; --y; 334 if (a[x][y] == c) continue; 335 clrs = c + 1; 336 add[c].pb(mp(x * m + y, i)); 337 del[a[x][y]].pb(mp(x * m + y, i)); 338 a[x][y] = c; 339 } 340 341 forn(x, n) forn(y, m) 342 del[a[x][y]].pb(mp(x * m + y, q)); 343 344 forn(i, clrs) reverse(all(del[i])); 345 346 forn(i, clrs) recalc(add[i], +1); 347 forn(i, clrs) recalc(del[i], -1); 348 349 int cur = 1; 350 forn(i, q) { 351 cur += dif[i]; 352 printf("%d\n", cur); 353 } 354 } 355 ``` 356 357 [1303G - Sum of Prefix Sums](/contest/1303/problem/G "Educational Codeforces Round 82 (Rated for Div. 2)") 358 359 Idea: [Neon](/profile/Neon "Candidate Master Neon") 360 361 **Tutorial** 362 363 Tutorial is loading... 364 365 **Solution (BledDest)** 366 367 ``` 368 #include<bits/stdc++.h> 369 370 using namespace std; 371 372 const int N = 150043; 373 374 typedef pair<long long, long long> func; 375 376 func T[4 * N]; 377 bool usedT[4 * N]; 378 379 void clear(int v, int l, int r) 380 { 381 if(!usedT[v]) return; 382 usedT[v] = false; 383 T[v] = make_pair(0ll, 0ll); 384 if(l < r - 1) 385 { 386 int m = (l + r) / 2; 387 clear(v * 2 + 1, l, m); 388 clear(v * 2 + 2, m, r); 389 } 390 } 391 392 long long eval(func f, int x) 393 { 394 return f.first * x + f.second; 395 } 396 397 long long get(int v, int l, int r, int x) 398 { 399 long long ans = eval(T[v], x); 400 if(l < r - 1) 401 { 402 int m = (l + r) / 2; 403 if(m > x) 404 ans = max(ans, get(v * 2 + 1, l, m, x)); 405 else 406 ans = max(ans, get(v * 2 + 2, m, r, x)); 407 } 408 return ans; 409 } 410 411 void upd(int v, int l, int r, func f) 412 { 413 usedT[v] = true; 414 int m = (l + r) / 2; 415 bool need_swap = eval(f, m) > eval(T[v], m); 416 if(need_swap) 417 swap(T[v], f); 418 if(l == r - 1) 419 return; 420 if(eval(f, l) > eval(T[v], l)) 421 upd(v * 2 + 1, l, m, f); 422 else 423 upd(v * 2 + 2, m, r, f); 424 } 425 426 long long ans = 0; 427 428 void update_ans(vector<vector<func> > heads, vector<vector<func> > tails) 429 { 430 int n = heads.size(); 431 for(int i = 0; i < n; i++) 432 { 433 for(auto x : heads[i]) 434 ans = max(ans, get(0, 0, N, x.first) + x.second); 435 for(auto x : tails[i]) 436 upd(0, 0, N, x); 437 } 438 clear(0, 0, N); 439 } 440 441 int a[N]; 442 vector<int> g[N]; 443 int n; 444 bool used[N]; 445 int siz[N]; 446 447 void dfs1(int x, int p = -1) 448 { 449 if(used[x]) return; 450 siz[x] = 1; 451 for(auto to : g[x]) 452 { 453 if(!used[to] && to != p) 454 { 455 dfs1(to, x); 456 siz[x] += siz[to]; 457 } 458 } 459 } 460 461 pair<int, int> c; 462 int S = 0; 463 464 void find_centroid(int x, int p = -1) 465 { 466 if(used[x]) return; 467 int mx = 0; 468 for(auto to : g[x]) 469 { 470 if(!used[to] && to != p) 471 { 472 find_centroid(to, x); 473 mx = max(mx, siz[to]); 474 } 475 } 476 if(p != -1) 477 mx = max(mx, S - siz[x]); 478 c = min(c, make_pair(mx, x)); 479 } 480 481 void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink) 482 { 483 if(used[v]) 484 return; 485 cnt++; 486 curadd += a[v]; 487 cursum += curadd; 488 sink.push_back(make_pair(cnt, cursum)); 489 for(auto to : g[v]) 490 if(to != p) 491 dfs_heads(to, v, cnt, cursum, curadd, sink); 492 } 493 494 void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink) 495 { 496 if(used[v]) 497 return; 498 cnt++; 499 curadd += a[v]; 500 cursum += a[v] * 1ll * cnt; 501 sink.push_back(make_pair(curadd, cursum)); 502 for(auto to : g[v]) 503 if(to != p) 504 dfs_tails(to, v, cnt, cursum, curadd, sink); 505 } 506 507 void centroid(int v) 508 { 509 if(used[v]) return; 510 dfs1(v); 511 S = siz[v]; 512 c = make_pair(int(1e9), -1); 513 find_centroid(v); 514 int C = c.second; 515 used[C] = 1; 516 vector<vector<func> > heads, tails; 517 for(auto to : g[C]) 518 if(!used[to]) 519 { 520 heads.push_back(vector<func>()); 521 dfs_heads(to, C, 1, a[C], a[C], heads.back()); 522 tails.push_back(vector<func>()); 523 dfs_tails(to, C, 0, 0, 0, tails.back()); 524 } 525 heads.push_back(vector<func>({{1, a[C]}})); 526 tails.push_back(vector<func>({{0, 0}})); 527 update_ans(heads, tails); 528 reverse(heads.begin(), heads.end()); 529 reverse(tails.begin(), tails.end()); 530 update_ans(heads, tails); 531 for(auto to : g[C]) 532 centroid(to); 533 } 534 535 int main() 536 { 537 scanf("%d", &n); 538 for(int i = 0; i < n - 1; i++) 539 { 540 int x, y; 541 scanf("%d %d", &x, &y); 542 --x; 543 --y; 544 g[x].push_back(y); 545 g[y].push_back(x); 546 } 547 for(int i = 0; i < n; i++) 548 scanf("%d", &a[i]); 549 centroid(0); 550 printf("%lld\n", ans); 551 } 552 ```