1795.md (8867B)
1 Source: https://codeforces.com/blog/entry/112963 2 3 [1795A - Two Towers](/contest/1795/problem/A "Educational Codeforces Round 143 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon) 1** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 auto ok = [](string s) { 20 for (int i = 1; i < (int)s.size(); ++i) 21 if (s[i - 1] == s[i]) return false; 22 return true; 23 }; 24 25 int t; 26 cin >> t; 27 while (t--) { 28 int n, m; 29 string s, t; 30 cin >> n >> m >> s >> t; 31 bool f = false; 32 for (int x = 0; x < 2; ++x) { 33 string cs = s, ct = t; 34 for (int i = 0; i < n; ++i) { 35 f |= ok(cs) && ok(ct); 36 ct.push_back(cs.back()); 37 cs.pop_back(); 38 } 39 swap(n, m); 40 swap(s, t); 41 } 42 cout << (f ? "YES\n" : "NO\n"); 43 } 44 } 45 ``` 46 47 **Solution (Neon) 2** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 using namespace std; 53 54 int main() { 55 int t; 56 cin >> t; 57 while (t--) { 58 int n, m; 59 string s, t; 60 cin >> n >> m >> s >> t; 61 reverse(t.begin(), t.end()); 62 s += t; 63 int cnt = 0; 64 for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i]; 65 cout << (cnt <= 1 ? "YES\n" : "NO\n"); 66 } 67 } 68 ``` 69 70 [1795B - Ideal Point](/contest/1795/problem/B "Educational Codeforces Round 143 (Rated for Div. 2)") 71 72 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 73 74 **Tutorial** 75 76 Tutorial is loading... 77 78 **Solution (Neon)** 79 80 ``` 81 #include <bits/stdc++.h> 82 83 using namespace std; 84 85 int main() { 86 int t; 87 cin >> t; 88 while (t--) { 89 int n, k; 90 cin >> n >> k; 91 int L = 0, R = 55; 92 while (n--) { 93 int l, r; 94 cin >> l >> r; 95 if (l <= k && k <= r) 96 L = max(L, l), R = min(R, r); 97 } 98 cout << (L == R ? "YES\n" : "NO\n"); 99 } 100 } 101 ``` 102 103 [1795C - Tea Tasting](/contest/1795/problem/C "Educational Codeforces Round 143 (Rated for Div. 2)") 104 105 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution (Neon)** 112 113 ``` 114 #include <bits/stdc++.h> 115 116 using namespace std; 117 118 using li = long long; 119 120 int main() { 121 ios::sync_with_stdio(false); cin.tie(0); 122 int t; 123 cin >> t; 124 while (t--) { 125 int n; 126 cin >> n; 127 vector<li> a(n), b(n); 128 for (auto& x : a) cin >> x; 129 for (auto& x : b) cin >> x; 130 vector<li> sum(n + 1); 131 for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i]; 132 vector<li> cnt(n + 1), add(n + 1); 133 for (int i = 0; i < n; ++i) { 134 int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1; 135 cnt[i] += 1; 136 cnt[j] -= 1; 137 add[j] += a[i] - sum[j] + sum[i]; 138 } 139 for (int i = 0; i < n; ++i) { 140 cout << cnt[i] * b[i] + add[i] << ' '; 141 cnt[i + 1] += cnt[i]; 142 } 143 cout << '\n'; 144 } 145 } 146 ``` 147 148 [1795D - Triangle Coloring](/contest/1795/problem/D "Educational Codeforces Round 143 (Rated for Div. 2)") 149 150 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution (BledDest)** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 const int MOD = 998244353; 164 165 int add(int x, int y) 166 { 167 return ((x + y) % MOD + MOD) % MOD; 168 } 169 170 int mul(int x, int y) 171 { 172 return x * 1ll * y % MOD; 173 } 174 175 int binpow(int x, int y) 176 { 177 int z = 1; 178 while(y) 179 { 180 if(y % 2 == 1) z = mul(z, x); 181 x = mul(x, x); 182 y /= 2; 183 } 184 return z; 185 } 186 187 int inv(int x) 188 { 189 return binpow(x, MOD - 2); 190 } 191 192 int divide(int x, int y) 193 { 194 return mul(x, inv(y)); 195 } 196 197 int main() 198 { 199 int n; 200 cin >> n; 201 int ans = 1; 202 for(int i = 1; i <= n / 6; i++) 203 ans = mul(ans, divide(i + n / 6, i)); 204 for(int i = 0; i < n / 3; i++) 205 { 206 vector<int> a(3); 207 for(int j = 0; j < 3; j++) 208 cin >> a[j]; 209 int mn = *min_element(a.begin(), a.end()); 210 int cnt_min = count(a.begin(), a.end(), mn); 211 ans = mul(ans, cnt_min); 212 } 213 cout << ans << endl; 214 } 215 ``` 216 217 [1795E - Explosions?](/contest/1795/problem/E "Educational Codeforces Round 143 (Rated for Div. 2)") 218 219 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 220 221 **Tutorial** 222 223 Tutorial is loading... 224 225 **Solution (adedalic)** 226 227 ``` 228 import java.util.* 229 230 fun main() { 231 repeat(readln().toInt()) { 232 val n = readln().toInt() 233 var h = readln().split(' ').map { it.toInt() } 234 235 val d = Array(2) { LongArray(n) { 0 } } 236 for (tp in 0..1) { 237 val s = Stack<Pair<Int, Int>>() 238 239 for (i in h.indices) { 240 while (s.isNotEmpty() && s.peek().first > h[i] - i) 241 s.pop() 242 var j = maxOf(-1, i - h[i]) 243 if (s.isNotEmpty()) 244 j = maxOf(j, s.peek().second) 245 246 val len = (i - j).toLong() 247 d[tp][i] = len * h[i] - len * (len - 1) / 2 248 if (j >= 0 && len < h[i]) 249 d[tp][i] += d[tp][j] 250 251 s.push(Pair(h[i] - i, i)) 252 } 253 h = h.reversed() 254 } 255 d[1] = d[1].reversedArray() 256 257 var ans = 1e18.toLong() 258 val sum = h.fold(0L) { total, it -> total + it } 259 for (i in h.indices) { 260 val cur = sum - d[0][i] - d[1][i] + 2 * h[i] 261 ans = minOf(ans, cur) 262 } 263 println(ans) 264 } 265 } 266 ``` 267 268 [1795F - Blocking Chips](/contest/1795/problem/F "Educational Codeforces Round 143 (Rated for Div. 2)") 269 270 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 271 272 **Tutorial** 273 274 Tutorial is loading... 275 276 **Solution (awoo)** 277 278 ``` 279 #include <bits/stdc++.h> 280 281 using namespace std; 282 283 #define forn(i, n) for(int i = 0; i < int(n); i++) 284 285 vector<vector<int>> g; 286 vector<int> req; 287 vector<char> used; 288 289 vector<int> d; 290 291 bool dfs(int v, int p = -1){ 292 d[v] = 0; 293 for (int u : g[v]) if (u != p){ 294 if (!dfs(u, v)) return false; 295 if (!used[u]) d[v] = max(d[v], d[u] + 1); 296 } 297 if (req[v] == 0 || d[v] >= req[v]) return true; 298 if (p == -1 || used[p]) return false; 299 used[p] = true; 300 req[p] = req[v] - 1; 301 return true; 302 } 303 304 int main(){ 305 int t; 306 scanf("%d", &t); 307 while (t--){ 308 int n; 309 scanf("%d", &n); 310 g.assign(n, {}); 311 d.resize(n); 312 forn(i, n - 1){ 313 int v, u; 314 scanf("%d%d", &v, &u); 315 --v, --u; 316 g[v].push_back(u); 317 g[u].push_back(v); 318 } 319 int k; 320 scanf("%d", &k); 321 vector<int> a(k); 322 forn(i, k){ 323 scanf("%d", &a[i]); 324 --a[i]; 325 } 326 int l = 1, r = n; 327 int res = 0; 328 while (l <= r){ 329 int m = (l + r) / 2; 330 used.assign(n, 0); 331 req.assign(n, 0); 332 forn(i, k){ 333 used[a[i]] = true; 334 req[a[i]] = m / k + (i < m % k); 335 } 336 if (dfs(0)){ 337 res = m; 338 l = m + 1; 339 } 340 else{ 341 r = m - 1; 342 } 343 } 344 printf("%d\n", res); 345 } 346 } 347 ``` 348 349 [1795G - Removal Sequences](/contest/1795/problem/G "Educational Codeforces Round 143 (Rated for Div. 2)") 350 351 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 352 353 **Tutorial** 354 355 Tutorial is loading... 356 357 **Solution (awoo)** 358 359 ``` 360 #include <bits/stdc++.h> 361 362 using namespace std; 363 364 #define forn(i, n) for(int i = 0; i < int(n); i++) 365 366 typedef unsigned long long uli; 367 368 int main(){ 369 int t; 370 scanf("%d", &t); 371 while (t--){ 372 int n, m; 373 scanf("%d%d", &n, &m); 374 vector<int> a(n); 375 forn(i, n) scanf("%d", &a[i]); 376 vector<vector<int>> g(n); 377 forn(i, m){ 378 int v, u; 379 scanf("%d%d", &v, &u); 380 --v, --u; 381 g[v].push_back(u); 382 g[u].push_back(v); 383 } 384 vector<char> rem(n); 385 vector<int> d(n); 386 forn(i, n) d[i] = g[i].size(); 387 queue<int> q; 388 forn(i, n) if (a[i] == d[i]) q.push(i); 389 vector<pair<int, int>> ord; 390 while (!q.empty()){ 391 int v = q.front(); 392 q.pop(); 393 rem[v] = true; 394 for (int u : g[v]) if (!rem[u]){ 395 --d[u]; 396 ord.push_back({v, u}); 397 if (d[u] == a[u]) 398 q.push(u); 399 } 400 } 401 reverse(ord.begin(), ord.end()); 402 vector<uli> mask(n); 403 long long ans = n * 1ll * (n + 1) / 2; 404 for (int l = 0; l < n; l += 64){ 405 int r = min(n, l + 64); 406 for (int i = l; i < r; ++i) 407 mask[i] = 1ull << (i - l); 408 for (const pair<int, int> &it : ord) 409 mask[it.first] |= mask[it.second]; 410 forn(i, n){ 411 ans -= __builtin_popcountll(mask[i]); 412 mask[i] = 0; 413 } 414 } 415 printf("%lld\n", ans); 416 } 417 } 418 ```