codeforces-scrape

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

2229.md (57963B)


      1 Source: https://codeforces.com/blog/entry/153948
      2 
      3 Thank you for participating in our round! We hope you enjoyed the problems as much as we enjoyed preparing them.
      4 
      5 **Rate the contest!**
      6 
      7 **Quality**
      8 
      9 * Absolute Cinema contest
     10 * Excellent contest
     11 * Good contest
     12 * Average contest
     13 * Bad contest
     14 * Horrible contest
     15 
     16 **Difficulty**
     17 
     18 * Trivial contest
     19 * Easy contest
     20 * Average contest
     21 * Hard contest
     22 * Impossible contest
     23 
     24 [2229A - Слаймы на прямой](/contest/2229/problem/A)
     25 
     26 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
     27 
     28 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
     29 
     30 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan")
     31 
     32 **Hint 1**
     33 
     34 Let $y$ denote the final position of all of the slimes. Then it is optimal to choose $x = y$ for every operation.
     35 
     36 **Hint 2**
     37 
     38 Let $\mathrm{mn}$ denote the minimum value in $a$, and let $\mathrm{mx}$ denote the maximum value in $a$. Now, the number of operations that you need to apply is equal to $\max(y - \mathrm{mn}, \mathrm{mx} - y)$.
     39 
     40 **Solution**
     41 
     42 We want to choose the value of $y$ that minimizes $\max(y - \mathrm{mn}, \mathrm{mx} - y)$. Therefore, we will choose the value that is closest to the middle of $\mathrm{mn}$ and $\mathrm{mx}$. This yields a final answer of $\lceil \frac{\mathrm{mx} - \mathrm{mn}}{2} \rceil$.
     43 
     44 **Code**
     45 
     46 ```
     47 #include<bits/stdc++.h>
     48 using namespace std;
     49 typedef long long ll;
     50 #define debug(x) cout << #x << " = " << x << "\n";
     51 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
     52 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     53 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
     54 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
     55 
     56 void solve(){
     57     int n;
     58     cin >> n;
     59 
     60     vector<int> a(n);
     61     for (int &x : a) cin >> x;
     62 
     63     int mx = *max_element(a.begin(), a.end());
     64     int mn = *min_element(a.begin(), a.end());
     65     cout << (mx - mn + 1) / 2 << "\n";
     66 }
     67 
     68 int main(){
     69     ios::sync_with_stdio(false);
     70     cin.tie(0);
     71     
     72     int t;
     73     cin >> t;
     74     while (t--) solve();
     75 }
     76 ```
     77 
     78 **Rate the problem!**
     79 
     80 **Quality**
     81 
     82 * Excellent problem
     83 * Good problem
     84 * Average problem
     85 * Bad problem
     86 * Horrible problem
     87 
     88 **Difficulty**
     89 
     90 * Trivial problem
     91 * Easy problem
     92 * Average problem
     93 * Hard problem
     94 * Impossible problem
     95 
     96 [2229B - Это шедевр!](/contest/2229/problem/B)
     97 
     98 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
     99 
    100 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    101 
    102 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan")
    103 
    104 **Hint 1**
    105 
    106 Consider each index separately. For one of the indices, you will gain value equal to $a_i + b_i$. For all of the other indices, you will gain value equal to $b_i$ only.
    107 
    108 **Hint 2**
    109 
    110 It is never bad to put the larger value in $b_i$.
    111 
    112 **Solution**
    113 
    114 We should swap any $a_i$ where $a_i \gt b_i$, because we would prefer for the larger value to be in $b_i$. In total, we gain value equal to the maximums of each pair, plus the largest of the minimums of each pair.
    115 
    116 **Code**
    117 
    118 ```
    119 #include<bits/stdc++.h>
    120 using namespace std;
    121 typedef long long ll;
    122 #define debug(x) cout << #x << " = " << x << "\n";
    123 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    124 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    125 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    126 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    127 
    128 void solve(){
    129     int n;
    130     cin >> n;
    131 
    132     vector<int> a(n), b(n);
    133     for (int &x : a) cin >> x;
    134     for (int &x : b) cin >> x;
    135 
    136     ll sum = 0;
    137     for (int i = 0; i < n; i++)
    138         sum += max(a[i], b[i]);
    139 
    140     ll ans = 0;
    141     for (int i = 0; i < n; i++)
    142         ans = max(ans, sum + min(a[i], b[i]));
    143     
    144     cout << ans << "\n";
    145 }
    146 
    147 int main(){
    148     ios::sync_with_stdio(false);
    149     cin.tie(0);
    150     
    151     int t;
    152     cin >> t;
    153     while (t--) solve();
    154 }
    155 ```
    156 
    157 **Rate the problem!**
    158 
    159 **Quality**
    160 
    161 * Excellent problem
    162 * Good problem
    163 * Average problem
    164 * Bad problem
    165 * Horrible problem
    166 
    167 **Difficulty**
    168 
    169 * Trivial problem
    170 * Easy problem
    171 * Average problem
    172 * Hard problem
    173 * Impossible problem
    174 
    175 [2229C1 - Время переворотов (простая версия)](/contest/2229/problem/C1) [2229C2 - Время переворотов (сложная версия)](/contest/2229/problem/C2)
    176 
    177 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    178 
    179 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    180 
    181 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan")
    182 
    183 **Hint 1**
    184 
    185 Suppose you have a positive element. You can make this element negative without affecting any later elements by applying an operation onto it directly.
    186 
    187 **Solution (Easy Version)**
    188 
    189 You can make all of the elements negative. To do so, consider each index starting from $n$ to $1$. If it is currently positive, you can apply an operation on this index, turning it negative.
    190 
    191 **Hint 2**
    192 
    193 Let $\mathrm{idx}$ be the largest index you ever operate on. Then since you can never flip its sign using an operation on a later index, $a_{\mathrm{idx}}$ must initially be positive, and it will be negative after performing the operation.
    194 
    195 **Solution (Hard Version)**
    196 
    197 Read the hints. In fact, it is always possible to make all elements before $\mathrm{idx}$ positive. Thus, in the end you end up with either the original array (if you applied no operations), or an array of the form $[|a_1|, ..., |a_{\mathrm{idx}-1}|, -a_{\mathrm{idx}}, a_{\mathrm{idx}+1}, ..., a_n]$ for some $\mathrm{idx}$ where $a_{\mathrm{idx}}$ is initially positive. You can find the optimal choice of $\mathrm{idx}$ using prefix and suffix arrays.
    198 
    199 To make all of the elements before $\mathrm{idx}$ positive, you can first make them all negative by applying the method in the easy version. Then at the end, you can perform an operation on $\mathrm{idx}$, yielding the optimal array.
    200 
    201 **Code (easy version)**
    202 
    203 ```
    204 #include<bits/stdc++.h>
    205 using namespace std;
    206 typedef long long ll;
    207 #define debug(x) cout << #x << " = " << x << "\n";
    208 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    209 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    210 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    211 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    212 
    213 void solve(){
    214     int n;
    215     cin >> n;
    216 
    217     vector<int> a(n);
    218     for (int &x : a) cin >> x;
    219 
    220     int par = 0;
    221     vector<int> ans;
    222     for (int i = n - 1; i >= 0; i--){
    223         if (par == 1)
    224             a[i] = -a[i];
    225         if (a[i] > 0){
    226             ans.push_back(i);
    227             par ^= 1;
    228         }
    229     }
    230 
    231     cout << ans.size() << "\n";
    232     for (int i = 0; i < ans.size(); i++)
    233         cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
    234 }
    235 
    236 int main(){
    237     ios::sync_with_stdio(false);
    238     cin.tie(0);
    239     
    240     int t;
    241     cin >> t;
    242     while (t--) solve();
    243 }
    244 ```
    245 
    246 **Code (hard version)**
    247 
    248 ```
    249 #include<bits/stdc++.h>
    250 using namespace std;
    251 typedef long long ll;
    252 #define debug(x) cout << #x << " = " << x << "\n";
    253 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    254 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    255 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    256 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    257 
    258 void solve(){
    259     int n;
    260     cin >> n;
    261 
    262     vector<int> a(n);
    263     for (int &x : a) cin >> x;
    264 
    265     vector<ll> pre(n), suf(n + 1);
    266     pre[0] = abs(a[0]);
    267     for (int i = 1; i < n; i++)
    268         pre[i] = pre[i - 1] + abs(a[i]);
    269     
    270     suf[n - 1] = a[n - 1];
    271     for (int i = n - 2; i >= 0; i--)
    272         suf[i] = suf[i + 1] + a[i];
    273 
    274     ll best = suf[0];
    275     int idx = -1;
    276     for (int i = 1; i < n; i++){
    277         if (a[i] > 0){
    278             ll score = pre[i - 1] + suf[i + 1] - a[i];
    279             if (score > best){
    280                 best = score;
    281                 idx = i;
    282             }
    283         }
    284     }
    285 
    286     if (idx == -1){
    287         cout << "0\n";
    288         return;
    289     }
    290 
    291     vector<int> ans;
    292     for (int i = idx - 1; i >= 0; i--){
    293         if (ans.size() & 1)
    294             a[i] = -a[i];
    295         if (a[i] > 0)
    296             ans.push_back(i);
    297     }
    298     ans.push_back(idx);
    299 
    300     cout << ans.size() << "\n";
    301     for (int i = 0; i < ans.size(); i++)
    302         cout << ans[i] + 1 << " \n"[i == ans.size() - 1];
    303 }
    304 
    305 int main(){
    306     ios::sync_with_stdio(false);
    307     cin.tie(0);
    308     
    309     int t;
    310     cin >> t;
    311     while (t--) solve();
    312 }
    313 ```
    314 
    315 **Rate the problem! (easy version)**
    316 
    317 **Quality**
    318 
    319 * Excellent problem
    320 * Good problem
    321 * Average problem
    322 * Bad problem
    323 * Horrible problem
    324 
    325 **Difficulty**
    326 
    327 * Trivial problem
    328 * Easy problem
    329 * Average problem
    330 * Hard problem
    331 * Impossible problem
    332 
    333 **Rate the problem! (hard version)**
    334 
    335 **Quality**
    336 
    337 * Excellent problem
    338 * Good problem
    339 * Average problem
    340 * Bad problem
    341 * Horrible problem
    342 
    343 **Difficulty**
    344 
    345 * Trivial problem
    346 * Easy problem
    347 * Average problem
    348 * Hard problem
    349 * Impossible problem
    350 
    351 [2229D - Я, когда задача на медиану](/contest/2229/problem/D)
    352 
    353 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    354 
    355 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    356 
    357 Editorial by: [reirugan](/profile/reirugan "Кандидат в мастера reirugan")
    358 
    359 **Hint 1**
    360 
    361 Try solving the problem on a binary array; that is, all values of $a$ and $b$ are either $0$ or $1$.
    362 
    363 **Hint 2**
    364 
    365 Suppose you want to check if it is possible to achieve a final value of at least $m$. Then you can replace all smaller values with $0$, and all values at least $m$ with $1$. Now, solve the problem on the resulting binary array and check if it is possible to achieve a final value of $1$.
    366 
    367 **Hint 3**
    368 
    369 This allows you to binary search for the final answer.
    370 
    371 **Solution**
    372 
    373 Read the hints. It now suffices to solve the problem on a binary array. Let $\mathrm{diff} = \mathrm{cnt}_1 - \mathrm{cnt}_0$. Whenever you apply an operation, you lose the minimum and maximum of $S$. Therefore, the only way to change the value of $\mathrm{diff}$ is to apply an operation where the minimum and maximum of $S$ are the same; that is, all four values in $S$ are the same. If they are $0$, then $\mathrm{diff}$ increases by $2$; if they are $1$, then $\mathrm{diff}$ decreases by $2$. We want to increase $\mathrm{diff}$ as much as possible; if we can make it positive in the end, then that implies the final two values are both $1$.
    374 
    375 Consider a subarray of indices such that there are no occurrences of ${a_i, b_i} = {1, 1}$; that is, we only have either ${a_i, b_i} = {0, 0}$ or ${a_i, b_i} = {0, 1}$. Then we want to repeatedly perform operations within this subarray, because this will maximize the number of times we can increase $\mathrm{diff}$. Note that an operation using ${0, 0}$ and ${0, 1}$ will produce a ${0, 0}$, so we will never lose an opportunity to increase $\mathrm{diff}$; we can apply operations within this subarray arbitrarily. Once we have applied as many operations as possible in this subarray, we are left with one pair, which is ${0, 0}$ if the subarray started with a ${0, 0}$, or ${0, 1}$ otherwise.
    376 
    377 Now, it is impossible to increase $\mathrm{diff}$ any further. This is because any two pairs of ${0, 0}$ have a ${1, 1}$ in between. Clearly, if $\mathrm{diff}$ is nonpositive, then we have already lost. If $\mathrm{diff}$ is positive, we claim we win. Indeed, if there exists any ${0, 0}$ or ${0, 1}$, we can perform any operation with it, thus avoiding decreasing $\mathrm{diff}$. Otherwise, if all pairs are equal to ${1, 1}$, then we win trivially. This concludes the solution.
    378 
    379 **Code**
    380 
    381 ```
    382 #include<bits/stdc++.h>
    383 using namespace std;
    384 typedef long long ll;
    385 #define debug(x) cout << #x << " = " << x << "\n";
    386 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    387 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    388 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    389 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    390 
    391 void solve(){
    392     int n;
    393     cin >> n;
    394 
    395     vector<int> a(n), b(n);
    396     for (int &x : a) cin >> x;
    397     for (int &x : b) cin >> x;
    398 
    399     int l = 0, r = 1e9 + 5;
    400     while (l < r){
    401         int mid = (l + r) / 2;
    402 
    403         int one = 0, zero = 0;
    404         int prev = -1;
    405         for (int i = 0; i < n; i++){
    406             int type = 0;
    407             if (a[i] >= mid)
    408                 type++;
    409             if (b[i] >= mid)
    410                 type++;
    411 
    412             if (type == 1)
    413                 continue;
    414 
    415             if (type == 2){
    416                 one++;
    417                 prev = 1;
    418             }
    419 
    420             if (type == 0){
    421                 if (prev != 0)
    422                     zero++;
    423                 prev = 0;
    424             }
    425         }
    426 
    427         if (one > zero)
    428             l = mid + 1;
    429         else
    430             r = mid;
    431     }
    432 
    433     cout << l - 1 << "\n";
    434 }
    435 
    436 int main(){
    437     ios::sync_with_stdio(false);
    438     cin.tie(0);
    439     
    440     int t;
    441     cin >> t;
    442     while (t--) solve();
    443 }
    444 ```
    445 
    446 **Rate the problem!**
    447 
    448 **Quality**
    449 
    450 * Excellent problem
    451 * Good problem
    452 * Average problem
    453 * Bad problem
    454 * Horrible problem
    455 
    456 **Difficulty**
    457 
    458 * Trivial problem
    459 * Easy problem
    460 * Average problem
    461 * Hard problem
    462 * Impossible problem
    463 
    464 [2229E - Дерево деструкции](/contest/2229/problem/E)
    465 
    466 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    467 
    468 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    469 
    470 Editorial by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
    471 
    472 **Hint 1**
    473 
    474 $n$ will never be removed, and will always be added to $S$.
    475 
    476 **Hint 2**
    477 
    478 Try rooting at $n$.
    479 
    480 **Solution**
    481 
    482 Read the hints, through this editorial I will consider $n$ to be the root of the tree.
    483 
    484 Lets try to determine the following for each node. When we add $x$ to $S$ for the first time, what can the largest element of $S$ be before this point. Lets try to find some necessary conditions for this.
    485 
    486 * $\max(S) \lt x$, this is true because the maximum leaf is non-decreasing.
    487 * $\max(S)$ is greater than the largest element in the subtree of $x$ (excluding $x$ itself). Since $n$ can never be removed, in order for $x$ to become a leaf, we must first remove everything in its subtree. For this to happen there must be some leaf outside the subtree of $x$ which is bigger than each element of the subtree. During this process a greater element will be added to $S$.
    488 
    489 $\text{subtree}(x)$ will be used to denote the subtree of $x$ excluding $x$ itself. Remember that we rooted the tree at $n$.
    490 
    491 It turns out that these conditions are also sufficient. i.e. if $\max(\text{subtree}(x)) \lt \max(S) \lt x$, then we are able to add $x$ into $S$ without needing to include any additional elements ($S := S \cup \lbrace x \rbrace$). We can prove that this is true because if the current largest leaf is larger than $\max(\text{subtree}(x))$, then we are able to remove the entire subtree of $x$ without changing the maximum. $x$ now becomes a leaf and because $\max(S) \lt x$, $x$ will be the new maximum and added on the next turn.
    492 
    493 Thus we can solve this problem with dynamic programming where $dp_i$ is the number of ways to reach a state where $\max(S) = i$. The initial state has only the max leaf set to $1$.
    494 
    495 $dp_i$ can transition to $dp_j$ if and only if $\max(\text{subtree}(j)) \lt i \lt j$. These transitions conveniently form ranges, so we can simulate all the transitions using prefix sums in $O(n)$.
    496 
    497 It should be note that transitions to $n$ are a special case, a node $x$ can transition to $n$ if and only if we can delete all children of $n$ excluding the one with $x$ in its subtree. In other words all nodes outside the subtree that contains $x$ are smaller than it.
    498 
    499 **Code**
    500 
    501 ```
    502 #include<bits/stdc++.h>
    503 using namespace std;
    504 typedef long long ll;
    505 #define debug(x) cout << #x << " = " << x << "\n";
    506 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    507 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    508 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    509 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    510 
    511 const int MOD = 998244353;
    512 
    513 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged
    514 struct modnum {
    515     static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
    516 
    517     using S = conditional_t<is_big_mod, ll, int>;
    518     using L = conditional_t<is_big_mod, __int128, ll>;
    519 
    520     S x;
    521 
    522     modnum() : x(0) {}
    523     modnum(ll _x) {
    524         _x %= static_cast<ll>(mod);
    525         if (_x < 0) { _x += mod; }
    526         x = _x;
    527     }
    528 
    529     modnum pow(ll n) const {
    530         modnum res = 1;
    531         modnum cur = *this;
    532         while (n > 0) {
    533             if (n & 1) res *= cur;
    534             cur *= cur;
    535             n /= 2;
    536         }
    537         return res;
    538     }
    539     modnum inv() const { return (*this).pow(mod-2); }
    540     
    541     modnum& operator+=(const modnum& a){
    542         x += a.x;
    543         if (x >= mod) x -= mod;
    544         return *this;
    545     }
    546     modnum& operator-=(const modnum& a){
    547         if (x < a.x) x += mod;
    548         x -= a.x;
    549         return *this;
    550     }
    551     modnum& operator*=(const modnum& a){
    552         x = static_cast<L>(x) * a.x % mod;
    553         return *this;
    554     }
    555     modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    556     
    557     friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    558     friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    559     friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    560     friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    561     
    562     friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    563     friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    564     friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
    565 
    566     friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    567     friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
    568 };
    569 
    570 using mint = modnum<MOD>;
    571 
    572 void solve(){
    573     int n;
    574     cin >> n;
    575 
    576     vector<vector<int>> g(n);
    577     for (int i = 0; i < n - 1; i++){
    578         int u, v;
    579         cin >> u >> v;
    580         u--;
    581         v--;
    582 
    583         g[u].push_back(v);
    584         g[v].push_back(u);
    585     }
    586 
    587     if (g[n - 1].size() == 1){
    588         cout << "1\n";
    589         return;
    590     }
    591 
    592     vector<int> mx(n);
    593     auto dfs = [&](auto self, int c, int p) -> void{
    594         for (int x : g[c]){
    595             if (x == p)
    596                 continue;
    597 
    598             self(self, x, c);
    599             mx[c] = max({mx[c], x, mx[x]});
    600         }
    601     };
    602     dfs(dfs, n - 1, -1);
    603 
    604     set<int, greater<int>> s;
    605     for (int i = 0; i < n - 1; i++)
    606         s.insert(i);
    607 
    608     vector<int> cur;
    609     auto dfs2 = [&](auto self, int c, int p) -> void{
    610         s.erase(c);
    611         cur.push_back(c);
    612 
    613         for (int x : g[c]){
    614             if (x == p)
    615                 continue;
    616 
    617             self(self, x, c);
    618         }
    619     };
    620     
    621     vector<bool> ok(n); // can transition to n
    622     for (int x : g[n - 1]){
    623         dfs2(dfs2, x, n - 1);
    624 
    625         for (int u : cur){
    626             if (u > (*s.begin()))
    627                 ok[u] = true;
    628         }
    629 
    630         for (int u : cur)
    631             s.insert(u);
    632         cur.clear();
    633     }
    634     ok[n - 1] = true;
    635 
    636     int idx = -1;
    637     for (int i = 0; i < n; i++){
    638         if (g[i].size() == 1)
    639             idx = i;
    640     }
    641 
    642     vector<mint> dp(n), pre(n);
    643     dp[idx] = 1;
    644     pre[idx] = 1;
    645     for (int i = idx + 1; i < n - 1; i++){
    646         int l = mx[i] + 1;
    647 
    648         if (l < i){
    649             dp[i] = pre[i - 1];
    650             if (l > 0)
    651                 dp[i] -= pre[l - 1];
    652         }
    653 
    654         pre[i] = dp[i] + pre[i - 1];
    655     }
    656 
    657     mint ans = 0;
    658     for (int i = 0; i < n; i++){
    659         if (ok[i])
    660             ans += dp[i];
    661     }
    662 
    663     cout << ans << "\n";
    664 }
    665 
    666 int main(){
    667     ios::sync_with_stdio(false);
    668     cin.tie(0);
    669     
    670     int t;
    671     cin >> t;
    672     while (t--) solve();
    673 }
    674 ```
    675 
    676 **Rate the problem!**
    677 
    678 **Quality**
    679 
    680 * Excellent problem
    681 * Good problem
    682 * Average problem
    683 * Bad problem
    684 * Horrible problem
    685 
    686 **Difficulty**
    687 
    688 * Trivial problem
    689 * Easy problem
    690 * Average problem
    691 * Hard problem
    692 * Impossible problem
    693 
    694 [2229F - Дисбаланс нагрузки](/contest/2229/problem/F)
    695 
    696 Idea by: [myst-6](/profile/myst-6 "Мастер myst-6")
    697 
    698 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
    699 
    700 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
    701 
    702 **Hint 1**
    703 
    704 Which element of $a$ is it optimal to use last?
    705 
    706 **Hint 2**
    707 
    708 Suppose you know which element you're placing last. Now what does the problem reduce to?
    709 
    710 **Hint 3**
    711 
    712 Binary search is your friend.
    713 
    714 **Solution**
    715 
    716 We will prove that it's optimal to place the maximum value of $a$ last in the array. After we've done that, the problem now becomes maximising the minimum value of $b$ after rearranging the rest of the values in $a$.
    717 
    718 To maximise the minimum value of $b$, we can binary search it. To check whether it's $\le v$, we can do a bitmask DP which finds the maximum number of disjoint subsets of $a$ whose sum is $\ge v$, and check whether we have at least $k$ of them. There exists a simple greedy algorithm, once we have these subsets, to construct an ordering which gets us the value of v: we assign each subset to a position in array $b$, and simulate the process; whenever an index is chosen to be added to, we choose the highest remaining number from the corresponding subset.
    719 
    720 We can make the bitmask dp in the form dp[mask] = maximum {number of groups, leftover}. There are $O(n)$ transitions from each mask (adding each possible extra element to the mask), so it runs in $O(2^n \cdot n)$. Since the difference between min and max in $b$ is at most $max(a)$, we can find an upper and lower bound for the binary search which are A apart, so time complexity ends up being $O(n \cdot 2^n \cdot log(A))$.
    721 
    722 We can use this greedy algorithm to prove that $max(a)$ can always be placed last (let's call it $x$). Suppose we have an optimal rearrangement with $x$ not being last, and let's consider the set of values which go in each position in array $b$. Consider the last item added to the maximum pile (let's call it $y$) and the pile where $x$ was added. If we remove $y$ from its pile, its pile is now $min(b)$. If we remove $x$ from its pile and add $y$ to it, there are two cases: 1. $y$'s original pile is still the min. Greedily construct this min and add $x$ last, and $pile = ans - y + x \ge ans$ so it's a maximal construction. 2. $x$'s original pile is now the min. Greedily construct this min and add $x$ last, and $pile \ge ans - y - x + y + x = ans$ so it's a maximal construction.
    723 
    724 **Code**
    725 
    726 ```
    727 #include <bits/stdc++.h>
    728 using namespace std;
    729 
    730 typedef long long ll;
    731 #define all(x) x.begin(), x.end()
    732 #define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _;
    733 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
    734 
    735 void solve() {
    736     int n, k; cin >> n >> k;
    737     vecin(aa, n); sort(all(aa));
    738     n --;
    739     ll extra = aa.back(); aa.pop_back();
    740 
    741     ll L = 0, R = extra * (ll)n;
    742     while (L != R) {
    743         ll mid = (L + R + 1) / 2;
    744         vector<pair<int, ll>> dp(1 << n, {0, 0});
    745         for (int i = 1; i < (1 << n); i ++) {
    746             for (int j = 0; (1 << j) <= i; j ++) {
    747                 if (!(i & (1 << j))) continue;
    748                 int res = i ^ (1 << j);
    749                 pair<int, ll> cur = dp[res];
    750                 cur.second += aa[j];
    751                 if (cur.second >= mid)
    752                     cur = {cur.first + 1, 0};
    753                 dp[i] = max(dp[i], cur);
    754             }
    755         }
    756         if (dp[(1 << n) - 1].first >= k)
    757             L = mid;
    758         else
    759             R = mid - 1;
    760     }
    761     cout << L + extra << endl;
    762 }
    763 
    764 int main() {
    765 	ios_base::sync_with_stdio(false);
    766     cin.tie(NULL);
    767     int tt = 1;
    768 
    769     cin >> tt;
    770 
    771     while (tt--) solve();
    772     return 0;
    773 }
    774 ```
    775 
    776 **Rate the problem!**
    777 
    778 **Quality**
    779 
    780 * Excellent problem
    781 * Good problem
    782 * Average problem
    783 * Bad problem
    784 * Horrible problem
    785 
    786 **Difficulty**
    787 
    788 * Trivial problem
    789 * Easy problem
    790 * Average problem
    791 * Hard problem
    792 * Impossible problem
    793 
    794 [2229G - Дорожные работы](/contest/2229/problem/G)
    795 
    796 Idea by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
    797 
    798 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
    799 
    800 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
    801 
    802 Special thanks to [Geothermal](/profile/Geothermal "Легендарный гроссмейстер Geothermal") for the absolute cinema solution!
    803 
    804 **Hint 1**
    805 
    806 When is it optimal to stay at a house for more than $1$ day?
    807 
    808 **Hint 2**
    809 
    810 Suppose you are staying at a house for more than $1$ day. When should you arrive at that house?
    811 
    812 **Hint 3**
    813 
    814 Suppose you are staying at a house for more than $1$ day. Which houses could you previously have come from?
    815 
    816 **Main Ideas**
    817 
    818 First, observe that any house you stay at for longer than $1$ day should be a prefix maximum on the path from house $x$, otherwise it's at least as good to stay on the previous house with greater $h_i$ on the path from house $x$.
    819 
    820 Also, if you are going to stay at a house for longer than $1$ day, it is optimal to reach it as early as possible. Assume you stay at it for longer than 1 day but also don't reach it as early as possible: if the previous house you stayed at for longer than $1$ day had greater or equal hospitality you could have stayed there instead for an extra day and it would not be worse, and if it had lower hospitality you should have reached the new house earlier.
    821 
    822 Finally, if you are going to switch directions in an optimal solution, you should go all the way past house $x$ before switching directions again. This is because if you switch directions at a house that is not a prefix maximum, it would have been better to just stay at the last prefix maximum for longer; and if you switch directions at a prefix maximum, but don't immediately go all the way past $x$, you should have stayed at that prefix maximum for longer.
    823 
    824 **Solution (Boring)**
    825 
    826 We can maintain for each house the maximum possible satisfaction we can achieve if we reach it as early as possible. We know that for each house, the optimal answer if we finish on that house at time $y$ depends only on the house with the next largest $h_i$ on the path to $x$, and the maximum answer for having previously stayed on the other side of $x$ then gone straight to that house.
    827 
    828 For the former case, we can maintain which house is the prefix maximum on both sides, and for the latter case, we can use convex hull trick or LCT to keep track of the best satisfaction if we arrive on house $x$ at exactly time $y$ from either side. We use two pointers for the leftmost and rightmost currently reachable houses and update whenever a new prefix maximum becomes reachable. We also need prefix sums to track the increase in satisfaction of any houses we pass on the path to the next prefix maximum. You also need to be careful to not immediately insert a new house into the CHT/LCT, but only as soon as the next prefix maximum on the other side can actually reach it. The implementation is a bit horrible and the time complexity is $O(n log n)$, although it can also be implemented in $O(n)$.
    829 
    830 **Hint 4**
    831 
    832 Suppose you are staying at a house for more than $1$ day. Which houses could you go to next?
    833 
    834 **Solution (Absolute Cinema)**
    835 
    836 The boring solution uses a "pull DP". What if instead we used a "push DP"? In fact, we can show that whenever you reach a prefix maximum, the next house you will move to is either the next higher prefix maximum on that side of $x$, or the next highest prefix maximum on the other side of $x$. So we can precalculate both those things using a monotonic stack, and perform the transitions to both those houses (if they exist), assuming we reach them as early as possible. This is easy to implement in $O(n)$.
    837 
    838  ![](/predownloaded/46/0c/460cfd5e3d79792180add755cf4f3f21ae96201d.png)
    839 
    840 **Code (Boring Solution)**
    841 
    842 ```
    843 #include <bits/stdc++.h>
    844 using namespace std;
    845 
    846 typedef long long ll;
    847 #define all(x) x.begin(), x.end()
    848 #define vecin(name, len) vector<ll> name(len); for (auto &_ : name) cin >> _;
    849 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
    850 
    851 struct Line {
    852 	mutable ll k, m, p;
    853 	bool operator<(const Line& o) const { return k < o.k; }
    854 	bool operator<(ll x) const { return p < x; }
    855     ll eval(ll x) { return k * x + m; }
    856 };
    857 
    858 struct LineContainer : multiset<Line, less<>> {
    859 	static const ll inf = LLONG_MAX;
    860 	ll div(ll a, ll b) {
    861 		return a / b - ((a ^ b) < 0 && a % b); }
    862 	bool isect(iterator x, iterator y) {
    863 		if (y == end()) return x->p = inf, 0;
    864 		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    865 		else x->p = div(y->m - x->m, x->k - y->k);
    866 		return x->p >= y->p;
    867 	}
    868 	void add(ll k, ll m) {
    869 		auto z = insert({k, m, 0}), y = z++, x = y;
    870 		while (isect(y, z)) z = erase(z);
    871 		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    872 		while ((y = x) != begin() && (--x)->p >= y->p)
    873 			isect(x, erase(y));
    874 	}
    875 	ll query(ll x) {
    876 		assert(!empty());
    877 		auto l = *lower_bound(x);
    878 		return l.eval(x);
    879 	}
    880 };
    881 
    882 vector<ll> h;
    883 vector<ll> pref;
    884 
    885 ll range_sum(int L, int R) {
    886     return pref[R + 1] - pref[L];
    887 }
    888 
    889 void solve() {
    890     int n, t, x; cin >> n >> t >> x;
    891     x --;
    892     h.resize(n); pref.resize(n + 1);
    893     pref[0] = 0;
    894     for (int i = 0; i < n; i ++) {
    895         cin >> h[i];
    896         pref[i + 1] = pref[i] + h[i];
    897     }
    898     vecin(d, n - 1);
    899     for (int i = x - 2; i >= 0; i --) {
    900         d[i] = max(d[i], d[i + 1] + 1);
    901     }
    902     for (int i = x; i < n - 2; i ++) {
    903         d[i + 1] = max(d[i + 1], d[i] + 1);
    904     }
    905 
    906     ll ans = h[x] * t;
    907     int L = x, R = x;
    908     Line curleft = {h[x], 0, 0}, curright = {h[x], 0, 0};
    909     int left_best = x, right_best = x;
    910     LineContainer left, right;
    911     left.add(h[x], 0); right.add(h[x], 0);
    912     queue<pair<int, pair<ll, ll>>> add_left, add_right;
    913     while (L > 0 || R < n - 1) {
    914         int left_time = (L == 0) ? 2e9 : d[L - 1];
    915         int right_time = (R == n - 1) ? 2e9 : d[R];
    916         if (min(left_time, right_time) > t) break;
    917         if (left_time <= right_time) {
    918             L --;
    919             if (h[L] > curleft.k) {
    920                 // best = max sum on day left_time-1 on house L+1
    921                 int pref_dist = left_best - L;
    922                 int start_dist = x - L;
    923                 while (add_right.size() && add_right.front().first <= left_time - start_dist) {
    924                     right.add(add_right.front().second.first, add_right.front().second.second);
    925                     add_right.pop();
    926                 }
    927                 ll best = max(
    928                     curleft.eval(left_time - pref_dist) + range_sum(L + 1, left_best - 1),
    929                     right.query(left_time - start_dist) + range_sum(L + 1, x - 1)
    930                 );
    931                 // cout << L << " " << h[L] << " " << best << endl;
    932                 ans = max(ans, best + (t - left_time + 1) * h[L]);
    933                 left_best = L;
    934                 curleft = {h[L], best - (left_time - 1) * h[L], 0};
    935                 add_left.push({left_time + start_dist, {h[L], best - (left_time - 1 + start_dist) * h[L] + range_sum(L + 1, x)}});
    936             }
    937         } else {
    938             R ++;
    939             if (h[R] > curright.k) {
    940                 // best = max sum on day right_time-1 on house R-1
    941                 int pref_dist = R - right_best;
    942                 int start_dist = R - x;
    943                 while (add_left.size() && add_left.front().first <= right_time - start_dist) {
    944                     left.add(add_left.front().second.first, add_left.front().second.second);
    945                     add_left.pop();
    946                 }
    947                 ll best = max(
    948                     curright.eval(right_time - pref_dist) + range_sum(right_best + 1, R - 1),
    949                     left.query(right_time - start_dist) + range_sum(x + 1, R - 1)
    950                 );
    951                 // cout << R << " " << h[R] << " " << best << endl;
    952                 ans = max(ans, best + (t - right_time + 1) * h[R]);
    953                 right_best = R;
    954                 curright = {h[R], best - (right_time - 1) * h[R], 0};
    955                 add_right.push({right_time + start_dist, {h[R], best - (right_time - 1 + start_dist) * h[R] + range_sum(x, R - 1)}});
    956             }
    957         }
    958     }
    959     cout << ans << endl;
    960 }
    961 
    962 int main() {
    963 	ios_base::sync_with_stdio(false);
    964     cin.tie(NULL);
    965     int tt = 1;
    966 
    967     cin >> tt;
    968 
    969     while (tt--) solve();
    970     return 0;
    971 }
    972 ```
    973 
    974 **Code (Absolute Cinema Solution)**
    975 
    976 ```
    977 #include <bits/stdc++.h>
    978  
    979 using namespace std;
    980  
    981 using ll = long long;
    982 using vi = vector<int>;
    983 using vl = vector<ll>;
    984 using pl = pair<ll, ll>;
    985 template <class T>
    986 using vc = vector<T>;
    987  
    988 template <class T>
    989 constexpr T infty = 0;
    990 template <>
    991 constexpr ll infty<ll> = 2'020'000'000'000'000'000;
    992  
    993 #define FOR2(i, a) for (int i = 0; i < int(a); ++i)
    994 #define FOR3(i, a, b) for (int i = int(a); i < int(b); ++i)
    995 #define FOR2_R(i, a) for (int i = int(a) - 1; i >= 0; --i)
    996 #define overload4(a, b, c, d, e, ...) e
    997 #define overload3(a, b, c, d, ...) d
    998 #define FOR(...) overload4(__VA_ARGS__, _4, FOR3, FOR2, _1)(__VA_ARGS__)
    999 #define FOR_R(...) overload3(__VA_ARGS__, _3, FOR2_R, _1)(__VA_ARGS__)
   1000  
   1001 #define all(x) (x).begin(), (x).end()
   1002 #define trav(a, x) for (auto& a : x)
   1003 #define eb emplace_back
   1004 #define mp make_pair
   1005 #define fi first
   1006 #define se second
   1007  
   1008 template <class T, class S>
   1009 inline bool chmax(T &a, const S &b) {
   1010     T c = max<T>(a, b);
   1011     bool changed = (c != a);
   1012     a = c;
   1013     return changed;
   1014 }
   1015  
   1016 template <class T>
   1017 void rd(T &x) { cin >> x; }
   1018  
   1019 template <class T>
   1020 void rd(vc<T> &x) { for (auto &d : x) rd(d); }
   1021  
   1022 void read() {}
   1023 template <class H, class... T>
   1024 void read(H &h, T &...t) { rd(h), read(t...); }
   1025  
   1026 void print() { cout << '\n'; }
   1027 template <class Head, class... Tail>
   1028 void print(Head &&head, Tail &&...tail) {
   1029     cout << head;
   1030     if (sizeof...(Tail)) cout << ' ';
   1031     print(forward<Tail>(tail)...);
   1032 }
   1033  
   1034 #define INT(...)   int __VA_ARGS__; read(__VA_ARGS__)
   1035 #define LL(...)    ll __VA_ARGS__; read(__VA_ARGS__)
   1036 #define VEC(type, name, size) vector<type> name(size); read(name)
   1037  
   1038 
   1039 void solve() {
   1040     INT(N); LL(tot); INT(X);
   1041     X--;
   1042     VEC(ll, A, N);
   1043     VEC(ll, D, N-1);
   1044     vl T(N);
   1045     T[X] = 1;
   1046     FOR(i, X, N-1) {
   1047         T[i+1] = max(T[i]+1, D[i]);
   1048         if (i == X && D[i] == 1) T[i+1] = 1;
   1049     }
   1050     FOR_R(i, X) {
   1051         T[i] = max(T[i+1]+1, D[i]);
   1052         if (i == X-1 && D[i] == 1) T[i] = 1;
   1053     }
   1054     vi nh(N), lh(N);
   1055     vc<pl> stk;
   1056     stk.eb(mp(N, 2e9));
   1057     FOR_R(i, N) {
   1058         while (stk.back().se <= A[i]) stk.pop_back();
   1059         nh[i] = stk.back().fi;
   1060         stk.eb(mp(i, A[i]));
   1061     }
   1062     stk.clear();
   1063     stk.eb(mp(-1, 2e9));
   1064     FOR(i, N) {
   1065         while (stk.back().se <= A[i]) stk.pop_back();
   1066         lh[i] = stk.back().fi;
   1067         stk.eb(mp(i, A[i]));
   1068     }
   1069  
   1070     ll dp[N];
   1071     FOR(i, N) {
   1072         dp[i] = -infty<ll>;
   1073     }
   1074     FOR(i, N) dp[i] = 0;
   1075     vc<pl> vals; FOR(i, N) vals.eb(mp(T[i], i));
   1076     sort(all(vals));
   1077     ll ans = 0;
   1078     vl ps; ps.eb(0);
   1079     FOR(i, N) ps.eb(ps.back()+A[i]);
   1080     trav(xx, vals) {
   1081         int i = xx.se;
   1082         if (dp[i] < 0) continue;
   1083         chmax(ans, (tot - T[i] + 1) * A[i] + dp[i]);
   1084         vi ops = {nh[i], lh[i]};
   1085         trav(j, ops) {
   1086             if (j < 0 || j >= N) continue;
   1087             if (abs(j-i) > T[j] - T[i]) {
   1088                 continue;
   1089             }
   1090             chmax(dp[j], dp[i] + (T[j] - T[i] - abs(j-i) + 1) * A[i] + ps[max(i, j)] - ps[min(i, j) + 1]);
   1091         }
   1092     }
   1093  
   1094     print(ans);
   1095 }
   1096  
   1097 signed main() {
   1098     ios::sync_with_stdio(false);
   1099     cin.tie(nullptr);
   1100     INT(T);
   1101     FOR(t, T) {
   1102         solve();
   1103     }
   1104     return 0;
   1105 }
   1106 ```
   1107 
   1108 **Rate the problem!**
   1109 
   1110 **Quality**
   1111 
   1112 * Excellent problem
   1113 * Good problem
   1114 * Average problem
   1115 * Bad problem
   1116 * Horrible problem
   1117 
   1118 **Difficulty**
   1119 
   1120 * Trivial problem
   1121 * Easy problem
   1122 * Average problem
   1123 * Hard problem
   1124 * Impossible problem
   1125 
   1126 [2229H - Ух ты, бинарная строка](/contest/2229/problem/H)
   1127 
   1128 Idea by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
   1129 
   1130 Prepared by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
   1131 
   1132 Editorial by: [Intellegent](/profile/Intellegent "Гроссмейстер Intellegent")
   1133 
   1134 **Hint 1**
   1135 
   1136 Imagine the string has no $\mathtt{?}$ characters, try to find a greedy which can check if a string $t$ can be generated from $s$ by applying the operation.
   1137 
   1138 **Hint 2**
   1139 
   1140 Try to generalise this greedy for when there are $\mathtt{?}$ characters.
   1141 
   1142 **Solution**
   1143 
   1144 Read the hints. A correct greedy for the no $\mathtt{?}$ character version is perhaps the simplest one you can try, which is as follows:
   1145 
   1146 We would like to find a subsequence of $s$ which is equal to $t$, where each substring between consecutive characters contains an even number of $\mathtt{1}$. We can find this by iterating through the characters of $t$. For each character find the first character in $s$ where $s_j = t_i$ and the substring between $s_j$ and the previously chosen character contains an even number of $\mathtt{1}$.
   1147 
   1148 We can prove correctness by contradiction. Say we have a matching where at some point we didn't chose the earliest match, say between $t_i$ and $t_{i + 1}$ (we matched with a later position for $t_{i + 1}$). We can adjust our matching to instead take the earliest position for $t_{i + 1}$, call this earliest position $x$. Since we know the substring from $t_i$ to $x$ is removable and the substring from $t_i$ to $t_{i + 1}$ is removable, we can deduce that the substring from $x$ to $t_{i + 1}$ is removable. Because $t_{i + 1}$ to $t_{i + 2}$ is removeable and $x$ to $t_{i + 1}$ is removable, we can deduce that $x$ to $t_{i + 2}$ will also be removable. Thus matching the earliest option is always optimal.
   1149 
   1150 Now lets try to generalise this when there are $\mathtt{?}$ characters. Naïvely using the same greedy does not work, consider a case like $s = \mathtt{?10000000}$, $t = \mathtt{10000000}$. If we match the first $\mathtt{1}$ with the $\mathtt{?}$ we get stuck, instead we should set the $\mathtt{?}$ to $\mathtt{0}$ and match with the $\mathtt{1}$.
   1151 
   1152 Let's analyse why we fail this counter case. It fails because we incorrectly assign the value of a $\mathtt{?}$, and in general this will always be why the greedy fails, since we already know this approach would be correct after replacing all $\mathtt{?}$. When we encounter a $\mathtt{?}$ during the greedy, our choice of replacement determines the parity of the count of $\mathtt{1}$ in the current suffix. If chose incorrectly we get "locked" on the incorrect parity and are forced to consume suboptimally.
   1153 
   1154 To fix this problem, we can adjust our greedy to consider both parities at the same time. Instead of considering only the earliest match, we consider the earliest match for each parity. For each character $t_i$, we will compute the pair $(\text{best}_0, \text{best}_1)$, where $\text{best}_0$ is the earliest match with an even count of $1$ in the suffix and $\text{best}_1$ is the earliest match with an odd count of $1$ in the suffix (note that each $\mathtt{?}$ does not contribute to the suffix parity). When we transition we only need to consider the $4$ combinations of new parity and old parity. Now the entire string will be generatable if and only if the substring $s_{best_i + 1},s_{best_i + 2},\ldots,s_n$ is removable for at least one element of the final pair.
   1155 
   1156 The proof for this greedy is similar to the naïve greedy in the no $\mathtt{?}$ version. However this time we prove that for any step, if we fix the parity of the new suffix, then taking the earliest choice is always optimal. And now since we always consider both suffix parities, we will always find a matching if one exists.
   1157 
   1158 Now for counting, we can run dynamic programming on this greedy. Where $dp_{i, j}$ is the number of strings with ending greedy pair $(i, j)$, for transitions we only need to try appending $\mathtt{0}$ and $\mathtt{1}$ to the string. To fit the time limit of the problem, we need to be able to find transitions in $O(1)$. Because the problem allows $O(n^2)$ anyway, we can pre-calculate the earliest even and odd match for each position. This allows us to calculate the transitions for pairs in $O(1)$.
   1159 
   1160 Thus, the final time complexity is $O(n^2)$.
   1161 
   1162 **Code**
   1163 
   1164 ```
   1165 #include<bits/stdc++.h>
   1166 using namespace std;
   1167 typedef long long ll;
   1168 #define debug(x) cout << #x << " = " << x << "\n";
   1169 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
   1170 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
   1171 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
   1172 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
   1173 
   1174 const int MOD = 998244353;
   1175 
   1176 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged
   1177 struct modnum {
   1178     static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
   1179 
   1180     using S = conditional_t<is_big_mod, ll, int>;
   1181     using L = conditional_t<is_big_mod, __int128, ll>;
   1182 
   1183     S x;
   1184 
   1185     modnum() : x(0) {}
   1186     modnum(ll _x) {
   1187         _x %= static_cast<ll>(mod);
   1188         if (_x < 0) { _x += mod; }
   1189         x = _x;
   1190     }
   1191 
   1192     modnum pow(ll n) const {
   1193         modnum res = 1;
   1194         modnum cur = *this;
   1195         while (n > 0) {
   1196             if (n & 1) res *= cur;
   1197             cur *= cur;
   1198             n /= 2;
   1199         }
   1200         return res;
   1201     }
   1202     modnum inv() const { return (*this).pow(mod-2); }
   1203     
   1204     modnum& operator+=(const modnum& a){
   1205         x += a.x;
   1206         if (x >= mod) x -= mod;
   1207         return *this;
   1208     }
   1209     modnum& operator-=(const modnum& a){
   1210         if (x < a.x) x += mod;
   1211         x -= a.x;
   1212         return *this;
   1213     }
   1214     modnum& operator*=(const modnum& a){
   1215         x = static_cast<L>(x) * a.x % mod;
   1216         return *this;
   1217     }
   1218     modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
   1219     
   1220     friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
   1221     friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
   1222     friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
   1223     friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
   1224     
   1225     friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
   1226     friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
   1227     friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
   1228 
   1229     friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
   1230     friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
   1231 };
   1232 
   1233 using mint = modnum<MOD>;
   1234 
   1235 void solve(){
   1236     int n;
   1237     cin >> n;
   1238 
   1239     string s;
   1240     cin >> s;
   1241 
   1242     s = '0' + s;
   1243     n++;
   1244 
   1245     vector<int> pre(n);
   1246     pre[0] = s[0] == '1';
   1247     for (int i = 1; i < n; i++){
   1248         pre[i] = pre[i - 1] + (s[i] == '1');
   1249     }
   1250 
   1251     vector<array<array<int, 2>, 2>> to(n + 1);
   1252     for (int i = 0; i <= n; i++){
   1253         to[i][0][0] = n;
   1254         to[i][0][1] = n;
   1255         to[i][1][0] = n;
   1256         to[i][1][1] = n;
   1257 
   1258         int cnt = 0;
   1259         bool wowee = false;
   1260         for (int j = i + 1; j < n; j++){
   1261             if ((cnt & 1) && !wowee){
   1262                 if (s[j] == '1')
   1263                     cnt++;
   1264                 if (s[j] == '?')
   1265                     wowee = true;
   1266                 continue;
   1267             }
   1268             
   1269             if (s[j] == '1')
   1270                 cnt++;
   1271             if (s[j] == '?')
   1272                 wowee = true;
   1273 
   1274             int par = pre[j] & 1;
   1275             if (s[j] == '?'){
   1276                 to[i][0][par] = min(to[i][0][par], j);
   1277                 to[i][1][par] = min(to[i][1][par], j);
   1278                 continue;
   1279             }
   1280 
   1281             int omg = s[j] - '0';
   1282             to[i][omg][par] = min(to[i][omg][par], j);
   1283         }
   1284     }
   1285 
   1286     vector<bool> good(n + 1);
   1287     int cnt = 0;
   1288     int wowee = false;
   1289     for (int i = n - 1; i >= 0; i--){
   1290         good[i] = (cnt % 2 == 0) || wowee;
   1291         if (s[i] == '1')
   1292             cnt++;
   1293         if (s[i] == '?')
   1294             wowee = true;
   1295     }
   1296 
   1297     mint ans = 0;
   1298     vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
   1299     dp[0][n] = 1;
   1300 
   1301     vector<array<int, 2>> ord;
   1302     for (int i = 0; i <= n; i++){
   1303         for (int j = i; j <= n; j++){
   1304             ord.push_back({i, j});
   1305             if (j != i)
   1306                 ord.push_back({j, i});
   1307         }
   1308     }
   1309 
   1310     for (auto [i, j] : ord){
   1311         for (int nxt = 0; nxt < 2; nxt++){
   1312             int even = min(to[i][nxt][0], to[j][nxt][0]);
   1313             int odd = min(to[i][nxt][1], to[j][nxt][1]);
   1314             dp[even][odd] += dp[i][j];
   1315         }
   1316 
   1317         if (good[i] || good[j])
   1318             ans += dp[i][j];
   1319     }
   1320 
   1321     cout << ans << "\n";
   1322 }
   1323 
   1324 int main(){
   1325     ios::sync_with_stdio(false);
   1326     cin.tie(0);
   1327     
   1328     int t;
   1329     cin >> t;
   1330     while (t--) solve();
   1331 }
   1332 ```
   1333 
   1334 **Rate the problem!**
   1335 
   1336 **Quality**
   1337 
   1338 * Excellent problem
   1339 * Good problem
   1340 * Average problem
   1341 * Bad problem
   1342 * Horrible problem
   1343 
   1344 **Difficulty**
   1345 
   1346 * Trivial problem
   1347 * Easy problem
   1348 * Average problem
   1349 * Hard problem
   1350 * Impossible problem
   1351 
   1352 [2229I - Концы](/contest/2229/problem/I)
   1353 
   1354 Idea by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
   1355 
   1356 Prepared by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
   1357 
   1358 Editorial by: [sammyuri](/profile/sammyuri "Международный гроссмейстер sammyuri")
   1359 
   1360 Special thanks to [p0tato](/profile/p0tato "Международный гроссмейстер p0tato") for the absolute cinema solution!
   1361 
   1362 **Hint -1**
   1363 
   1364 It's not convex, monotone, monge, FFT, centroid, or any other fancy trick like that. The solution is simpler than you might expect.
   1365 
   1366 **Hint 0**
   1367 
   1368 Reformulate the formula for score so that it's in terms of nodes in the subtree from root, not the path to the root.
   1369 
   1370 **Hint 1**
   1371 
   1372 Suppose you wanted to solve for a single root in $O(n^2)$. How would you do it?
   1373 
   1374 **Answer**
   1375 
   1376 Trick 7 from <https://codeforces.com/blog/entry/100910> is your friend.
   1377 
   1378 **Hint 2**
   1379 
   1380 Why is naive rerooting $O(n^3)$ on a tree like this?
   1381 
   1382  ![](/predownloaded/21/dc/21dc02589944b6b5767222f5e3697f311a2c16a1.png)
   1383 
   1384 **Hint 3**
   1385 
   1386 How many DP values do you compute for the node labelled X? How many do you actually care about?
   1387 
   1388 **Hint 4**
   1389 
   1390 In general, how many DP values do you actually care about for a node?
   1391 
   1392 **Main Idea**
   1393 
   1394 Let:
   1395 
   1396 * $dp_1[i][j]$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $i$, assuming the selected root is $i$ or an ancestor of $i$, which uses exactly $j$ nodes.
   1397 * $dp_2[i][j]$ be the maximum score of a subset of nodes \textbf{in} the subtree of node $i$ assuming the selected root is $i$ or an ancestor of $i$, which uses exactly $j$ nodes, and does not have node $i$ selected.
   1398 * $dp_3[i][j]$ be the maximum score of a subset of nodes \textbf{outside} the subtree of node $i$, assuming the selected root is $i$ or in its subtree, which uses exactly $j$ nodes.
   1399 
   1400 We can compute $dp_1$ and $dp_2$ using Trick 7 in $O(n^2)$. The tricky part is $dp_3$. The critical observation is that for each node $i$ with a subtree size of $sz(i)$, we only care about the $sz(i)$ largest values of $dp_3[i]$, that is: $dp_3[i][k - sz(i)], dp_3[i][k - sz(i) + 1], \ldots, dp3_[i][k - 1]$. This is because if we select fewer than $k - sz(i)$ nodes outside of the subtree of $i$, then we have selected fewer than $k$ nodes overall and the solution is not optimal. There are now two ways to continue.
   1401 
   1402 **Solution (Boring)**
   1403 
   1404 Let us compute $dp_3$ in a way similar to Trick 7. Initially we have $dp_3[0][j] = 0$ for all $j$ (since the root has no parents).
   1405 
   1406 Suppose we are at a node $u$ with children $c_1, c_2, \ldots, c_m$ and we have already computed $dp_3[u]$. Let $pref[i][j]$ be the max score we can achieve by selecting $j$ nodes out of the subtrees of $c_1, \ldots, c_i$. And let $suf[i][j]$ be the max score we can achieve by selecting $j$ nodes out of the subtrees of $c_i, \ldots, c_m$ and nodes outside of the subtree of $u$. Then for each child we obtain the largest $sz(c_i0$ values of $dp_3[c_i]$ by merging $pref[i - 1]$ and $suf[i + 1]$.
   1407 
   1408 Observe that we only need to compute $\Sigma_{j\le i}sz(c_i)$ values of $pref[i]$, and $\Sigma_{j\ge i}sz(c_i)$ values of $suf[i]$. So by the same argument as Trick 7 running in $O(n^2)$, this DP also runs in $O(n^2)$.
   1409 
   1410 All that remains is to add the contribution of node $u$ to each of its child values with $dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$. Then the answer for each root is $max(dp_2[x][j] + dp_3[x][k - 1 - j] + k \cdot w[i])$.
   1411 
   1412 **Solution (Absolute Cinema)**
   1413 
   1414 Suppose the tree is a binary tree. Then, for a node $u$ with children $c_1, c_2$, we can just naively merge $dp_1[c_2]$ and $dp_3[u]$ to get $dp_3[c_1]$, and merge $dp_1[c_1]$ and $dp_3[u]$ to get $dp_3[c_2]$ (then add the contribution of $u$ with $dp_3[c_i][j] = max(dp_3[c_i][j], dp_3[c_i][j - 1] + j \cdot w_u)$). And this magically runs in $O(n^2)$, because both the convolutions run in $sz(c_1) \cdot sz(c_2)$, and the sum across all nodes of $sz(c_1) \cdot sz(c_2)$ exactly corresponds to each pair of nodes once.
   1415 
   1416 What if the tree is not a binary tree? We can make it one! If a node $u$ has $m$ children, add $m-3$ dummy nodes $d_1, d_2, \ldots, d_{m-3}$ in a chain and connect the children to them like this:
   1417 
   1418  ![](/predownloaded/8b/16/8b16c4fb6de9cae03c6f9dbaefaf197545ea256e.png)
   1419 
   1420 The only thing to watch out for is that the contribution of the original node $u$ must be done for each original child, not for the dummy nodes. The number of nodes is still $O(n)$ so it runs in $O(n^2)$.
   1421 
   1422  ![](/predownloaded/46/0c/460cfd5e3d79792180add755cf4f3f21ae96201d.png)
   1423 
   1424 **Code (Boring Solution)**
   1425 
   1426 ```
   1427 #include <bits/stdc++.h>
   1428 using namespace std;
   1429 
   1430 typedef long long ll;
   1431 #define all(x) x.begin(), x.end()
   1432 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
   1433 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
   1434 
   1435 const int MAXN = 4005;
   1436 
   1437 ll dp_down[MAXN][MAXN], dp_down_take[MAXN][MAXN], dp_up[MAXN][MAXN];
   1438 ll pref_merge[MAXN][MAXN], suff_merge[MAXN][MAXN];
   1439 vector<int> adj[MAXN];
   1440 vector<int> children[MAXN];
   1441 ll weight[MAXN];
   1442 int sz[MAXN];
   1443 int n, k;
   1444 
   1445 void dfs1(int node, int parent) {
   1446     sz[node] = 1;
   1447     for (auto a : adj[node])
   1448         if (a != parent) {
   1449             children[node].push_back(a);
   1450             dfs1(a, node);
   1451             for (int i = min(sz[node] - 1, k); i >= 0; i --)
   1452                 for (int j = 1; j <= sz[a] && i + j <= k; j ++)
   1453                     dp_down[node][i + j] = max(dp_down[node][i + j], dp_down[node][i] + dp_down_take[a][j]);
   1454             sz[node] += sz[a];
   1455         }
   1456     for (int i = min(k, sz[node]); i > 0; i --)
   1457         dp_down_take[node][i] = max(dp_down[node][i], dp_down[node][i - 1] + (ll)i * weight[node]);
   1458 }
   1459 
   1460 void dfs2(int node) {
   1461     int deg = children[node].size();
   1462     if (deg == 1) {
   1463         for (int i = 0; i <= k; i ++)
   1464             dp_up[children[node][0]][i] = dp_up[node][i];
   1465     } else if (deg >= 2) {
   1466         int p = sz[children[node][0]];
   1467         for (int i = 0; i <= k; i ++)
   1468             pref_merge[0][i] = dp_down_take[children[node][0]][i],
   1469             suff_merge[deg][i] = dp_up[node][i];
   1470         for (int c = 1; c < deg; c ++) {
   1471             for (int i = 0; i <= k; i ++)
   1472                 pref_merge[c][i] = 0;
   1473             int child = children[node][c];
   1474             p += sz[child];
   1475             for (int i = min(k, p); i >= 0; i --)
   1476                 for (int j = min(i, sz[child]); j >= 0 && i - j <= p - sz[child]; j --)
   1477                     pref_merge[c][i] = max(pref_merge[c][i], pref_merge[c - 1][i - j] + dp_down_take[child][j]);
   1478         }
   1479         for (int c = deg - 1; c >= 0; c --) {
   1480             for (int i = 0; i <= k; i ++)
   1481                 suff_merge[c][i] = 0;
   1482             int child = children[node][c];
   1483             p -= sz[child];
   1484             for (int i = k; i >= max(0, k - p - 1); i --)
   1485                 for (int j = min(i, sz[child]); j >= 0; j --)
   1486                     suff_merge[c][i] = max(suff_merge[c][i], suff_merge[c + 1][i - j] + dp_down_take[child][j]);
   1487             for (int i = k; i >= max(0, k - sz[child] - 1); i --)
   1488                 for (int j = min(i, p); j >= 0; j --)
   1489                     dp_up[child][i] = max(dp_up[child][i], suff_merge[c + 1][i - j] + (c > 0 ? pref_merge[c - 1][j] : 0));
   1490         }
   1491     }
   1492     for (auto a : children[node]) {
   1493         for (int i = min(k, n - sz[a]); i >= 1; i --)
   1494             dp_up[a][i] = max(dp_up[a][i], dp_up[a][i - 1] + (ll)i * weight[node]);
   1495         dfs2(a);
   1496     }
   1497 }
   1498 
   1499 void solve() {
   1500     cin >> n >> k;
   1501     for (int i = 0; i < n; i ++) {
   1502         for (int j = 0; j <= k; j ++)
   1503             dp_down[i][j] = dp_down_take[i][j] = dp_up[i][j] = 0;
   1504         adj[i].clear(); children[i].clear();
   1505         cin >> weight[i];
   1506     }
   1507     for (int i = 0; i < n - 1; i ++) {
   1508         int a, b; cin >> a >> b;
   1509         a --; b --;
   1510         adj[a].push_back(b);
   1511         adj[b].push_back(a);
   1512     }
   1513     dfs1(0, -1);
   1514     dfs2(0);
   1515     for (int i = 0; i < n; i ++) {
   1516         ll best = 0;
   1517         for (int j = 0; j < min(k, sz[i]); j ++)
   1518             best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * weight[i]);
   1519         cout << best << " ";
   1520     }
   1521     cout << endl;
   1522 }
   1523 
   1524 int main() {
   1525 	ios_base::sync_with_stdio(false);
   1526     cin.tie(NULL);
   1527     int tt = 1;
   1528 
   1529     cin >> tt;
   1530 
   1531     while (tt--) solve();
   1532     return 0;
   1533 }
   1534 ```
   1535 
   1536 **Code (Absolute Cinema Solution)**
   1537 
   1538 ```
   1539 #include <bits/stdc++.h>
   1540 using namespace std;
   1541  
   1542 typedef long long ll;
   1543 #define all(x) x.begin(), x.end()
   1544 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
   1545 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
   1546  
   1547 const int MAXN = 4005;
   1548 int n, k;
   1549 int spare;
   1550 vector<int> adj[MAXN], children[2 * MAXN];
   1551 ll beauty[2 * MAXN];
   1552 int sz[2 * MAXN];
   1553 ll dp_down[2 * MAXN][MAXN], dp_down_take[2 * MAXN][MAXN];
   1554 ll dp_up[2 * MAXN][MAXN];
   1555  
   1556 void merge(ll *target, ll *aa, ll *bb, int tsize, int asize, int bsize, int topmost) {
   1557     for (int i = tsize; i > max(0, tsize - topmost); i --)
   1558         for (int j = 0; j <= min(min(asize, bsize), i); j ++)
   1559             target[i] = max(target[i], asize >= bsize ? aa[i - j] + bb[j] : bb[i - j] + aa[j]);
   1560 }
   1561 void finalise(ll *target, ll *source, ll b, int tsize) {
   1562     for (int i = tsize; i > 0; i --)
   1563         target[i] = max(source[i], source[i - 1] + (ll)i * b);
   1564 }
   1565  
   1566 void dfs1(int node, int parent) {
   1567     vector<int> cc;
   1568     for (auto a : adj[node])
   1569         if (a != parent) {
   1570             dfs1(a, node);
   1571             cc.push_back(a);
   1572         }
   1573     int cur = node;
   1574     while (cc.size() > 2) {
   1575         children[cur] = {cc.back(), spare};
   1576         cc.pop_back();
   1577         beauty[spare] = beauty[node];
   1578         cur = spare ++;
   1579     }
   1580     children[cur] = cc;
   1581 }
   1582  
   1583 void dfs2(int node) {
   1584     sz[node] = (node < n);
   1585     for (auto a : children[node]) {
   1586         dfs2(a);
   1587         sz[node] += sz[a];
   1588     }
   1589     if (children[node].size() == 1) {
   1590         for (int i = 0; i <= k; i ++)
   1591             dp_down[node][i] = dp_down_take[children[node][0]][i];
   1592     } else if (children[node].size() == 2) {
   1593         merge(dp_down[node], dp_down_take[children[node][0]], dp_down_take[children[node][1]], min(k, sz[node] - (node < n)), sz[children[node][0]], sz[children[node][1]], sz[node] - (node < n));
   1594     }
   1595     finalise(dp_down_take[node], dp_down[node], node < n ? beauty[node] : 0, min(k, sz[node]));
   1596 }
   1597  
   1598 void dfs3(int node) {
   1599     if (children[node].size() == 1) {
   1600         finalise(dp_up[children[node][0]], dp_up[node], beauty[node], min(k, n - sz[children[node][0]]));
   1601     } else if (children[node].size() == 2) {
   1602         int aa = children[node][0], bb = children[node][1];
   1603         merge(dp_up[aa], dp_up[node], dp_down_take[bb], min(n - sz[aa], k), min(n - sz[node], k), min(sz[bb], k), min(sz[aa] + 2, k));
   1604         merge(dp_up[bb], dp_up[node], dp_down_take[aa], min(n - sz[bb], k), min(n - sz[node], k), min(sz[aa], k), min(sz[bb] + 2, k));
   1605         if (aa < n)
   1606             finalise(dp_up[aa], dp_up[aa], beauty[node], min(n - sz[aa], k));
   1607         if (bb < n)
   1608             finalise(dp_up[bb], dp_up[bb], beauty[node], min(n - sz[bb], k));
   1609     }
   1610     for (auto a : children[node])
   1611         dfs3(a);
   1612 }
   1613  
   1614 void solve() {
   1615     cin >> n >> k;
   1616     for (int i = 0; i < n; i ++)
   1617         adj[i].clear(), children[i].clear();
   1618     for (int i = n; i < 2 * n; i ++)
   1619         children[i].clear();
   1620     spare = n;
   1621     for (int i = 0; i < n; i ++)
   1622         cin >> beauty[i];
   1623     for (int i = 0; i < n - 1; i ++) {
   1624         int a, b; cin >> a >> b;
   1625         a --; b --;
   1626         adj[a].push_back(b);
   1627         adj[b].push_back(a);
   1628     }
   1629     dfs1(0, -1);
   1630     for (int i = 0; i < spare; i ++)
   1631         for (int j = 0; j <= k; j ++)
   1632             dp_down[i][j] = dp_up[i][j] = dp_down_take[i][j] = 0;
   1633     dfs2(0);
   1634     dfs3(0);
   1635     for (int i = 0; i < n; i ++) {
   1636         ll best = 0;
   1637         for (int j = 0; j < min(k, sz[i]); j ++)
   1638             best = max(best, dp_down[i][j] + dp_up[i][k - 1 - j] + (ll)k * beauty[i]);
   1639         cout << best << " ";
   1640     }
   1641     cout << endl;
   1642 }
   1643  
   1644 int main() {
   1645 	ios_base::sync_with_stdio(false);
   1646     cin.tie(NULL);
   1647     int tt = 1;
   1648  
   1649     cin >> tt;
   1650  
   1651     while (tt--) solve();
   1652     return 0;
   1653 }
   1654 ```
   1655 
   1656 **Rate the problem!**
   1657 
   1658 **Quality**
   1659 
   1660 * Excellent problem
   1661 * Good problem
   1662 * Average problem
   1663 * Bad problem
   1664 * Horrible problem
   1665 
   1666 **Difficulty**
   1667 
   1668 * Trivial problem
   1669 * Easy problem
   1670 * Average problem
   1671 * Hard problem
   1672 * Impossible problem