2069.md (8740B)
1 Source: https://codeforces.com/blog/entry/139774 2 3 [2069A - Was there an Array?](/contest/2069/problem/A "Educational Codeforces Round 174 (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 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 s = list(input().split()) 18 s = "".join(s) 19 if "101" in s: 20 print('NO') 21 else: 22 print('YES') 23 ``` 24 25 [2069B - Set of Strangers](/contest/2069/problem/B "Educational Codeforces Round 174 (Rated for Div. 2)") 26 27 Idea: [adedalic](/profile/adedalic "International Master adedalic") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution (adedalic)** 34 35 ``` 36 for _ in range(int(input())): 37 n, m = map(int, input().split()) 38 a = [list(map(int, input().split())) for i in range(n)] 39 hasColor = [0] * (n * m) 40 hasBad = [0] * (n * m) 41 for i in range(n): 42 for j in range(m): 43 hasColor[a[i][j] - 1] = 1 44 if i + 1 < n and a[i][j] == a[i + 1][j]: 45 hasBad[a[i][j] - 1] = 1 46 if j + 1 < m and a[i][j] == a[i][j + 1]: 47 hasBad[a[i][j] - 1] = 1 48 print(sum(hasColor) + sum(hasBad) - 1 - max(hasBad)) 49 ``` 50 51 [2069C - Beautiful Sequence](/contest/2069/problem/C "Educational Codeforces Round 174 (Rated for Div. 2)") 52 53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (Neon)** 60 61 ``` 62 #include <bits/stdc++.h> 63 64 using namespace std; 65 66 const int MOD = 998244353; 67 68 int add(int x, int y) { 69 x += y; 70 if (x >= MOD) x -= MOD; 71 return x; 72 } 73 74 int main() { 75 int t; 76 cin >> t; 77 while (t--) { 78 int n; 79 cin >> n; 80 vector<int> dp(4, 0); 81 dp[0] = 1; 82 while (n--) { 83 int x; 84 cin >> x; 85 if (x == 2) dp[x] = add(dp[x], dp[x]); 86 dp[x] = add(dp[x], dp[x - 1]); 87 } 88 cout << dp[3] << '\n'; 89 } 90 } 91 ``` 92 93 [2069D - Palindrome Shuffle](/contest/2069/problem/D "Educational Codeforces Round 174 (Rated for Div. 2)") 94 95 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution (Neon)** 102 103 ``` 104 #include <bits/stdc++.h> 105 106 using namespace std; 107 108 int main() { 109 int t; 110 cin >> t; 111 while (t--) { 112 string s; 113 cin >> s; 114 int n = s.size(); 115 int i = 0; 116 while (i < n / 2 && s[i] == s[n - i - 1]) ++i; 117 n -= 2 * i; 118 s = s.substr(i, n); 119 int ans = n; 120 for (int z = 0; z < 2; ++z) { 121 int l = 0, r = n; 122 while (l <= r) { 123 int m = (l + r) / 2; 124 vector<int> cnt(26); 125 for (int i = 0; i < m; ++i) 126 cnt[s[i] - 'a']++; 127 bool ok = true; 128 for (int i = 0; i < min(n / 2, n - m); ++i) { 129 char c = s[n - i - 1]; 130 if (i < m) { 131 ok &= cnt[c - 'a'] > 0; 132 cnt[c - 'a']--; 133 } else { 134 ok &= (c == s[i]); 135 } 136 } 137 for (auto x : cnt) 138 ok &= (x % 2 == 0); 139 if (ok) { 140 r = m - 1; 141 } else { 142 l = m + 1; 143 } 144 } 145 ans = min(ans, r + 1); 146 reverse(s.begin(), s.end()); 147 } 148 cout << ans << '\n'; 149 } 150 } 151 ``` 152 153 [2069E - A, B, AB and BA](/contest/2069/problem/E "Educational Codeforces Round 174 (Rated for Div. 2)") 154 155 Idea: [adedalic](/profile/adedalic "International Master adedalic") 156 157 **Tutorial** 158 159 Tutorial is loading... 160 161 **Solution (adedalic)** 162 163 ``` 164 #include<bits/stdc++.h> 165 166 using namespace std; 167 168 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 169 #define sz(a) int((a).size()) 170 171 typedef long long li; 172 173 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 174 return out << "(" << p.x << ", " << p.y << ")"; 175 } 176 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 177 fore(i, 0, sz(v)) { 178 if(i) out << " "; 179 out << v[i]; 180 } 181 return out; 182 } 183 184 const int INF = int(1e9); 185 const li INF64 = li(1e18); 186 187 string s; 188 int a, b, ab, ba; 189 190 inline bool read() { 191 if(!(cin >> s)) 192 return false; 193 cin >> a >> b >> ab >> ba; 194 return true; 195 } 196 197 int process(vector<int> &rem, int &tot) { 198 int placed = 0; 199 sort(rem.begin(), rem.end(), greater<int>()); 200 while (!rem.empty() && tot > 0) { 201 int cnt = min(rem.back() / 2, tot); 202 placed += cnt; 203 tot -= cnt; 204 rem.back() -= 2 * cnt; 205 if (rem.back() == 0) 206 rem.pop_back(); 207 } 208 return placed; 209 } 210 211 int remnants(vector<int> &rem, int &tot) { 212 int placed = 0; 213 for (int &cur : rem) { 214 int cnt = min(tot, (cur - 2) / 2); 215 placed += cnt; 216 tot -= cnt; 217 cur -= 2 * cnt + 2; 218 } 219 return placed; 220 } 221 222 inline void solve() { 223 s.push_back(s.back()); 224 int eq = 0, placedPairs = 0; 225 vector<int> remAB, remBA; 226 227 int lst = 0; 228 // cerr << "s = " << s << endl; 229 fore (i, 1, sz(s)) { 230 if (s[i] != s[i - 1]) 231 continue; 232 233 if (s[lst] == s[i - 1]) { 234 // ABA..A or BAB..B 235 eq += (i - lst) / 2; 236 } 237 else { 238 int len = i - lst; 239 if (s[lst] == 'A') { 240 // ABA..B 241 remAB.push_back(len); 242 } 243 else { 244 // BAB..A 245 remBA.push_back(len); 246 } 247 } 248 // cerr << lst << ", " << i << endl; 249 lst = i; 250 } 251 s.pop_back(); 252 253 placedPairs += process(remAB, ab); 254 assert(remAB.empty() || ab == 0); 255 256 placedPairs += process(remBA, ba); 257 assert(remBA.empty() || ba == 0); 258 259 placedPairs += remnants(remAB, ba); 260 placedPairs += remnants(remBA, ab); 261 262 int remPlaced = min(eq, ab + ba); 263 placedPairs += remPlaced; 264 265 int needA = count(s.begin(), s.end(), 'A') - placedPairs; 266 int needB = count(s.begin(), s.end(), 'B') - placedPairs; 267 268 if (needA <= a && needB <= b) 269 cout << "YES\n"; 270 else 271 cout << "NO\n"; 272 } 273 274 int main() { 275 #ifdef _DEBUG 276 freopen("input.txt", "r", stdin); 277 int tt = clock(); 278 #endif 279 ios_base::sync_with_stdio(false); 280 cin.tie(0), cout.tie(0); 281 cout << fixed << setprecision(15); 282 283 int t; cin >> t; 284 while (t--) { 285 read(); 286 solve(); 287 288 #ifdef _DEBUG 289 cerr << "TIME = " << clock() - tt << endl; 290 tt = clock(); 291 #endif 292 } 293 return 0; 294 } 295 ``` 296 297 [2069F - Graph Inclusion](/contest/2069/problem/F "Educational Codeforces Round 174 (Rated for Div. 2)") 298 299 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 300 301 **Tutorial** 302 303 Tutorial is loading... 304 305 **Solution (BledDest)** 306 307 ``` 308 #include<bits/stdc++.h> 309 310 using namespace std; 311 312 const int N = 400043; 313 const int BUF = N * 20; 314 315 int* where[BUF]; 316 int val[BUF]; 317 int cur = 0; 318 319 void change(int& x, int y) 320 { 321 val[cur] = x; 322 where[cur] = &x; 323 x = y; 324 cur++; 325 } 326 327 void rollback() 328 { 329 cur--; 330 (*where[cur]) = val[cur]; 331 } 332 333 struct DSU 334 { 335 vector<int> p, s; 336 int n; 337 int comps; 338 339 int get(int x) 340 { 341 if(p[x] == x) return x; 342 return get(p[x]); 343 } 344 345 void merge(int x, int y) 346 { 347 x = get(x); 348 y = get(y); 349 if(x == y) return; 350 change(comps, comps - 1); 351 if(s[x] < s[y]) swap(x, y); 352 change(p[y], x); 353 change(s[x], s[x] + s[y]); 354 } 355 356 DSU(int n = 0) 357 { 358 this->n = n; 359 s = vector<int>(n, 1); 360 p = vector<int>(n); 361 iota(p.begin(), p.end(), 0); 362 comps = n; 363 } 364 }; 365 366 struct edge 367 { 368 char g; 369 int x; 370 int y; 371 edge(char g = 'A', int x = 0, int y = 0) : g(g), x(x), y(y) {}; 372 }; 373 374 DSU A, united; 375 vector<edge> T[4 * N]; 376 int ans[N]; 377 378 void dfs(int v, int l, int r) 379 { 380 int state = cur; 381 for(auto e : T[v]) 382 { 383 united.merge(e.x, e.y); 384 if(e.g == 'A') A.merge(e.x, e.y); 385 } 386 if(l == r - 1) 387 { 388 ans[l] = A.comps - united.comps; 389 } 390 else 391 { 392 int m = (l + r) / 2; 393 dfs(v * 2 + 1, l, m); 394 dfs(v * 2 + 2, m, r); 395 } 396 while(state != cur) rollback(); 397 } 398 399 void add_edge(int v, int l, int r, int L, int R, edge e) 400 { 401 if(L >= R) return; 402 if(L == l && R == r) T[v].push_back(e); 403 else 404 { 405 int m = (l + r) / 2; 406 add_edge(v * 2 + 1, l, m, L, min(m, R), e); 407 add_edge(v * 2 + 2, m, r, max(L, m), R, e); 408 } 409 } 410 411 map<pair<int, int>, int> last[2]; 412 413 int main() 414 { 415 ios_base::sync_with_stdio(0); 416 cin.tie(0); 417 int n, q; 418 cin >> n >> q; 419 A = DSU(n); 420 united = DSU(n); 421 for(int i = 0; i < q; i++) 422 { 423 string s; 424 int x, y; 425 cin >> s >> x >> y; 426 --x; 427 --y; 428 int idx = (s[0] == 'A' ? 0 : 1); 429 if(x > y) swap(x, y); 430 if(last[idx].count(make_pair(x, y)) == 0) 431 { 432 last[idx][make_pair(x, y)] = i; 433 } 434 else 435 { 436 add_edge(0, 0, q, last[idx][make_pair(x, y)], i, edge(s[0], x, y)); 437 last[idx].erase(make_pair(x, y)); 438 } 439 } 440 for(int i = 0; i < 2; i++) 441 for(auto a : last[i]) 442 add_edge(0, 0, q, a.second, q, edge(char(i + 'A'), a.first.first, a.first.second)); 443 dfs(0, 0, q); 444 for(int i = 0; i < q; i++) 445 cout << ans[i] << "\n"; 446 } 447 ```