1574.md (8125B)
1 Source: https://codeforces.com/blog/entry/95188 2 3 [1574A - Regular Bracket Sequences](/contest/1574/problem/A "Educational Codeforces Round 114 (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 for j in range(n): 18 print("()" * j + "(" * (n - j) + ")" * (n - j)) 19 ``` 20 21 [1574B - Combinatorics Homework](/contest/1574/problem/B "Educational Codeforces Round 114 (Rated for Div. 2)") 22 23 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 24 25 **Tutorial** 26 27 Tutorial is loading... 28 29 **Solution (awoo)** 30 31 ``` 32 for _ in range(int(input())): 33 a, b, c, m = map(int, input().split()) 34 a, b, c = sorted([a, b, c]) 35 print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO") 36 ``` 37 38 [1574C - Slay the Dragon](/contest/1574/problem/C "Educational Codeforces Round 114 (Rated for Div. 2)") 39 40 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution (Neon)** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 using li = long long; 54 55 int main() { 56 ios_base::sync_with_stdio(false); 57 cin.tie(NULL); 58 int n; 59 cin >> n; 60 vector<li> a(n); 61 for (auto &x : a) cin >> x; 62 sort(a.begin(), a.end()); 63 li sum = accumulate(a.begin(), a.end(), 0LL); 64 int m; 65 cin >> m; 66 while (m--) { 67 li x, y; 68 cin >> x >> y; 69 int i = lower_bound(a.begin(), a.end(), x) - a.begin(); 70 li ans = 2e18; 71 if (i > 0) ans = min(ans, (x - a[i - 1]) + max(0LL, y - sum + a[i - 1])); 72 if (i < n) ans = min(ans, max(0LL, y - sum + a[i])); 73 cout << ans << '\n'; 74 } 75 } 76 ``` 77 78 [1574D - The Strongest Build](/contest/1574/problem/D "Educational Codeforces Round 114 (Rated for Div. 2)") 79 80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution (awoo)** 87 88 ``` 89 #include <bits/stdc++.h> 90 91 #define forn(i, n) for (int i = 0; i < int(n); i++) 92 93 using namespace std; 94 95 int n; 96 vector<vector<int>> a; 97 int m; 98 vector<vector<int>> b; 99 100 int main() { 101 scanf("%d", &n); 102 a.resize(n); 103 forn(i, n){ 104 int c; 105 scanf("%d", &c); 106 a[i].resize(c); 107 forn(j, c) scanf("%d", &a[i][j]); 108 } 109 scanf("%d", &m); 110 b.resize(m); 111 forn(i, m){ 112 b[i].resize(n); 113 forn(j, n){ 114 scanf("%d", &b[i][j]); 115 --b[i][j]; 116 } 117 } 118 sort(b.begin(), b.end()); 119 vector<int> ult(n); 120 forn(i, n) ult[i] = int(a[i].size()) - 1; 121 if (!binary_search(b.begin(), b.end(), ult)){ 122 forn(i, n) printf("%d ", ult[i] + 1); 123 puts(""); 124 return 0; 125 } 126 int mx = 0; 127 vector<int> ans(n, -1); 128 forn(i, m){ 129 vector<int> tmp = b[i]; 130 int sum = 0; 131 forn(j, n) sum += a[j][tmp[j]]; 132 forn(j, n) if (tmp[j] != 0){ 133 --tmp[j]; 134 if (!binary_search(b.begin(), b.end(), tmp) && sum - a[j][tmp[j] + 1] + a[j][tmp[j]] > mx){ 135 mx = sum - a[j][tmp[j] + 1] + a[j][tmp[j]]; 136 ans = tmp; 137 } 138 ++tmp[j]; 139 } 140 } 141 forn(i, n){ 142 printf("%d ", ans[i] + 1); 143 } 144 puts(""); 145 } 146 ``` 147 148 [1574E - Coloring](/contest/1574/problem/E "Educational Codeforces Round 114 (Rated for Div. 2)") 149 150 Idea: [Roms](/profile/Roms "Master Roms") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution (Roms)** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 const int MOD = 998244353; 164 const int N = 1'000'009; 165 166 int sum (int a, int b) { 167 int res = a + b; 168 if (res < 0) res += MOD; 169 if (res >= MOD) res -= MOD; 170 return res; 171 } 172 173 int n, m, k; 174 map <pair <int, int>, char> c; 175 int cntr[N][2], cntc[N][2]; 176 int cntx[2]; 177 set <int> badr, badc; 178 set<int> ur, uc; 179 int p2[N]; 180 181 void upd2(int pos, int col, int add, int cnt[N][2], set <int> &bad, set<int> &u) { 182 cnt[pos][col] += add; 183 assert(cnt[pos][col] >= 0); 184 185 if (cnt[pos][0] > 0 && cnt[pos][1] > 0){ 186 if (!bad.count(pos)) 187 bad.insert(pos); 188 } else { 189 if (bad.count(pos)) 190 bad.erase(pos); 191 } 192 193 if (cnt[pos][0] > 0 || cnt[pos][1] > 0){ 194 if (!u.count(pos)) 195 u.insert(pos); 196 } else { 197 if (u.count(pos)) 198 u.erase(pos); 199 } 200 } 201 202 void upd(int x, int y, int t) { 203 int col = (x & 1) ^ (y & 1); 204 if (c.count({x, y})) { 205 int ncol = col ^ c[{x, y}]; 206 --cntx[ncol]; 207 upd2(x, ncol, -1, cntr, badr, ur); 208 upd2(y, ncol, -1, cntc, badc, uc); 209 c.erase({x, y}); 210 } 211 212 if (t == -1) 213 return; 214 215 int ncol = col ^ t; 216 ++cntx[ncol]; 217 upd2(x, ncol, 1, cntr, badr, ur); 218 upd2(y, ncol, 1, cntc, badc, uc); 219 c[{x, y}] = t; 220 } 221 222 int main(){ 223 p2[0] = 1; 224 for (int i = 1; i < N; ++i) 225 p2[i] = sum(p2[i - 1], p2[i - 1]); 226 227 scanf("%d%d%d", &n, &m, &k); 228 for (int i = 0; i < k; ++i) { 229 int x, y, t; 230 scanf("%d %d %d", &x, &y, &t); 231 --x, --y; 232 upd(x, y, t); 233 234 int res = 0; 235 if(badr.size() > 0 && badc.size() > 0) { 236 res = 0; 237 } else if (badr.size() > 0) { 238 assert(m - uc.size() >= 0); 239 res = p2[m - uc.size()]; 240 } else if (badc.size() > 0) { 241 assert(n - ur.size() >= 0); 242 res = p2[n - ur.size()]; 243 } else { 244 if (ur.size() == 0 && uc.size() == 0) 245 res = sum(sum(p2[n], p2[m]), -2); 246 else { 247 assert(m - uc.size() >= 0); 248 res = sum(res, p2[m - uc.size()]); 249 assert(n - ur.size() >= 0); 250 res = sum(res, p2[n - ur.size()]); 251 if (cntx[0] == 0 || cntx[1] == 0) { 252 assert(cntx[0] != 0 || cntx[1] != 0); 253 res = sum(res, -1); 254 } 255 } 256 } 257 258 printf("%d\n", res); 259 } 260 return 0; 261 } 262 ``` 263 264 [1574F - Occurrences](/contest/1574/problem/F "Educational Codeforces Round 114 (Rated for Div. 2)") 265 266 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution (BledDest)** 273 274 ``` 275 #include <bits/stdc++.h> 276 277 using namespace std; 278 279 const int MOD = 998244353; 280 281 int add(int x, int y) 282 { 283 x += y; 284 while(x >= MOD) x -= MOD; 285 while(x < 0) x += MOD; 286 return x; 287 } 288 289 int mul(int x, int y) 290 { 291 return (x * 1ll * y) % MOD; 292 } 293 294 int main() 295 { 296 int n, m, k; 297 scanf("%d %d %d", &n, &m, &k); 298 vector<vector<int>> A(n); 299 vector<int> bad_num(k); 300 for(int i = 0; i < n; i++) 301 { 302 int c; 303 scanf("%d", &c); 304 A[i].resize(c); 305 for(int j = 0; j < c; j++) 306 { 307 scanf("%d", &A[i][j]); 308 A[i][j]--; 309 } 310 } 311 312 for(int i = 0; i < n; i++) 313 { 314 if(set<int>(A[i].begin(), A[i].end()).size() != A[i].size()) 315 { 316 for(auto x : A[i]) 317 bad_num[x] = 1; 318 } 319 } 320 vector<vector<int>> nxt(k); 321 vector<vector<int>> prv(k); 322 for(int i = 0; i < n; i++) 323 for(int j = 0; j + 1 < A[i].size(); j++) 324 { 325 nxt[A[i][j]].push_back(A[i][j + 1]); 326 prv[A[i][j + 1]].push_back(A[i][j]); 327 } 328 329 for(int i = 0; i < k; i++) 330 { 331 sort(nxt[i].begin(), nxt[i].end()); 332 sort(prv[i].begin(), prv[i].end()); 333 nxt[i].erase(unique(nxt[i].begin(), nxt[i].end()), nxt[i].end()); 334 prv[i].erase(unique(prv[i].begin(), prv[i].end()), prv[i].end()); 335 } 336 337 vector<int> used(k, 0); 338 vector<int> cnt(k + 1, 0); 339 for(int i = 0; i < k; i++) 340 { 341 if(used[i]) continue; 342 queue<int> q; 343 vector<int> comp; 344 q.push(i); 345 used[i] = 1; 346 while(!q.empty()) 347 { 348 int z = q.front(); 349 q.pop(); 350 comp.push_back(z); 351 for(auto x : nxt[z]) 352 if(!used[x]) 353 { 354 used[x] = 1; 355 q.push(x); 356 } 357 for(auto x : prv[z]) 358 if(!used[x]) 359 { 360 used[x] = 1; 361 q.push(x); 362 } 363 } 364 bool bad = false; 365 int cnt_beg = 0; 366 for(auto x : comp) 367 { 368 if(prv[x].empty()) 369 cnt_beg++; 370 if(prv[x].size() > 1 || nxt[x].size() > 1 || bad_num[x]) 371 bad = true; 372 } 373 bad |= (cnt_beg == 0); 374 if(!bad) 375 cnt[comp.size()]++; 376 } 377 vector<int> nonzero; 378 for(int i = 1; i <= k; i++) 379 if(cnt[i] > 0) 380 nonzero.push_back(i); 381 vector<int> dp(m + 1, 0); 382 dp[0] = 1; 383 for(int i = 1; i <= m; i++) 384 for(auto x : nonzero) 385 if(x <= i) 386 dp[i] = add(dp[i], mul(cnt[x], dp[i - x])); 387 388 printf("%d\n", dp[m]); 389 return 0; 390 } 391 ```