1569.md (10261B)
1 Source: https://codeforces.com/blog/entry/94721 2 3 [1569A - Balanced Substring](/contest/1569/problem/A "Educational Codeforces Round 113 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 s = input() 17 for i in range(n - 1): 18 if s[i] != s[i + 1]: 19 print(i + 1, i + 2) 20 break 21 else: 22 print(-1, -1) 23 ``` 24 25 [1569B - Chess Tournament](/contest/1569/problem/B "Educational Codeforces Round 113 (Rated for Div. 2)") 26 27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution (Neon)** 34 35 ``` 36 #include <bits/stdc++.h> 37 38 using namespace std; 39 40 int main() { 41 ios_base::sync_with_stdio(false); 42 cin.tie(NULL); 43 int t; 44 cin >> t; 45 while (t--) { 46 int n; 47 string s; 48 cin >> n >> s; 49 vector<int> id; 50 for (int i = 0; i < n; ++i) if (s[i] == '2') 51 id.push_back(i); 52 int k = id.size(); 53 if (k == 1 || k == 2) { 54 cout << "NO\n"; 55 continue; 56 } 57 vector<string> t(n, string(n, '=')); 58 for (int i = 0; i < n; ++i) t[i][i] = 'X'; 59 for (int i = 0; i < k; ++i) { 60 int x = id[i], y = id[(i + 1) % k]; 61 t[x][y] = '+'; 62 t[y][x] = '-'; 63 } 64 cout << "YES\n"; 65 for (int i = 0; i < n; ++i) cout << t[i] << '\n'; 66 } 67 } 68 ``` 69 70 [1569C - Jury Meeting](/contest/1569/problem/C "Educational Codeforces Round 113 (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 const int MOD = 998244353; 86 87 int main() { 88 ios_base::sync_with_stdio(false); 89 cin.tie(NULL); 90 int t; 91 cin >> t; 92 while (t--) { 93 int n; 94 cin >> n; 95 vector<int> a(n); 96 for (int &x : a) cin >> x; 97 int mx = *max_element(a.begin(), a.end()); 98 int cmx = count(a.begin(), a.end(), mx); 99 int k = count(a.begin(), a.end(), mx - 1); 100 int ans = 1, sub = 1; 101 for (long long i = 1; i <= n; ++i) { 102 ans = ans * i % MOD; 103 if (i != k + 1) sub = sub * i % MOD; 104 } 105 if (cmx == 1) ans = (ans - sub + MOD) % MOD; 106 cout << ans << '\n'; 107 } 108 } 109 ``` 110 111 [1569D - Inconvenient Pairs](/contest/1569/problem/D "Educational Codeforces Round 113 (Rated for Div. 2)") 112 113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution (adedalic)** 120 121 ``` 122 #include<bits/stdc++.h> 123 124 using namespace std; 125 126 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 127 #define sz(a) int((a).size()) 128 #define all(a) (a).begin(), (a).end() 129 130 #define x first 131 #define y second 132 133 typedef long long li; 134 typedef pair<int, int> pt; 135 136 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 137 return out << "(" << p.x << ", " << p.y << ")"; 138 } 139 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 140 fore(i, 0, sz(v)) { 141 if(i) out << " "; 142 out << v[i]; 143 } 144 return out; 145 } 146 147 const int INF = int(1e9); 148 const li INF64 = li(1e18); 149 150 int n, m, k; 151 vector<int> x, y; 152 vector<pt> ps; 153 154 inline bool read() { 155 if(!(cin >> n >> m >> k)) 156 return false; 157 x.resize(n); 158 fore (i, 0, n) 159 cin >> x[i]; 160 y.resize(m); 161 fore (i, 0, m) 162 cin >> y[i]; 163 ps.resize(k); 164 fore (i, 0, k) 165 cin >> ps[i].x >> ps[i].y; 166 167 return true; 168 } 169 170 inline void solve() { 171 li ans = 0; 172 173 fore (_i, 0, 2) { 174 vector<int> cntY(m, 0); 175 sort(all(ps)); 176 177 vector<pt> bord(k); 178 179 int u = 0; 180 while (u < k) { 181 int v = u; 182 while (v < k && ps[v].x == ps[u].x) 183 v++; 184 185 fore (i, u, v) { 186 int r = int(lower_bound(all(y), ps[i].y) - y.begin()); 187 int l = r; 188 if (y[l] > ps[i].y) 189 l--; 190 assert(y[l] <= ps[i].y && ps[i].y <= y[r]); 191 192 bord[i] = {l, r}; 193 } 194 195 fore (i, u, v) if (bord[i].x < bord[i].y) 196 ans += cntY[bord[i].x]; 197 198 fore (i, u, v) if (bord[i].x < bord[i].y) 199 cntY[bord[i].x]++; 200 201 u = v; 202 } 203 204 205 fore (i, 0, k) 206 swap(ps[i].x, ps[i].y); 207 swap(x, y); 208 swap(n, m); 209 } 210 211 cout << ans << endl; 212 } 213 214 int main() { 215 #ifdef _DEBUG 216 freopen("input.txt", "r", stdin); 217 int tt = clock(); 218 #endif 219 ios_base::sync_with_stdio(false); 220 cin.tie(0), cout.tie(0); 221 cout << fixed << setprecision(15); 222 223 int t; cin >> t; 224 while (t--) { 225 read(); 226 solve(); 227 228 #ifdef _DEBUG 229 cerr << "TIME = " << clock() - tt << endl; 230 tt = clock(); 231 #endif 232 } 233 return 0; 234 } 235 ``` 236 237 [1569E - Playoff Restoration](/contest/1569/problem/E "Educational Codeforces Round 113 (Rated for Div. 2)") 238 239 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 240 241 **Tutorial** 242 243 Tutorial is loading... 244 245 **Solution (BledDest)** 246 247 ``` 248 #include <bits/stdc++.h> 249 250 using namespace std; 251 252 const int MOD = 998244353; 253 254 int add(int x, int y) 255 { 256 x += y; 257 while(x >= MOD) x -= MOD; 258 while(x < 0) x += MOD; 259 return x; 260 } 261 262 int mul(int x, int y) 263 { 264 return (x * 1ll * y) % MOD; 265 } 266 267 int binpow(int x, int y) 268 { 269 int z = 1; 270 while(y) 271 { 272 if(y & 1) z = mul(z, x); 273 x = mul(x, x); 274 y >>= 1; 275 } 276 return z; 277 } 278 279 vector<int> evaluate(int n, int choice_mask) 280 { 281 int cur_place = n / 2 + 1; 282 int cur_bit = n - 2; 283 vector<int> p(n); 284 vector<int> c(n); 285 for(int i = 0; i < n; i++) 286 c[i] = i; 287 while(c.size() != 1) 288 { 289 vector<int> nc; 290 for(int i = 0; i < c.size(); i += 2) 291 { 292 if(choice_mask & (1 << cur_bit)) 293 { 294 p[c[i]] = cur_place; 295 nc.push_back(c[i + 1]); 296 } 297 else 298 { 299 p[c[i + 1]] = cur_place; 300 nc.push_back(c[i]); 301 } 302 cur_bit--; 303 } 304 c = nc; 305 cur_place /= 2; 306 cur_place++; 307 } 308 p[c[0]] = 1; 309 return p; 310 } 311 312 vector<int> adjust(int n, vector<int> p, bool winning) 313 { 314 for(int i = 0; i < n; i++) 315 { 316 if(p[i] == 1) 317 { 318 if(!winning) p[i]++; 319 } 320 else 321 p[i] = p[i] * 2 - 1; 322 } 323 return p; 324 } 325 326 int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0) 327 { 328 if(partial) 329 p = adjust(n, p, winning); 330 int res = 0; 331 for(int i = 0; i < n; i++) 332 res = add(res, mul(add(i + 1, shift), binpow(A, p[i]))); 333 return res; 334 } 335 336 int main() 337 { 338 int k, A, h; 339 cin >> k >> A >> h; 340 if(k <= 4) 341 { 342 for(int i = 0; i < (1 << ((1 << k) - 1)); i++) 343 { 344 vector<int> p = evaluate(1 << k, i); 345 if(get_hash(1 << k, p, A) == h) 346 { 347 for(auto x : p) cout << x << " "; 348 cout << endl; 349 return 0; 350 } 351 } 352 } 353 else 354 { 355 int mask_left = -1; 356 int mask_right = -1; 357 bool left_win = false; 358 for(int c = 0; c < 2; c++) 359 { 360 map<int, int> left_map; 361 for(int i = 0; i < (1 << 16); i++) 362 { 363 vector<int> p = evaluate(16, i); 364 int left_hash = get_hash(16, p, A, true, c == 0, 0); 365 left_map[left_hash] = i; 366 } 367 for(int i = 0; i < (1 << 16); i++) 368 { 369 vector<int> p = evaluate(16, i); 370 int right_hash = get_hash(16, p, A, true, c == 1, 16); 371 int left_hash = add(h, MOD - right_hash); 372 if(left_map.count(left_hash)) 373 { 374 mask_left = left_map[left_hash]; 375 mask_right = i; 376 left_win = (c == 0); 377 } 378 } 379 } 380 if(mask_left != -1) 381 { 382 vector<int> ans_left = evaluate(16, mask_left); 383 vector<int> ans_right = evaluate(16, mask_right); 384 ans_left = adjust(16, ans_left, left_win); 385 ans_right = adjust(16, ans_right, !left_win); 386 for(auto x : ans_left) 387 cout << x << " "; 388 for(auto x : ans_right) 389 cout << x << " "; 390 return 0; 391 } 392 } 393 cout << -1 << endl; 394 return 0; 395 } 396 ``` 397 398 [1569F - Palindromic Hamiltonian Path](/contest/1569/problem/F "Educational Codeforces Round 113 (Rated for Div. 2)") 399 400 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 401 402 **Tutorial** 403 404 Tutorial is loading... 405 406 **Solution (awoo)** 407 408 ``` 409 #include <bits/stdc++.h> 410 411 #define forn(i, n) for (int i = 0; i < int(n); i++) 412 413 using namespace std; 414 415 vector<vector<char>> g; 416 map<long long, bool> dp; 417 418 void brute(int n, vector<int> &p){ 419 int x = find(p.begin(), p.end(), -1) - p.begin(); 420 if (x == int(p.size())){ 421 vector<vector<char>> dp2(1 << n, vector<char>(n)); 422 vector<int> pos1(n), pos2(n); 423 forn(i, p.size()){ 424 pos1[p[i]] = pos2[p[i]]; 425 pos2[p[i]] = i; 426 } 427 forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true; 428 forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){ 429 forn(j, n) if (!((mask >> j) & 1)){ 430 dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]); 431 dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]); 432 } 433 } 434 forn(i, n) if (dp2[(1 << n) - 1][i]){ 435 long long num = 0; 436 for (int x : p) num = num * 6 + x; 437 dp[num] = true; 438 break; 439 } 440 return; 441 } 442 for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){ 443 p[x] = p[y] = n; 444 brute(n + 1, p); 445 p[x] = p[y] = -1; 446 } 447 } 448 449 bool dfs(vector<int> p){ 450 vector<int> used(int(p.size()), -1); 451 int cnt = 0; 452 forn(i, p.size()) if (used[p[i]] == -1) 453 used[p[i]] = cnt++; 454 long long num = 0; 455 for (int& x : p){ 456 x = used[x]; 457 num = num * 6 + x; 458 } 459 if (dp.count(num)) return dp[num]; 460 bool res = false; 461 vector<int> cur(cnt); 462 forn(i, p.size()) ++cur[p[i]]; 463 forn(i, p.size()) if (cur[p[i]] > 2){ 464 int x = p[i]; 465 for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){ 466 p[i] = p[j] = cnt; 467 if (dfs(p)){ 468 res = true; 469 break; 470 } 471 p[i] = p[j] = x; 472 } 473 break; 474 } 475 return dp[num] = res; 476 } 477 478 void brute2(int n, vector<int> &p){ 479 int x = find(p.begin(), p.end(), -1) - p.begin(); 480 if (x == int(p.size())){ 481 dfs(p); 482 return; 483 } 484 forn(i, n + 1){ 485 for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){ 486 p[x] = p[y] = i; 487 brute2(max(n, i + 1), p); 488 p[x] = p[y] = -1; 489 } 490 } 491 } 492 493 int main() { 494 int n, m, k; 495 scanf("%d%d%d", &n, &m, &k); 496 g.resize(n, vector<char>(n)); 497 forn(_, m){ 498 int v, u; 499 scanf("%d%d", &v, &u); 500 --v, --u; 501 g[v][u] = g[u][v] = 1; 502 } 503 vector<int> cur(n, -1); 504 brute(0, cur); 505 brute2(0, cur); 506 vector<long long> fact(k + 1); 507 fact[0] = 1; 508 for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i; 509 long long ans = 0; 510 for (auto it : dp) if (it.second){ 511 long long num = it.first; 512 long long mx = 1; 513 while (num){ 514 mx = max(mx, num % 6 + 1); 515 num /= 6; 516 } 517 if (mx <= k){ 518 ans += fact[k] / fact[k - mx]; 519 } 520 } 521 printf("%lld\n", ans); 522 return 0; 523 } 524 ```