1818.md (17613B)
1 Source: https://codeforces.com/blog/entry/115586 2 3 [1818A - Политика](/contest/1818/problem/A "Codeforces Round 869 (Div. 2)") 4 5 Problem idea: [adamant](/profile/adamant "Мастер adamant") 6 Preparation: [adamant](/profile/adamant "Мастер adamant") 7 8 **Editorial** 9 10 Tutorial is loading... 11 12 **Solution** 13 14 ``` 15 void solve() { 16 int n, k; 17 cin >> n >> k; 18 string t[n]; 19 int ans = n; 20 for(int i = 0; i < n; i++) { 21 cin >> t[i]; 22 if(t[i] != t[0]) { 23 ans--; 24 } 25 } 26 cout << ans << "\n"; 27 } 28 ``` 29 30 [1818B - Неделимые отрезки](/contest/1818/problem/B "Codeforces Round 869 (Div. 2)") 31 32 Problem idea: [adamant](/profile/adamant "Мастер adamant") 33 Preparation: [adamant](/profile/adamant "Мастер adamant") 34 35 **Editorial** 36 37 Tutorial is loading... 38 39 **Solution** 40 41 ``` 42 void solve() { 43 int n; 44 cin >> n; 45 if(n == 1) { 46 cout << 1 << "\n"; 47 } else if(n % 2) { 48 cout << -1 << "\n"; 49 } else { 50 int a[n]; 51 iota(a, a + n, 1); 52 for(int i = 0; i < n; i += 2) { 53 swap(a[i], a[i + 1]); 54 } 55 for(auto it: a) { 56 cout << it << ' '; 57 } 58 cout << "\n"; 59 } 60 } 61 ``` 62 63 [1817A - Почти возрастающая подпоследовательность](/contest/1817/problem/A "Codeforces Round 869 (Div. 1)") 64 65 Problem idea: [dario2994](/profile/dario2994 "Международный гроссмейстер dario2994") 66 Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb") 67 68 **Editorial** 69 70 Tutorial is loading... 71 72 **Solution** 73 74 ``` 75 #include "bits/stdc++.h" 76 using namespace std; 77 typedef vector<int> vi; 78 79 int main() { 80 ios_base::sync_with_stdio(false); 81 cin.tie(NULL); 82 int n,q; cin >> n >> q; 83 vi a(n); 84 for(int& i : a) cin >> i; 85 vi p(n-1); 86 for(int i=1;i<n-1;++i) { 87 int downhill = a[i-1]>=a[i] and a[i]>=a[i+1]; 88 p[i] = p[i-1] + downhill; 89 } 90 while(q--) { 91 int l,r; cin >> l >> r; 92 --l,--r; 93 if(l==r) { 94 cout << "1\n"; 95 } else { 96 int ans = (r-l+1) - p[r-1] + p[l]; 97 cout << ans << '\n'; 98 } 99 } 100 } 101 ``` 102 103 [1817B - Граф-рыба](/contest/1817/problem/B "Codeforces Round 869 (Div. 1)") 104 105 Problem idea: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb") 106 Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb") 107 108 **Hint 1** 109 110 Can you find a necessary condition for whether a Fish Subgraph exists? 111 112 **Hint 2** 113 114 For the Fish Subgraph to exist, the graph must have a cycle with one node in the cycle having degree at least 4. 115 116 **Hint 3** 117 118 When the necessary condition is satisfied, actually, you can always find a Fish Subgraph. Try to prove this, and see if your proof can be turned into an algorithm. 119 120 **Editorial** 121 122 Tutorial is loading... 123 124 **Solution** 125 126 ``` 127 #include "bits/stdc++.h" 128 using namespace std; 129 #define all(x) begin(x),end(x) 130 typedef vector<int> vi; 131 typedef vector<vi> vvi; 132 typedef pair<int,int> pi; 133 134 void solve() { 135 int n,m; cin >> n >> m; 136 vvi adj(n); 137 while(m--) { 138 int u,v; cin >> u >> v; 139 --u,--v; 140 adj[u].push_back(v); 141 adj[v].push_back(u); 142 } 143 // find cycle and node with big degree. 144 for(int u=0;u<n;++u) if(adj[u].size()>=4) for(int v : adj[u]) { 145 // find path from u to v, without edge (u,v) 146 vi cur; 147 vi p; 148 vector<bool> vis(n); 149 auto dfs = [&](auto&& self, int at) -> void { 150 vis[at]=1; 151 cur.push_back(at); 152 if(at==v) { 153 p=cur; 154 return; 155 } 156 for(int to : adj[at]) if(!vis[to]) { 157 if(at==u and to==v) continue; 158 self(self,to); 159 if(!p.empty()) return; 160 } 161 cur.pop_back(); 162 }; 163 dfs(dfs,u); 164 if(p.empty()) continue; 165 // found cycle, with a node with degree >=4 166 vi extra = adj[u]; 167 extra.resize(4); 168 int mn = p.size(); 169 for(auto i : extra) { 170 auto it = find(all(p),i); 171 if(it!=p.begin()+1) { 172 mn = min(mn,int(it-p.begin())+1); 173 } 174 } 175 p.resize(mn); 176 partition(all(extra),[&](int i) {return count(all(p),i)==0;}); 177 extra.resize(2); 178 179 cout << "YES\n"; 180 cout << p.size()+2 << '\n'; 181 auto out = [&](int a, int b) {cout << a+1 << ' ' << b+1 << '\n';}; 182 int prv=p.back(); 183 for(auto i : p) { 184 out(i,prv); 185 prv=i; 186 } 187 out(u,extra[0]); 188 out(u,extra[1]); 189 return; 190 } 191 192 cout << "NO\n"; 193 } 194 195 int main() { 196 ios_base::sync_with_stdio(false); 197 cin.tie(NULL); 198 int t; cin >> t; 199 while(t--) solve(); 200 } 201 ``` 202 203 [1817C - Подобные многочлены](/contest/1817/problem/C "Codeforces Round 869 (Div. 1)") 204 205 Problem idea: [adamant](/profile/adamant "Мастер adamant") 206 Preparation: [adamant](/profile/adamant "Мастер adamant") 207 208 **Editorial** 209 210 Tutorial is loading... 211 212 **Solution** 213 214 ``` 215 const int mod = 1e9 + 7; 216 217 namespace algebra { 218 const int maxn = 3e6 + 42; 219 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 220 221 template<typename T> 222 T bpow(T x, size_t n) { 223 if(n == 0) { 224 return T(1); 225 } else { 226 auto t = bpow(x, n / 2); 227 t = t * t; 228 return n % 2 ? x * t : t; 229 } 230 } 231 232 const int m = mod; 233 struct modular { 234 int r; 235 constexpr modular(): r(0) {} 236 constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;} 237 modular inv() const {return bpow(*this, m - 2);} 238 modular operator - () const {return r ? m - r : 0;} 239 modular operator * (const modular &t) const {return (int64_t)r * t.r % m;} 240 modular operator / (const modular &t) const {return *this * t.inv();} 241 modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;} 242 modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;} 243 modular operator + (const modular &t) const {return modular(*this) += t;} 244 modular operator - (const modular &t) const {return modular(*this) -= t;} 245 modular operator *= (const modular &t) {return *this = *this * t;} 246 modular operator /= (const modular &t) {return *this = *this / t;} 247 248 bool operator == (const modular &t) const {return r == t.r;} 249 bool operator != (const modular &t) const {return r != t.r;} 250 bool operator < (const modular &t) const {return r < t.r;} 251 252 explicit operator int() const {return r;} 253 int64_t rem() const {return 2 * r > m ? r - m : r;} 254 }; 255 256 istream& operator >> (istream &in, modular &x) { 257 return in >> x.r; 258 } 259 260 ostream& operator << (ostream &out, modular const& x) { 261 return out << x.r; 262 } 263 264 vector<modular> F(maxn), RF(maxn); 265 266 template<typename T> 267 T fact(int n) { 268 static bool init = false; 269 if(!init) { 270 F[0] = T(1); 271 for(int i = 1; i < maxn; i++) { 272 F[i] = F[i - 1] * T(i); 273 } 274 init = true; 275 } 276 return F[n]; 277 } 278 279 template<typename T> 280 T rfact(int n) { 281 static bool init = false; 282 if(!init) { 283 RF[maxn - 1] = T(1) / fact<T>(maxn - 1); 284 for(int i = maxn - 2; i >= 0; i--) { 285 RF[i] = RF[i + 1] * T(i + 1); 286 } 287 init = true; 288 } 289 return RF[n]; 290 } 291 } 292 293 using namespace algebra; 294 295 using base = modular; 296 297 void solve() { 298 int d; 299 cin >> d; 300 vector<base> A(d + 1), B(d + 1); 301 copy_n(istream_iterator<base>(cin), d + 1, begin(A)); 302 copy_n(istream_iterator<base>(cin), d + 1, begin(B)); 303 base s = 0, k2 = 0; 304 auto coef = [&](int i) { 305 return base((d - i) % 2 ? -1 : 1) * rfact<base>(i) * rfact<base>(d - i); 306 }; 307 for(int i = 0; i <= d; i++) { 308 s += (A[i] - B[i]) * coef(i) * (d * (d + 1) / 2 - i); 309 k2 += (A[i] + B[i]) * coef(i); 310 } 311 s *= base(2) / (k2 * d); 312 cout << s << "\n"; 313 } 314 ``` 315 316 [1817D - Автомат с игрушками](/contest/1817/problem/D "Codeforces Round 869 (Div. 1)") 317 318 Problem idea: [adamant](/profile/adamant "Мастер adamant") 319 Preparation: [jeroenodb](/profile/jeroenodb "Гроссмейстер jeroenodb") 320 321 **Editorial** 322 323 Instead of caring about the positions of all the toys, we only need to care about the position of the special toy with index $k$. The other toys can be treated as undistinguishable. 324 325 The intended way of solving this problem is playing the game in the webpage, trying to come up with some simple combinations of operations that make the special toy move to another position in a predictable way. Using these building blocks in a smart way, finding a way to move the special toy to the topleft. 326 327 As the size of the grid can be up to $100\,000$ and we can make $1\,000\,000$ moves, we will be aiming for a solution which does a linear number of moves. 328 329 There are lots of potential solutions which use a linear number of moves, here is a relatively painless one: 330 331 Do casework on $k$: 332 333 * Case $1$: If $1 \leq k \lt \frac{n-1}{2}$, we initally make one $\texttt{R}$ button press to align the toys with the right boundary. After this, there is an easy pattern to expose all the toys in the left halve, one by one: $\texttt{DRURDRUR...}$ repeated. When the special toy is exposed, the repeating pattern is stopped, and $\texttt{DL}$ are pressed. Toy $k$ will be moved to the topleft corner. 334 335 **Visualization** 336 337  Left halve solution for $n=15$. 338 339 * Case $2$: If $k = \frac{n-1}{2}$, the puzzle can be solved in two moves: $\texttt{DL}$. 340 341 **Visualization** 342 343  Solution for middle toy and $n=15$. 344 345 * Case $3$: If $\frac{n-1}{2} \lt k \leq n-2$, we try to reduce back to case $1$, by moving the special toy to the left halve, and ensuring that all other toys are in the top row. Using symmetry, we can apply case $1$ to $k^\prime = n-1 - k$, but mirror all horizontal moves, to move the toy to the topright corner. The other toys are no longer all in the top row. To fix this, the last pattern we need is again $\texttt{DRURDRUR...}$ repeated. After a while of repeating this, all toys will be in the right halve of the board, occupying the top and bottom row. To finish moving the special toy (which stayed in the topright corner), we do the buttons presses $\texttt{LDRU}$. All toys end up in the top row, and the special toy will be at position $k_\text{new} = \frac{n-1}{2} - 1$, so this successfully reduces to case $1$. 346 347 **Visualization** 348 349  Full solution for right halve for $n=15$. 350 351 How many moves does this take? In case $1$ the pattern $\texttt{DRUR}$ needs to be repeated at most $\approx \frac{n}{2}$ times. In case $3$, we need to use the first pattern $\frac{n}{2}$ times, and we use the second pattern $\frac{n}{2}$ times. We reduce down to case $1$, but luckily the special toy is already close to the correct position, so only a constant number of extra moves are done. 352 353 So in total, this solution uses $O(1) + \max \left( 4\frac{n}{2}, 4 \cdot 2 \frac{n}{2} \right) = 4n + O(1)$ moves. So this solution fits well within the constraints, although it is pretty wasteful. 354 355 Bonus: Can you prove that the optimal number of moves needed in the worstcase (over all $k$) for a width of $n$ is $\Omega(n)$? We only did some testing of small cases, with a bruteforce BFS solution, and found that the worstcase is around $n/2$ button presses. 356 357 **Solution** 358 359 ``` 360 #include "bits/stdc++.h" 361 using namespace std; 362 363 int main() { 364 int n,k; cin >> n >> k; 365 --k; 366 int half = (n-3)/2; 367 string res = ""; 368 if(k==half) { 369 res = "DL"; 370 } else { 371 while(true) { 372 if(k<half) { 373 res+="R"; 374 int need = half-1-k; 375 while(need--) { 376 res+="DRUR"; 377 } 378 res+="DL"; 379 break; 380 } else { 381 int need = k-half-1; 382 while(need--) { 383 res+="LDLU"; 384 } 385 res+="LDR"; 386 for(int i=0;i<half+1;++i) { 387 res+="DRUR"; 388 } 389 res+="LDRU"; 390 k = half-1; 391 } 392 } 393 } 394 cout << res << '\n'; 395 } 396 ``` 397 398 [1817E - Полусумма](/contest/1817/problem/E "Codeforces Round 869 (Div. 1)") 399 400 Problem idea: [adamant](/profile/adamant "Мастер adamant") 401 Preparation: [adamant](/profile/adamant "Мастер adamant") 402 403 **Editorial** 404 405 Tutorial is loading... 406 407 **Solution** 408 409 ``` 410 // split into 1, ..., k and k+1, ..., n 411 pair<int, istring> check_k(istring const& a, int k) { 412 int n = size(a); 413 istring A(n, 0), B(n, 0); 414 for(int i = 0; i < n; i++) { 415 if(i <= k) { 416 A[min(k, i + 1)] += a[i]; 417 } else { 418 B[min(n - k - 2, n - i)] += a[i]; 419 } 420 } 421 // multiply by 2^(n - i - 1) instead of dividing by 2^i 422 reverse(all(A)); 423 reverse(all(B)); 424 int carry = 0; 425 // subtract A from B and normalize base 2 426 for(int i = 0; i < n; i++) { 427 B[i] -= A[i] - carry; 428 carry = B[i] >> 1; // floor(B[i] / 2) 429 B[i] &= 1; 430 } 431 if(carry < 0) { 432 return {-1, {}}; // it's always possible to make it positive 433 } 434 while(carry) { 435 B.push_back(carry & 1); 436 carry >>= 1; 437 } 438 while(!B.empty() && B.back() == 0) { 439 B.pop_back(); 440 } 441 reverse(all(B)); 442 return {(int)size(B) - n, B}; 443 } 444 445 const int mod = 1e9 + 7; 446 447 int bpow(int x, int n) { 448 if(!n) { 449 return 1; 450 } else if(n % 2) { 451 return int64_t(x) * bpow(x, n - 1) % mod; 452 } else { 453 return bpow(int64_t(x) * x % mod, n / 2); 454 } 455 } 456 457 int inv(int x) { 458 return bpow(x, mod - 2); 459 } 460 461 void solve() { 462 int n; 463 cin >> n; 464 istring a(n, 0); 465 for(int i = 0; i < n; i++) { 466 cin >> a[i]; 467 } 468 sort(all(a)); 469 auto cand = check_k(a, 0); 470 int cnt = 0; 471 for(int i = 1; i < n; i++) { 472 if(a[i] != a[i - 1]) { 473 cand = max(cand, check_k(a, i - 1)); 474 cnt++; 475 if(cnt == 30) { 476 break; 477 } 478 } 479 } 480 cnt = 0; 481 istring b = a; 482 reverse(all(b)); 483 for(int i = 1; i < n; i++) { 484 if(b[i] != b[i - 1]) { 485 cand = max(cand, check_k(a, n - i - 1)); 486 cnt++; 487 if(cnt == 30) { 488 break; 489 } 490 } 491 } 492 auto [sz, ansf] = cand; 493 int ans = 0; 494 for(size_t i = 0; i < size(ansf); i++) { 495 ans = (ans + bpow(2, (mod - 1) + (sz - i)) * ansf[i]) % mod; 496 } 497 cout << ans << "\n"; 498 } 499 ``` 500 501 [1817F - Запутанные строки](/contest/1817/problem/F "Codeforces Round 869 (Div. 1)") 502 503 Problem idea: [adamant](/profile/adamant "Мастер adamant") 504 Preparation: [adamant](/profile/adamant "Мастер adamant") 505 506 **Editorial** 507 508 Tutorial is loading... 509 510 **Solution** 511 512 ``` 513 map<char, int> to[maxn]; 514 int len[maxn], link[maxn]; 515 int last, sz = 1; 516 517 void add_letter(char c) { 518 int p = last; 519 last = sz++; 520 len[last] = len[p] + 1; 521 for(; to[p][c] == 0; p = link[p]) { 522 to[p][c] = last; 523 } 524 int q = to[p][c]; 525 if(q != last) { 526 if(len[q] == len[p] + 1) { 527 link[last] = q; 528 } else { 529 int cl = sz++; 530 len[cl] = len[p] + 1; 531 link[cl] = link[q]; 532 to[cl] = to[q]; 533 link[last] = link[q] = cl; 534 for(; to[p][c] == q; p = link[p]) { 535 to[p][c] = cl; 536 } 537 } 538 } 539 } 540 541 int term[maxn]; 542 int used[maxn], comp[maxn], dist[maxn]; 543 vector<int> in_comp[maxn]; 544 545 void dfs(int v = 0) { 546 comp[v] = v; 547 dist[v] = 0; 548 used[v] = 1; 549 for(auto [c, u]: to[v]) { 550 if(!used[u]) { 551 dfs(u); 552 } 553 if(to[v].size() == 1 && !term[v]) { 554 comp[v] = comp[u]; 555 dist[v] = dist[u] + 1; 556 } 557 } 558 in_comp[comp[v]].push_back(v); 559 } 560 561 void solve() { 562 string s; 563 cin >> s; 564 for(auto c: s) { 565 add_letter(c); 566 } 567 for(int p = last; p; p = link[p]) { 568 term[p] = 1; 569 } 570 term[0] = 1; 571 dfs(); 572 int64_t ans = 0; 573 for(int v = 0; v < sz; v++) { 574 if(in_comp[v].size()) { 575 int m = in_comp[v].size(); 576 sort(all(in_comp[v]), [&](int a, int b) { 577 return dist[a] > dist[b]; 578 }); 579 vector<int64_t> A(m), B(m); 580 for(int i = 0; i < m; i++) { 581 int u = in_comp[v][i]; 582 int L = dist[u]; 583 int R = L + len[link[u]]; 584 // L' must be larger than R 585 int cnt = len[u] - len[link[u]]; 586 A[i] = (int64_t)cnt * L; 587 B[i] = cnt; 588 if(i > 0) { 589 A[i] += A[i - 1]; 590 B[i] += B[i - 1]; 591 } 592 auto it = upper_bound(all(in_comp[v]), R, [&](int R, int b) { 593 return R > dist[b]; 594 }) - begin(in_comp[v]); 595 if(it) { 596 it--; 597 ans += A[it] - B[it] * R; 598 } 599 } 600 } 601 } 602 cout << ans << "\n"; 603 } 604 ```