codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1943.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 ```