1944.md (43456B)
1 Source: https://codeforces.com/blog/entry/127195 2 3 Sorry for the delay in publishing the editorial. If anything is unclear or missing, please let me know in the comments. 4 5 In all the problems, reading the hints is a must as the solution continues from there. 6 7 [1944A - Destroying Bridges](/contest/1944/problem/A "Codeforces Round 934 (Div. 2)") 8 9 Idea: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 10 Preparation: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 11 Editorial: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 12 13 **Hint 1** 14 15 What is the minimum number of bridges to burn if we want to make exactly $i$ islands visitable from $1$? 16 17 **O(n) Solution** 18 19 Atleast $i \cdot (n - i)$ bridges need to burnt (the bridges connecting the $i$ reachable islands and the $n - i$ non-reachable islands). 20 21 A simple $O(n)$ solution is for every $i$ from $1$ to $n$, check if $i \cdot (n - i) \le k$, in which case print $i$ and break. 22 23 **Hint 2** 24 25 What is the answer when $k \ge n - 1$. 26 27 **Hint 3** 28 29 When $k \lt n - 1$, is it possible to make any island non-visitable? 30 31 **O(1) Solution** 32 33 When $k \ge n - 1$, the answer is $1$ since we can just destroy all bridges $(1, i)$ for $2 \le i \le n$. 34 35 Otherwise, suppose we tried to make some set of $i$ islands non-visitable, and the other $n - i$ nodes reachable from $1$. Then we need to burn atleast $i \cdot (n - i)$ bridges (the bridges connecting the $2$ sets). It is not hard to see that this function attains the minimum value when $i = 1$ or $i = n - 1$ for $1 \le i \lt n$. Hence the minimum number of bridges to burn always exceeds $n - 1$. 36 37 **Formal Proof** 38 39 The function $f(x) = x \cdot (n - x)$ is a quadratic function in $x$, which attains maximum value at $x = \frac{n}{2}$, and the value decreasing proportionally as the distance from $\frac{n}{2}$ increases. This means that $f(1) = f(n - 1)$, and $f(1) \gt f(i)$ for all ($2 \le i \le (n - 2)$). 40 41 **Code (O(n))** 42 43 ``` 44 #include <bits/stdc++.h> 45 using namespace std; 46 47 int main(){ 48 int t; cin >> t; 49 while (t--){ 50 int n, k; cin >> n >> k; 51 for (int i = 1; i <= n; i++){ 52 if (i * (n - i) <= k){ 53 cout << i << "\n"; 54 break; 55 } 56 } 57 } 58 return 0; 59 } 60 ``` 61 62 **Code (O(1))** 63 64 ``` 65 #include <bits/stdc++.h> 66 using namespace std; 67 68 int main(){ 69 int t; cin >> t; 70 while (t--){ 71 int n, k; cin >> n >> k; 72 if (k >= n - 1) cout << 1 << "\n"; 73 else cout << n << "\n"; 74 } 75 return 0; 76 } 77 ``` 78 79 [1944B - Equal XOR](/contest/1944/problem/B "Codeforces Round 934 (Div. 2)") 80 81 Idea : [satyam343](/profile/satyam343 "Master satyam343") 82 Preparation : [satyam343](/profile/satyam343 "Master satyam343") 83 Editorial : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 84 85 **Hint 1** 86 87 Group numbers according to how many times they occur in $a[1...n]$. 88 89 **Hint 2** 90 91 The group of numbers having $0$ occurrences in $a[1...n]$ is of the same size as the group of numbers having $2$ occurences in $a[1...n]$. 92 93 **Hint 3** 94 95 Try to use the $0$ and $2$ occurrence numbers first, and then if we still need more, we can use the $1$ occurence numbers. Remember that we have to form sequences of size $2 \cdot k$ which is even. 96 97 **Solution** 98 99 We can append any $2$ occurrence numbers to our sequence $l$ and any $0$ occurrence numbers to our sequence $r$ without any issue because the xor value will cancel out. We do this while our sequence sizes are less than $2 \cdot k$. At the end of this process, $l$ and $r$ will have the same size due to Hint $2$. 100 101 Now, we use as many $1$ occurrence numbers appending to both $l$ and $r$ as needed. Since we append to both sequences, the xor value of the $2$ sequences will be the same. 102 103 If we had to solve for odd sequence sizes, we could take a $1$ occurrence number at the very start to make it even, and then run the same process, but if there are no $1$ occurrence numbers at all, we fail with this method. 104 105 **Code** 106 107 ``` 108 #include <bits/stdc++.h> 109 using namespace std; 110 111 int main(){ 112 int t; cin >> t; 113 while (t--){ 114 int n, k; 115 cin >> n >> k; 116 k = 2 * k; 117 118 vector <int> a(2 * n), occ(n + 1, 0); 119 120 for (auto &x : a) cin >> x; 121 for (int i = 0; i < n; i++) occ[a[i]]++; 122 123 vector <int> g0, g1, g2; 124 for (int i = 1; i <= n; i++){ 125 if (occ[i] == 0) g0.push_back(i); 126 else if (occ[i] == 1) g1.push_back(i); 127 else g2.push_back(i); 128 } 129 130 int v = 0; 131 for (auto x : g2){ 132 if (v < k){ 133 v += 2; 134 cout << x << " " << x << " "; 135 } 136 } 137 for (auto x : g1){ 138 if (v < k){ 139 v++; 140 cout << x << " "; 141 } 142 } 143 cout << "\n"; 144 145 v = 0; 146 for (auto x : g0){ 147 if (v < k){ 148 v += 2; 149 cout << x << " " << x << " "; 150 } 151 } 152 for (auto x : g1){ 153 if (v < k){ 154 v++; 155 cout << x << " "; 156 } 157 } 158 cout << "\n"; 159 } 160 return 0; 161 } 162 ``` 163 164 [1943A - MEX Game 1](/contest/1943/problem/A "Codeforces Round 934 (Div. 1)") 165 166 Idea : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 167 Preparation : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 168 Editorial : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 169 170 **Hint 1** 171 172 Alice can adapt to Bob's strategy. Try to keep that in mind. 173 174 **Big Hint 2** 175 176 Whenever Bob chooses $i$, and if there are any copies of $i$ left, Alice can take $i$ on her next move. 177 178 **Hint 3** 179 180 Let $f$ be the frequency array of $a$. You can ignore all $f(i) \ge 2$ due to the previous hint. Now the answer is some simple casework. 181 182 **Solution** 183 184 For any $i$ s.t. $f_i \ge 2$, whenever Bob chooses to remove an occurence of $i$, on the next move Alice simply chooses $i$ herself (if she hasn't already taken $i$ before that). Thus, we only focus on $f_i \le 1$ now. 185 186 The answer is min(first $i$ s.t. $f(i) = 0$, second $i$ s.t. $f(i) = 1$). 187 188 Obviously, Alice can't do better than the mex of array (first $i$ s.t. $f(i) = 0$). Further, among $f(i) = 1$, Alice can save atmost $1$ $i$ after which Bob will remove the smallest $f(i) = 1$ he can find. This is optimal for Bob as well because he cannot do better when Alice removes the (first $i$ s.t. $f(i) = 1$) on her first move. 189 190 **Code** 191 192 ``` 193 #include <bits/stdc++.h> 194 using namespace std; 195 196 int main(){ 197 int t; cin >> t; 198 while (t--){ 199 int n; cin >> n; 200 vector <int> f(n + 1, 0); 201 202 for (int i = 0; i < n; i++){ 203 int x; cin >> x; 204 f[x]++; 205 } 206 207 int c = 0; 208 for (int i = 0; i <= n; i++){ 209 c += (f[i] == 1); 210 if ((c == 2) || (f[i] == 0)){ 211 cout << i << "\n"; 212 break; 213 } 214 } 215 } 216 return 0; 217 } 218 ``` 219 220 [1943B - Non-Palindromic Substring](/contest/1943/problem/B "Codeforces Round 934 (Div. 1)") 221 222 Idea : [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 223 Preparation : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 224 Editorial : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 225 226 **Hint 1** 227 228 When is a string not $k$-good? (Ignore the trivial edge cases of $k = 1$ and $k = n$). 229 230 **Hint 2** 231 232 What happens when $s[i....j]$ and $s[i + 1....j + 1]$ are both palindromes? 233 234 **Solution** 235 236 We first try to find the answer for a string 237 238 Let $k = j - i + 1$, $s[i....j]$ -> I and $s[i + 1...j + 1]$ -> II are both palindromes. 239 240 Then $s_i = s_j$ (due to I) 241 $s_j = s_{i + 2}$ (due to II) 242 $s_{i + 2} = s_{j - 2}$ (due to I) 243 $s_{j - 2} = s_{i + 4}$ (due to II) 244 and so on.... you can see that it forces $s_i = s_{i + 2} = s_{i + 4} = ....$. A similiar reasoning gives you $s_{i + 1} = s_{i + 3} = s_{i + 5}$. 245 246 Further, if $k$ is even, $i$ and $j$ have different parities, but $s_i = s_j$ implies that all characters must be equal actually. 247 248 We mentioned that the edge cases are $1$ and $n$, but why exactly? How does the analysis fail for them?(Left as a exercise) 249 250 So, the condition for a string to be $k$-good can be written as follows : $k = 1$ : never possible 251 $1 \lt k \lt n$, odd : not an alternating string 252 $1 \lt k \lt n$, even : not all characters same 253 $k = n$ : non-palindromic string 254 255 Now onto substring queries. The second and third things are easy to handle, you can store the next position where $s_i \ne s_{i + 2}$ and $s_i \ne s_{i + 1}$ respectively. Checking if a substring is a palindrome is standard with various methods such as string hashing or manacher's algorithm. 256 257 **Code** 258 259 ``` 260 #include <bits/stdc++.h> 261 using namespace std; 262 263 #define INF (int)1e18 264 265 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 266 267 vector<int> manacher_odd(string s) { 268 int n = s.size(); 269 s = "$" + s + "^"; 270 vector<int> p(n + 2); 271 int l = 1, r = 1; 272 for(int i = 1; i <= n; i++) { 273 p[i] = max(0, min(r - i, p[l + (r - i)])); 274 while(s[i - p[i]] == s[i + p[i]]) { 275 p[i]++; 276 } 277 if(i + p[i] > r) { 278 l = i - p[i], r = i + p[i]; 279 } 280 } 281 return vector<int>(begin(p) + 1, end(p) - 1); 282 } 283 284 vector<int> manacher(string s) { 285 string t; 286 for(auto c: s) { 287 t += string("#") + c; 288 } 289 auto res = manacher_odd(t + "#"); 290 return vector<int>(begin(res) + 1, end(res) - 1); 291 } 292 293 #define int long long 294 295 void Solve() 296 { 297 int n, q; cin >> n >> q; 298 299 string s; cin >> s; 300 auto v = manacher(s); 301 for (auto &x : v) x--; 302 303 // we also need to know if all same, and all alternating 304 set <int> s1, s2; 305 for (int i = 0; i < n - 1; i++){ 306 if (s[i] != s[i + 1]) s1.insert(i); 307 if (i != n - 1 && s[i] != s[i + 2]) s2.insert(i); 308 } 309 310 while (q--){ 311 int l, r; cin >> l >> r; 312 l--; 313 r--; 314 315 if (l == r){ 316 cout << 0 << "\n"; 317 continue; 318 } 319 320 int len = r - l + 1; 321 322 int ans; 323 auto it = s1.lower_bound(l); 324 if (it == s1.end() || (*it) >= r){ 325 ans = 0; 326 } else { 327 it = s2.lower_bound(l); 328 if (it == s2.end() || (*it) >= r - 1){ 329 ans = ((len - 1)/ 2) * (((len - 1) / 2) + 1); 330 } else { 331 ans = len * (len - 1) / 2 - 1; 332 } 333 } 334 335 if (v[l + r] < (r - l + 1)) ans += len; 336 337 cout << ans << "\n"; 338 } 339 } 340 341 int32_t main() 342 { 343 auto begin = std::chrono::high_resolution_clock::now(); 344 ios_base::sync_with_stdio(0); 345 cin.tie(0); 346 int t = 1; 347 // freopen("in", "r", stdin); 348 // freopen("out", "w", stdout); 349 350 cin >> t; 351 for(int i = 1; i <= t; i++) 352 { 353 //cout << "Case #" << i << ": "; 354 Solve(); 355 } 356 auto end = std::chrono::high_resolution_clock::now(); 357 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 358 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 359 return 0; 360 } 361 ``` 362 363 [1943C - Tree Compass](/contest/1943/problem/C "Codeforces Round 934 (Div. 1)") 364 365 Idea: [Everule](/profile/Everule "Grandmaster Everule") 366 Preparation: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 367 Editorial: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 368 369 **Hint 1** 370 371 Try to solve for line case. 372 373 **Hint 2** 374 375 You may have to use more than $1$ node for certain cases. 376 377 **Hint 3** 378 379 Extend the solution for the line to the general tree version (consider the diamater). 380 381 **Solution** 382 383 For a line, an obvious bound on the answer is $\lceil \frac{n}{2} \rceil$, as we can colour atmost $2$ nodes per operation. I claim this is achieveable except for when $n$ mod $4 = 2$, where we do $1$ worse. That is however still provably optimal as you can bicolour the line and operations only colours nodes black which are in the same bicolouring. 384 385 **Construction for line** 386 387 When $n$ mod $2 = 1$, simply use the centre of the line and do operations of the form $(centre, i)$ ($0 \le i \le \lfloor \frac{n}{2} \rfloor$). 388 When $n$ mod $4 = 0$, for convenience let the line be $1, 2, ...., n$. Then, we can do operations like $(2, 1), (3, 1), (6, 1), (7, 1)....$. 389 When $n$ mod $4 = 2$, either of the above $2$ methods can be adapted to work because we are allowed $1$ "extra" operation. 390 391 Now that we have the solution for the line case, lets divide into $2$ cases based on parity of diamater (maximum number of nodes on a path) : 392 393 diameter mod $2 = 1$ : Find the centre of the diamater. Then we can simply do operations of the form $(centre, i)$ (for all $0 \le i \le \lfloor \frac{diameter}{2} \rfloor$). If this doesn't colour all nodes, then one can easily check that the diamater we found is not the real diamater, as the node which is not coloured is an endpoint of a larger diameter. 394 395 diamater mod $2 = 0$ : Find the $2$ centres of the diameter. Then the following set of operations satisfy the requirements : $(centre1, i)$ and $(centre2, i)$ for all odd $i$ satisfying $1 \le i \le \frac{diameter}{2}$. The intuition behind this is to basically split the nodes into $2$ sets according to a bicolouring, and then $1$ centre colours all nodes of a certain colour, while the other centre colours all nodes of the other colour. 396 397 **Code** 398 399 ``` 400 #include <bits/stdc++.h> 401 using namespace std; 402 #define int long long 403 #define INF (int)1e18 404 #define f first 405 #define s second 406 407 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 408 409 void Solve() 410 { 411 int n; 412 cin >> n; 413 414 vector<vector<int>> E(n); 415 416 for (int i = 1; i < n; i++){ 417 int u, v; cin >> u >> v; 418 419 u--; v--; 420 E[u].push_back(v); 421 E[v].push_back(u); 422 } 423 424 auto bfs = [&](int s){ 425 vector<int> d(n, -1); 426 d[s] = 0; 427 queue<int> Q; 428 Q.push(s); 429 while (!Q.empty()){ 430 int v = Q.front(); 431 Q.pop(); 432 for (int w : E[v]){ 433 if (d[w] == -1){ 434 d[w] = d[v] + 1; 435 Q.push(w); 436 } 437 } 438 } 439 return d; 440 }; 441 442 vector<int> d1 = bfs(0); 443 int a = max_element(d1.begin(), d1.end()) - d1.begin(); 444 vector<int> d2 = bfs(a); 445 int b = max_element(d2.begin(), d2.end()) - d2.begin(); 446 vector<int> d3 = bfs(b); 447 int diam = d3[max_element(d3.begin(), d3.end()) - d3.begin()] + 1; 448 //if 3 we want 1, 1 if 4 we want 1 2 449 450 vector <int> ans; 451 for (int i = 0; i < n; i++){ 452 if ((d2[i] + d3[i] == diam - 1) && ((d2[i] == diam/2) || (d3[i] == diam/2))) 453 ans.push_back(i); 454 } 455 456 if (diam & 1) assert(ans.size() == 1); 457 else assert(ans.size() == 2); 458 459 vector <pair<int, int>> ok; 460 461 if (diam & 1){ 462 //print everything from 0 to diam/2 463 for (int i = 0; i <= diam/2; i++){ 464 ok.push_back({ans[0], i}); 465 } 466 } else { 467 //2 => 2 ops, 4 => 2 ops , 6 => 4 ops, 8 => 4 ops 468 int ops = ((n - 2)/4) + 1; 469 int need = (diam/2) - 1; 470 while (need >= 0){ 471 ok.push_back({ans[0], need}); 472 ok.push_back({ans[1], need}); 473 474 need -= 2; 475 } 476 } 477 478 cout << ok.size() << "\n"; 479 for (auto [u, r] : ok){ 480 cout << u + 1 << " " << r << "\n"; 481 } 482 } 483 484 int32_t main() 485 { 486 auto begin = std::chrono::high_resolution_clock::now(); 487 ios_base::sync_with_stdio(0); 488 cin.tie(0); 489 int t = 1; 490 cin >> t; 491 for(int i = 1; i <= t; i++) 492 { 493 //cout << "Case #" << i << ": "; 494 Solve(); 495 } 496 auto end = std::chrono::high_resolution_clock::now(); 497 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 498 // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 499 return 0; 500 } 501 ``` 502 503 [1943D1 - Counting Is Fun (Easy Version)](/contest/1943/problem/D1 "Codeforces Round 934 (Div. 1)") 504 505 Idea : [satyam343](/profile/satyam343 "Master satyam343") 506 Preparation : [satyam343](/profile/satyam343 "Master satyam343") 507 Editorial : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 508 509 **Hint 1** 510 511 Try to come up with some necessary and sufficient conditions of a good array. 512 513 **Hint 2** 514 515 Apply dp once you have a good condition. 516 517 **Solution** 518 519 All operations which include $i$ must also either include $i - 1$ or $i + 1$. Hence $a_i \le a_{i - 1} + a_{i + 1}$ must hold. Throughout the editorial treat $a_i = 0$ for $(i \le 0)$ or $(i \gt n)$. 520 521 But, is this sufficient? Infact, it is and we can prove it by strong induction. 522 523 **Proof** 524 525 Group arrays according to the sum of the array. We will now apply strong induction on the sum of the array. 526 527 Base Cases (sum = 0, 1 or 2) are all trivial. 528 529 Now, assume that the condition is sufficient for all arrays with sum $ \lt x$ ($x \ge 3$). 530 Let us consider some array $a_1, a_2, ...., a_n$ with sum $x$. Let $a_i$ be the first non-zero element of $a$.(Observe that $a_{i + 1}$ can't be $0$). 531 We claim that either operating on $[i, i + 1]$ or $[i, i + 2]$ will give still satisfy the condition $a_j \le a_{j - 1} + a_{j + 1}$ for all $j$. 532 533 Let's check it. The only time $[i, i + 1]$ operation causes an issue is when $a_{i + 2} \gt a_{i + 1} - 1 + a_{i + 3}$, i.e. it should necessarily hold that $a_{i + 2} \gt a_{i + 3}$, but then $a_{i + 3} \le a_{i + 2} - 1$, and so, $a_{i + 3} \le a_{i + 2} - 1 + a_{i + 4}$, meaning $[i, i + 2]$ is valid. 534 535 Now that we have the condition, we can define a dynamic programming as follows : 536 537 $dp(i, a, b)$ = number of ways to make an array upto the $i$-th index with $a_{i - 1} = a$, $a_i = b$ (since only the last $2$ elements are relevant). 538 539 Let the new element be $c$, then it is a valid way iff $b \le a + c$. So we have a $\mathcal{O}(n^4)$ by iterating over all possibilities. 540 541 As a final optimization, we can speed it up to $\mathcal{O}(n^3)$ by using prefix sums. Note that the valid values of $a$ for fixed $b$ and $c$ satisfy $a \ge max(0, b - c)$, and hence maintaining prefix sums over $a$, we can speed it up. 542 543 **Code** 544 545 ``` 546 #include <bits/stdc++.h> 547 using namespace std; 548 #define int long long 549 #define INF (int)1e18 550 #define f first 551 #define s second 552 553 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 554 555 void Solve() 556 { 557 int n, k, mod; cin >> n >> k >> mod; 558 559 vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0)); 560 dp[0][0] = 1; // dp[a][b] 561 562 for (int i = 1; i <= n + 2; i++){ 563 vector<vector<int>> ndp(k + 1, vector<int>(k + 1, 0)); // dp[b][c] 564 vector<vector<int>> pref(k + 1, vector<int>(k + 1, 0)); // pref[b][a] 565 566 for (int b = 0; b <= k; b++){ 567 pref[b][0] = dp[0][b]; 568 for (int a = 1; a <= k; a++){ 569 pref[b][a] = (pref[b][a - 1] + dp[a][b]) % mod; 570 } 571 } 572 573 for (int b = 0; b <= k; b++){ 574 for (int c = 0; c <= k; c++){ 575 if (b > c){ 576 // a must be atleast b - c 577 ndp[b][c] = (pref[b][k] - pref[b][b - c - 1] + mod) % mod; 578 } else { 579 ndp[b][c] = pref[b][k]; 580 } 581 } 582 } 583 584 dp = ndp; 585 } 586 587 cout << dp[0][0] << "\n"; 588 } 589 590 int32_t main() 591 { 592 auto begin = std::chrono::high_resolution_clock::now(); 593 ios_base::sync_with_stdio(0); 594 cin.tie(0); 595 int t = 1; 596 // freopen("in", "r", stdin); 597 // freopen("out", "w", stdout); 598 599 cin >> t; 600 for(int i = 1; i <= t; i++) 601 { 602 //cout << "Case #" << i << ": "; 603 Solve(); 604 } 605 auto end = std::chrono::high_resolution_clock::now(); 606 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 607 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 608 return 0; 609 } 610 ``` 611 612 [1943D2 - Counting Is Fun (Hard Version)](/contest/1943/problem/D2 "Codeforces Round 934 (Div. 1)") 613 614 Idea : [satyam343](/profile/satyam343 "Master satyam343") 615 Preparation : [satyam343](/profile/satyam343 "Master satyam343") 616 Editorial : [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 617 618 **Hint 1** 619 620 Try to apply Principle of Inclusion Exclusion (PIE). 621 622 **Hint 2** 623 624 You do not need to store both last elements! Only the last is enough. 625 626 **Solution** 627 628 Since there are $n^3$ states in our dp, we will have to optimize the number of states somehow. 629 630 Let us consider all arrays and not just good arrays. An element is bad if $a_i \gt a_{i - 1} + a_{i + 1}$. 631 632 Suppose, $f(x_1, x_2, ...., x_k)$ gave us the number of arrays where each of $x_i$ are distinct and bad. (Note that other positions may be bad as well). Then, by PIE, the answer is $(-1)^k \cdot f(x_1, x_2, ....., x_k)$. 633 634 For example, for $n = 3$, we would want to compute $f([]) - f([1]) - f([2]) - f([3]) + f([1, 2]) + f([1, 3]) + f([2, 3]) - f([1, 2, 3])$. Note that $f([])$ is simply $(k + 1)^n$ as there are no restrictions placed on the array. 635 636 This has $2^n$ calculations, so we need to optimize it. 637 638 First optimization : obviously, only $k$ matters and not the exact indices. This means we only have to maintain the count of the number of indices we have made sure are bad. 639 640 Second optimization : only parity of $k$ matters, due to the only dependence of $k$ being $(-1)^k$. 641 642 We now define $dp(i, last, x)$ = number of arrays such that $a_i = last$ and the parity of bad elements (that we know of) till $i$ is $x$. 643 644 Transitions : 645 646 * Without (necessarily) creating a bad element : $dp(i, last, x) += dp(i - 1, y, x)$ for all $0 \le y \le k$. We might accidentally create more bad elements, but remember that PIE allows us to not worry about that. 647 * With creating a bad element : We view it as a transition from index $(i - 2)$, $a_{i - 1} \gt a_i + a_{i - 2}$ for it to bad, so fix $a_i = l1$, $a_{i - 2} = l2$, and you get $dp(i, l1, x) += dp(i - 2, l2, 1 - x) \cdot (max(0, k - l1 - l2))$. 648 The $max(0, k - l1 - l2)$ term comes from the ways to choose $a_{i - 1}$ such that $a_{i - 1} \gt l1 + l2$. 649 650 Both the transitions are optimizable with some prefix sums and running totals to get a $\mathcal{O}(n^2)$ solution. 651 652 **Code** 653 654 ``` 655 #include <bits/stdc++.h> 656 using namespace std; 657 #define int long long 658 #define INF (int)1e18 659 #define f first 660 #define s second 661 662 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 663 664 void Solve() 665 { 666 int n, k, mod; cin >> n >> k >> mod; 667 668 vector<vector<int>> dp(2, vector<int>(k + 1, 0)); 669 auto prev2 = dp; 670 dp[0][0] = 1; 671 672 for (int i = 1; i <= n + 1; i++){ 673 vector<vector<int>> ndp(2, vector<int>(k + 1, 0)); 674 vector<int> sum(2, 0); 675 676 for (int j = 0; j < 2; j++) for (int x = 0; x <= k; x++){ 677 sum[j] += dp[j][x]; sum[j] %= mod; 678 } 679 680 for (int j = 0; j < 2; j++){ 681 int s1 = 0, s2 = 0; 682 683 for (int x = k; x >= 0; x--){ 684 ndp[j][x] += sum[j]; // normal transition 685 686 ndp[j][x] += s2; ndp[j][x] %= mod; // with one wrong 687 688 s1 += prev2[j ^ 1][k - x]; s1 %= mod; 689 s2 += s1; s2 %= mod; 690 } 691 } 692 693 prev2 = dp; 694 dp = ndp; 695 } 696 697 int ans = (dp[0][0] - dp[1][0] + mod) % mod; 698 cout << ans << "\n"; 699 } 700 701 int32_t main() 702 { 703 auto begin = std::chrono::high_resolution_clock::now(); 704 ios_base::sync_with_stdio(0); 705 cin.tie(0); 706 int t = 1; 707 // freopen("in", "r", stdin); 708 // freopen("out", "w", stdout); 709 710 cin >> t; 711 for(int i = 1; i <= t; i++) 712 { 713 //cout << "Case #" << i << ": "; 714 Solve(); 715 } 716 auto end = std::chrono::high_resolution_clock::now(); 717 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 718 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 719 return 0; 720 } 721 ``` 722 723 [1943E1 - MEX Game 2 (Easy Version)](/contest/1943/problem/E1 "Codeforces Round 934 (Div. 1)") 724 725 Idea: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 726 Preparation: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 727 Editorial: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 728 729 **Hint 1** 730 731 It might be optimal for Bob to reduce multiple elements at the same time, thus making Alice choose between which element she wants to take. 732 733 **Hint 2** 734 735 Suppose you are only checking whether $ans \ge i$ for now, what would Alice's strategy be? 736 737 **Hint 3** 738 739 Try fixing the element that Bob wants to make sure Alice is not able to get. What would be his strategy then? 740 741 **Solution** 742 743 For now, lets try to see if $ans \ge i$. This is equivalent to Alice being able to take $1$ occurence of everything when the game is reduced to numbers $[0, i - 1]$. 744 745 Alice's strategy here is actually easy to find. At every step, Alice will choose the minimum $f_j$ such that $0 \le j \lt i$, and she hasn't chosen $i$ yet. You can reason this with greedy stays ahead, exchange argument, whatever you want. 746 747 This gives us a nice definition of Alice's moves, however we seemingly have to maintain the sorted sequence of $f_i$ always. But we can actually rewrite Bob's moves such that it does not affect the sorted order of $f_i$ and always keeps it sorted. Here, by sorted order, we mean some permutation $p = [p_1, p_2, ...., p_i]$ of $[0, i - 1]$ such that $f_{p_i} \le f_{p_j}$ whenever $i \le j$. 748 749 First, instead of subtracting $k$, we will do $k$ subtractions of only $1$. Then, the only case when sorted order can be destroyed is when there exists $k1$ and $k2$ such that $f_{k1} = f_{k2}$ and we do an operation on $k1$ but $k2$ occurs before $k1$ in the sorted order. This issue can simply be fixed by doing the operation on the smallest $x$ (according to sorted order) such that $f_x = f_{k1}$. 750 751 Now, we have a good way of representing Alice moves. Suppose we fixed the element that Bob "wins" on. Then, Bob's strategy will obviously be to make the frequency of that element as small as possible, but he must make sure to never violate sorted condition. Since Bob will make at most $m$ moves, you can just simulate his moves. 752 753 The main details of the simulation is that you need to figure out upto what index all values will become equal when doing k operations (or nearly equal, off by 1), and then first take all elements to that state. Let $w$ be the remaining operations from the $k$ operations after this, and $l$ the length of the equal sequence. Then you will reduce every frequency by $w / l$, and finally reduce the first $w$ mod $l$ numbers of this sequence. Check the code for more details. 754 755 A naive implementation takes $O(m)$ per move, so $O(m^2)$ per element we fix => $O(m^3)$ total to check $ans \ge i$. With a binary search on the answer, you get $O(m^3 logm)$. It can be optimized further, but it wasnt needed to pass. Most other polynomial solutions should pass this. 756 757 **Code** 758 759 ``` 760 #include <bits/stdc++.h> 761 using namespace std; 762 #define int long long 763 #define INF (int)1e18 764 #define f first 765 #define s second 766 767 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 768 769 void Solve() 770 { 771 int n, k; cin >> n >> k; 772 773 vector <int> a(n + 1); 774 for (auto &x : a) cin >> x; 775 776 auto check = [&](int x){ 777 vector <int> b; 778 for (int i = 0; i < x; i++){ 779 b.push_back(a[i] - k); 780 } 781 782 sort(b.begin(), b.end()); 783 784 for (int fix = 1; fix < x; fix++){ 785 // this is element where bob wins 786 787 deque <int> c; 788 for (int i = 0; i <= fix; i++){ 789 c.push_back(b[i]); 790 } 791 792 assert(c.size() >= 2); 793 794 while (c.size() != 2){ 795 c.pop_front(); 796 797 // find suffix which works 798 int sz = c.size(); 799 int works = 0; 800 int sum = 0; 801 for (int j = 1; j < sz; j++){ 802 // sum(elements of c - current element) 803 // this shud be >= k 804 sum += c[sz - j]; 805 int loss = sum - c[sz - j - 1] * j; 806 if (loss >= k){ 807 works = sz - j; 808 break; 809 } 810 } 811 812 int have = k; 813 814 // make everything = c[works] 815 for (int j = works + 1; j < sz; j++){ 816 have -= c[j] - c[works]; 817 c[j] = c[works]; 818 } 819 820 assert(have >= 0); 821 for (int j = works; j < sz; j++){ 822 c[j] -= have / (sz - works); 823 } 824 have %= (sz - works); 825 826 for (int j = works; j < sz; j++){ 827 if (have){ 828 c[j]--; 829 have--; 830 } 831 } 832 833 for (int j = 0; j < sz - 1; j++){ 834 assert(c[j] <= c[j + 1]); 835 } 836 } 837 838 c.pop_front(); 839 if (c[0] <= 0) return false; 840 } 841 842 return true; 843 }; 844 845 int l = 1, r = n + 1; 846 while (l != r){ 847 int mid = (l + r + 1) / 2; 848 849 if (check(mid)) l = mid; 850 else r = mid - 1; 851 } 852 853 cout << l << "\n"; 854 } 855 856 int32_t main() 857 { 858 auto begin = std::chrono::high_resolution_clock::now(); 859 ios_base::sync_with_stdio(0); 860 cin.tie(0); 861 int t = 1; 862 // freopen("in", "r", stdin); 863 // freopen("out", "w", stdout); 864 865 cin >> t; 866 for(int i = 1; i <= t; i++) 867 { 868 //cout << "Case #" << i << ": "; 869 Solve(); 870 } 871 auto end = std::chrono::high_resolution_clock::now(); 872 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 873 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 874 return 0; 875 } 876 ``` 877 878 [1943E2 - MEX Game 2 (Hard Version)](/contest/1943/problem/E2 "Codeforces Round 934 (Div. 1)") 879 880 Idea: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 881 Solution : [ffao](/profile/ffao "International Grandmaster ffao") 882 Preparation: [Dominater069](/profile/Dominater069 "Grandmaster Dominater069") 883 Editorial: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 884 885 **Solution** 886 887 Instead of doing the check for $ans \geq i$ in $O(m^3)$, we will do it in $O(m)$. 888 889 For an array $f$ of length $n$. Let $s=f_1+f_2+\ldots+f_n$ be the sum of the element. $f$ will be called *flat* if $f_i = \lfloor \frac{s+i-1}{n} \rfloor$. That is, it has the form $x, \ldots, x, x+1, \ldots x+1$. All flat array can be characters by $2$ integers $(n,s)$ only. 890 891 Imagine simulating Bob's strategy without simulating Alice's moves of removing the first element of the array. For some prefix of the moves, the actual simulation will be a suffix of this simulation. This is because to subtract something from index $\leq i$, we must have $f_{i+1} = f_{i+2} = \ldots = f_n$. 892 893 As an example, let $k=4$. 894 895 With Alice moves: $[1,2,3,5,5] \to [2,3,3,3] \to [1,2,2]$ 896 897 Without Alice moves: $[1,2,3,5,5] \to [1,2,3,3,3] \to [1,1,2,2,2]$ 898 899 $[1,2,2]$ is not a suffix of $[1,1,2,2,2]$ and is the first time such a thing happens. 900 901 Suppose that the first time this happens is after $p$ moves. Then the resulting array is the flat array $(n-p,f_{p+1}+f_{p+2}+\ldots+f_n-pk)$. To find the necessary value of $p$, we can binary search or run $2$-pointers to check if the suffix of the array can reach $f_p$ with the amount of subtraction operations till then. (What we basically did is find the suffix of the array that actually gets operated on, since that makes it much more easier to solve) 902 903 Then, since the flat array $(n,s)$ becomes $(n-1,s-\lfloor \frac{s}{n} \rfloor - k)$, we can figure out whether each flat array evantually becomes a losing or winning state as we can calculate for each $n$, the minimum $s$ such that $(n,s)$ is a winning state. 904 905 **Code** 906 907 ``` 908 #include <bits/stdc++.h> 909 using namespace std; 910 911 #define int long long 912 #define ll long long 913 #define ii pair<ll,ll> 914 #define iii pair<ii,ll> 915 #define fi first 916 #define se second 917 #define endl '\n' 918 #define debug(x) cout << #x << ": " << x << endl 919 920 #define pub push_back 921 #define pob pop_back 922 #define puf push_front 923 #define pof pop_front 924 #define lb lower_bound 925 #define ub upper_bound 926 927 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 928 #define all(x) (x).begin(),(x).end() 929 #define sz(x) (int)(x).size() 930 931 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 932 933 int n,k; 934 int arr[200005]; 935 int temp[200005]; 936 937 bool solve(vector<int> v){ 938 sort(all(v)); 939 940 rep(x,0,sz(v)) temp[x]=1e18; 941 942 int l=1,curr=0; 943 rep(x,1,sz(v)){ 944 curr+=v[x]; 945 946 while (l<x && (curr-v[l])-(x-l)*v[l] >= l*k){ 947 curr-=v[l]; 948 l++; 949 } 950 951 temp[x-l]=min(temp[x-l],curr-l*k); 952 } 953 954 rep(x,sz(v),1) temp[x-1]=min(temp[x-1],(temp[x]-temp[x]/(x+1))-k); 955 956 return temp[0]>0; 957 } 958 959 signed main(){ 960 ios::sync_with_stdio(0); 961 cin.tie(0); 962 cout.tie(0); 963 cin.exceptions(ios::badbit | ios::failbit); 964 965 int TC; 966 cin>>TC; 967 while (TC--){ 968 cin>>n>>k; 969 rep(x,0,n+1) cin>>arr[x]; 970 971 // solve(vector<int>(arr,arr+n+1)); 972 // continue; 973 974 int lo=0,hi=n+2,mi; 975 while (hi-lo>1){ 976 mi=hi+lo>>1; 977 978 if (solve(vector<int>(arr,arr+mi))) lo=mi; 979 else hi=mi; 980 } 981 982 cout<<lo<<endl; 983 } 984 } 985 ``` 986 987 [1943F - Minimum Hamming Distance](/contest/1943/problem/F "Codeforces Round 934 (Div. 1)") 988 989 Idea: [satyam343](/profile/satyam343 "Master satyam343") 990 Preparation: [satyam343](/profile/satyam343 "Master satyam343") 991 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 992 993 **Hint 1 / Claim 1** 994 995 Assumption: 0 is the mode of string t. If 1 occurs more times than 0 in t, we will flip all characters of s and t so that 0 is the mode of string t. 996 997 Let us say index $i$ *nice* if there exists $l$ and $r$($1 \le l \le i \le r \le n$) such that $s_i$ is the mode of substring $t[l,r]$. 998 999 So we might have some not *nice* indices $i$ such that $s_i =$ $\mathtt{1} $. We will not have any index $i$ such that i is not *nice* and $s_i =$ $\mathtt{0} $, as $\mathtt{0} $ is the mode of $t$. So, we need to fix the not *nice* indices. 1000 1001 Now we will start changing some $\mathtt{0} $ to $\mathtt{1} $. So it might be possible that in final $t$, the frequency of $\mathtt{1} $ is more than that of $\mathtt{0} $, and $\mathtt{0} $ is no longer the mode. So should we worry about indices $ i $ such that $ i $ was nice in the beginning, and now that we made some flips, $ i $ may become not *nice*? 1002 1003 No! It will never be possible. 1004 1005 In case $\mathtt{1} $ occurs more times than $\mathtt{0} $ in the updated $t$, we will have $frequency[1] = frequency[0] + 1$ and $t[1] = t[n] =$ $\mathtt{1} $(we will have such cases for pairs like ($s =$ $\mathtt{011} $, $t =$ $\mathtt{100} $; for this pair final $t$ should be $t =$ $\mathtt{101} $). So the substrings $t[1, n - 1]$ and $t[2, n]$ will have equal numbers of $\mathtt{0} $ and $\mathtt{1} $, and thus all indices should be *nice*. So our claim is that we should change some $\mathtt{0} $ to $\mathtt{1} $, without caring about indices $i$(which were *nice* initially) becoming not *nice* such that $s_i =$ $\mathtt{0} $. 1006 1007 **Hint 2** 1008 1009 We can use dynamic programming here. 1010 So let us have $dp$, such that $dp[i][j]$ gives the minimum number of flips required to make $t[1, i]$ *friend* of $s[1, i]$ and the maximum suffix sum is $j$. 1011 String $x$ is called to be *friend* of string $y(|x| = |y|)$, if for every $i$($1 \le i \le |x|$), there exists indices $l$ and $r$ such that: 1012 1. $1 \le l \le i \le r \le |x|$ 1013 2. $x_i$ is a mode of the string $y[l,r]$ 1014 1015 **Solution** 1016 1017 Please read hints $1$ and $2$ if you haven't as they contain some claims and definitions. 1018 1019 Note that when we find some sum, we add $1$ when we get $\mathtt{1} $ and subtract $-1$ when we get $\mathtt{0} $. 1020 1021 Suppose we have found $dp$ values for the first $i - 1$ indices, and we want to find $dp[i][j]$ for $0 \le j \le n$. Now, we need to perform the transitions. 1022 1023 Let us try to have a $O(n^3)$ solution first, which we can optimise after making some observations. 1024 1025 Take some $l$($0 \leq l \leq i - 1$). We will iterate over $suff$_$sum = 0$ to $n$, here $suff$_$sum$ is the maximum suffix sum of substring $t[1, l]$, and use $dp[l][suff$_$sum]$ to find optimal values for $dp[i][x]$ for some $x$. 1026 1027 So we need to do some flips to substring $t[l + 1, i]$, as $s[1, l]$ and $t[1, l]$ are already *friends*. So we only care to make all indices $j$ ($l + 1 \le j \le i$) *nice*. So there are two possibilities(either $\mathtt{1} $ occurs in substring $s[l + 1, i]$ or not): 1028 1029 1. If $\mathtt{1} $ does not occur, we can perform the transition without making any flips. 1030 2. Assume $\mathtt{1} $ occurs in substring $s[l + 1, i]$. So firstly, find the sum(say $cur$_$sum$) of substring $t[l + 1, i]$. Now, if we do some flips to substring $t[l + 1, i]$, $cur$_$sum$ will change accordingly. We will do a minimum number of flips such that $suff$_$sum + cur$_$sum \ge 0$. Note that we are talking here about updated $cur$_$sum$. So we can find the minimum number(say $cost$) of flips, which will be $\lfloor \frac{\max(0, 1 -d )}{2} \rfloor$, where $d=suff$_$sum + initial$_$cur$_$sum$. So we know how many flips to make. 1031 1032 But which ones to flip? Here is one more claim. We should only flip the last $cost$ $\mathtt{0} $ of substring $t[l + 1, i]$. 1033 1034 So this is a sufficient condition, as we can certainly say that $t[1, i]$ will be *friend* of $s[1, i]$ now. So we know the required number of flips, which is $dp[l][suff$_$sum] + cost$. We need to find one more thing — what would be the maximum suffix sum if we flip the last $cost$ characters of $t[l + 1, i]$? We can precompute. 1035 1036 But we have an issue now. We know that what we performed is sufficient. But is it necessary? What if we did not need to flip cost characters of $t[l + 1, i]$? 1037 1038 It might be possible that we could have done less number of flips and still made all indices $l + 1 \le j \le i$ *nice*. The reasoning behind this is we made sure that $suff$_$sum + cur$_$sum \ge 0$, but what if it was not needed? 1039 1040 Like it is possible that total sum is negative, but all indices $j$($l + 1 \le j \le i$) such that $s_j =$ $\mathtt{1} $ are satisfied. So here, we can use exchange arguments and conclude that all cases will be covered if we check for all pairs of ($l, suff$_$sum$) $0 \le l, suff$_$sum \le i - 1$. 1041 1042 Now we need to optimise this to $O(n^2)$. 1043 1044 Notice that when we do the flips, there will be a suffix(possibly empty when $cost=0$) of $t[l + 1, i]$ containing only $\mathtt{1} $ s. Suppose we are at index $i$ and need to find $dp[i][j]$ for $0 \le j \le i$. We can iterate over all $j$($1 \le j \le i$), assume that all the characters in substring $t[j,i]$ are $\mathtt{1} $ s, and find the $dp$ values. Maximum suffix sum will be $i-j+1+max$_$suffix$_$sum[j-1]$. So we can find the smallest index $p$ such that the sum of the elements in substring $t[p,l]$ is greater than or equal to $0$ if we make all the characters in substring $t[j,i]$ $\mathtt{1} $. 1045 1046 Notice that we already have the new suffix maximum, and we know the $cost$ too, which is equal to the number of $\mathtt{0} $ s in the original substring $t[j,i]$. So our transition will be $dp[i][new$_$suffix$_$max]=\max(dp[i][new$_$suffix$_$max], \min\limits_{k = p-1}^{i} best[k] + cost)$, where $best[i]= \min\limits_{k = 0}^{i} dp[i][k]$. 1047 1048 So, our final complexity will be $O(n^2)$, as we can perform the transition in $O(1)$ if we precompute the needed things. 1049 1050 **Code** 1051 1052 ``` 1053 #include <bits/stdc++.h> 1054 #include <ext/pb_ds/tree_policy.hpp> 1055 #include <ext/pb_ds/assoc_container.hpp> 1056 using namespace __gnu_pbds; 1057 using namespace std; 1058 #define ll int 1059 #define pb push_back 1060 #define mp make_pair 1061 #define nline "\n" 1062 #define f first 1063 #define s second 1064 #define pll pair<ll,ll> 1065 #define all(x) x.begin(),x.end() 1066 const ll MOD=998244353; 1067 const ll MAX=10005; 1068 ll dp[MAX][MAX]; 1069 ll suffix_min[MAX]; 1070 ll suffix_max[MAX]; 1071 ll can_go_till[MAX][MAX+5]; 1072 void solve(){ 1073 ll n; cin>>n; 1074 ll shift=n; 1075 for(ll i=-n;i<=0;i++){ 1076 can_go_till[0][shift+i]=0; 1077 } 1078 string s,t; cin>>s>>t; 1079 s=" "+s,t=" "+t; 1080 ll sum=0; 1081 for(ll i=1;i<=n;i++){ 1082 sum+=2*(t[i]-'0')-1; 1083 } 1084 suffix_max[0]=0; 1085 if(sum>=0){ 1086 for(ll i=1;i<=n;i++){ 1087 s[i]='0'+'1'-s[i]; 1088 t[i]='0'+'1'-t[i]; 1089 } 1090 } 1091 ll max_sum=0; 1092 for(ll i=1;i<=n;i++){ 1093 max_sum+=2*(t[i]-'0')-1; 1094 max_sum=max(0,max_sum); 1095 suffix_max[i]=max_sum; 1096 } 1097 for(ll i=1;i<=n;i++){ 1098 sum=0; 1099 for(ll j=-n;j<=0;j++){ 1100 can_go_till[i][shift+j]=i+1; 1101 } 1102 for(ll j=i;j>=1;j--){ 1103 sum+=2*(t[j]-'0')-1; 1104 ll use=min(sum,0); 1105 can_go_till[i][shift+use]=j; 1106 } 1107 for(ll j=n-1;j>=0;j--){ 1108 can_go_till[i][j]=min(can_go_till[i][j],can_go_till[i][j+1]); 1109 } 1110 } 1111 for(ll i=0;i<=n+1;i++){ 1112 for(ll j=0;j<=n+1;j++){ 1113 dp[i][j]=MOD; 1114 } 1115 } 1116 dp[0][0]=0; 1117 vector<ll> best(n+5,MOD); 1118 best[0]=0; 1119 for(ll i=1;i<=n;i++){ 1120 for(ll l=0;l<=i-1;l++){ 1121 dp[i][l+1]=dp[i-1][l]+(t[i]=='0'); 1122 } 1123 for(ll l=0;l<=i;l++){ 1124 ll new_sum=l+2*(t[i]-'0')-1; 1125 if(s[i]=='1' and new_sum<=-1){ 1126 continue; 1127 } 1128 new_sum=max(0,new_sum); 1129 dp[i][new_sum]=min(dp[i][new_sum],dp[i-1][l]); 1130 } 1131 suffix_min[i]=MOD; 1132 for(ll j=i-1;j>=0;j--){ 1133 suffix_min[j]=min(suffix_min[j+1],best[j]); 1134 } 1135 ll cnt=0; 1136 for(ll j=i;j>=1;j--){ 1137 cnt+=(t[j]=='0'); 1138 ll now=i-j+1; 1139 ll cur_suff_max=now+suffix_max[j-1]; 1140 ll pos=max(0,can_go_till[j-1][shift-now]-1); 1141 dp[i][cur_suff_max]=min(dp[i][cur_suff_max],suffix_min[pos]+cnt); 1142 } 1143 for(ll j=0;j<=n;j++){ 1144 best[i]=min(best[i],dp[i][j]); 1145 } 1146 } 1147 ll ans=MOD; 1148 s[0]='1'; 1149 for(ll i=n;i>=0;i--){ 1150 ans=min(ans,best[i]); 1151 if(s[i]=='1'){ 1152 cout<<ans<<nline; 1153 return; 1154 } 1155 } 1156 return; 1157 } 1158 int main() 1159 { 1160 ios_base::sync_with_stdio(false); 1161 cin.tie(NULL); 1162 #ifndef ONLINE_JUDGE 1163 freopen("input.txt", "r", stdin); 1164 freopen("output.txt", "w", stdout); 1165 freopen("error.txt", "w", stderr); 1166 #endif 1167 ll test_cases=1; 1168 cin>>test_cases; 1169 while(test_cases--){ 1170 solve(); 1171 } 1172 cout<<fixed<<setprecision(10); 1173 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 1174 } 1175 ```