codeforces-scrape

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

2117.md (32975B)


      1 Source: https://codeforces.com/blog/entry/143362
      2 
      3 **Rating Predictions**
      4 
      5 | Predictor | A | B | C | D | E | F | G | H |
      6 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 800 | 900 | 1300 | 1500 | 1800 | 1900 | 2300 |
      8 | [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv") | 800 | 800 | 1100 | 1200 | — | 1600 | 1900 | 2200 |
      9 | [wuhudsm](/profile/wuhudsm "Candidate Master wuhudsm") | 600 | 800 | 1300 | 1500 | 2100 | 1900 | 2100 | 2200 |
     10 | [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") | 800 | 800 | 1000 | 1200 | 1900 | 1800 | 1800 | 2000 |
     11 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 800 | 1100 | 1300 | 1500 | 1700 | 1900 | 2400 |
     12 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 800 | 1300 | 1400 | 1600 | 1800 | 2100 | 2400 |
     13 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 1200 | 1300 | — | 1700 | 1800 | 2300 |
     14 | [Edeeva](/profile/Edeeva "Master Edeeva") | 800 | 800 | 1200 | 1400 | 1500 | 1800 | 2000 | — |
     15 | [Intellegent](/profile/Intellegent "Master Intellegent") | 800 | 800 | 1300 | 1400 | 1500 | 1700 | 1800 | 2400 |
     16 | [beaten_by_ai](/profile/beaten_by_ai "Expert beaten_by_ai") | 800 | 800 | 1200 | 1100 | 1600 | 1800 | 1900 | 2200 |
     17 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 800 | 1100 | 1400 | 1300 | 1000 | 2100 | — |
     18 | [efishel](/profile/efishel "Master efishel") | 800 | 800 | 1200 | 1200 | 1300 | 1700 | 2000 | 2300 |
     19 | [__baozii__](/profile/__baozii__ "International Master __baozii__") | 800 | 800 | 1200 | 1500 | 1500 | 1800 | 1700 | 2300 |
     20 
     21 Thanks to [reirugan](/profile/reirugan "Candidate Master reirugan") for helping proofread the editorial!
     22 
     23 #### [2117A — False Alarm](https://codeforces.com/contest/2117/problem/A)
     24 
     25 Author: [yse](/profile/yse "Expert yse")
     26 
     27 **Hint**
     28 
     29 When is the optimal time to use the button?
     30 
     31 **Solution (written by yse)**
     32 
     33 It's not necessary to use the button when a door is already open. Therefore, it's always optimal to use the button as soon as we hit a closed door.
     34 
     35 Let's call the position of the first closed door $l$ and the position of the last closed door $r$. The length of this interval is $r - l + 1$, so we need to check that $x$ is greater than or equal to $r - l + 1$.
     36 
     37 **Code (C++)**
     38 
     39 ```
     40 #include <bits/stdc++.h>
     41  
     42 using namespace std;
     43 
     44 void solve() {
     45     int n, x;
     46     cin >> n >> x;
     47 
     48     int l = 1e5, r = -1;
     49     for(int i = 0; i < n; i++) {
     50         int door;
     51         cin >> door;
     52 
     53         if(door == 1) {
     54             l = min(l, i);
     55             r = max(r, i);
     56         }
     57     }
     58 
     59     cout << (x >= r - l + 1 ? "YES" : "NO") << endl;
     60 }
     61 
     62 int main() {
     63     int t;
     64     cin >> t;
     65     while(t--) solve();
     66 }
     67 ```
     68 
     69 **Rate the problem!**
     70 
     71 * Good problem 😁
     72 * Average problem 🤔
     73 * Bad problem 😭
     74 * Did not solve 😴
     75 
     76 #### [2117B — Shrink](https://codeforces.com/contest/2117/problem/B)
     77 
     78 Author: [yse](/profile/yse "Expert yse")
     79 
     80 **Hint 1**
     81 
     82 When are we unable to remove the maximum element?
     83 
     84 **Hint 2**
     85 
     86 We can always remove the maximum element as long as it exists between two elements. How can we generalize this?
     87 
     88 **Solution (written by yse)**
     89 
     90 In a permutation, the maximum element can only occur once. Since all other elements are guaranteed to be smaller than maximum, we can remove the maximum if there exists an element on its left and another on its right.
     91 
     92 After we remove the maximum element, another maximum appears, which we also want to remove. This process can keep going until the length of the permutation becomes $2$, since both remaining elements are on the ends and can not be removed.
     93 
     94 Therefore, any permutation with $1$ and $2$ on the ends is acceptable, since any value greater than $2$ will eventually be a maximum in between two elements.
     95 
     96 **Code (C++)**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100  
    101 using namespace std;
    102 
    103 void solve() {
    104     int n;
    105     cin >> n;
    106     
    107     for(int i = 2; i <= n; i++) cout << i << ' ';
    108     cout << 1 << endl;
    109 }
    110 
    111 int main() {
    112     int t;
    113     cin >> t;
    114     while(t--) solve();
    115 }
    116 ```
    117 
    118 **Rate the problem!**
    119 
    120 * Good problem 😁
    121 * Average problem 🤔
    122 * Bad problem 😭
    123 * Did not solve 😴
    124 
    125 #### [2117C — Cool Partition](https://codeforces.com/contest/2117/problem/C)
    126 
    127 Author: [yse](/profile/yse "Expert yse")
    128 
    129 **Hint 1**
    130 
    131 The last segment of a valid partition must contain all distinct elements of the array.
    132 
    133 **Hint 2**
    134 
    135 From the first hint, we can say that any segment ending at some position $r$ must contain all distinct elements of the prefix $[1, r]$.
    136 
    137 **Solution 1 (written by yse)**
    138 
    139 Claim: In a valid partition, if a segment ends at some position $r$, it must contain all distinct elements in the prefix $[1, r]$.
    140 
    141 **Proof**
    142 
    143 Call the segments $b_1,b_2,\dots,b_k$. Notice that an element in some segment $b_j$ must also appear in $b_{j+1}, b_{j+2}, ..., b_k$.
    144 
    145 Now, let's prove by contradiction. Assume that some segment $b_j$ doesn't contain all distinct elements in $[1, r]$, where $r$ is the end position of $b_j$. Then, the distinct elements that don't appear in $b_j$ surely appear in some previous segment(s). This does not make a valid partition since at least one previous segment contains an element which $b_j$ does not have.
    146 
    147 Let $d_i$ be the number of distinct elements in the range $[1, i]$. To maximize the number of segments, we make them as small as possible. Let $r$ be the end position for the current segment, we will iterate from $r$ to the left until we find the first position $l$ such that the number of distinct elements in $[l, r] = d_r$, then increment our answer and set $r = l - 1$. We repeat until $l=1$.
    148 
    149 **Code (C++)**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153  
    154 using namespace std;
    155 
    156 void solve() {
    157     int n;
    158     cin >> n;
    159     vector<int> v(n);
    160     vector<int> distinct(n), freq(n + 1);
    161     
    162     int total = 0;
    163     for(int i = 0; i < n; i++) {
    164         cin >> v[i];
    165         freq[v[i]]++;
    166         if(freq[v[i]] == 1) distinct[i] = 1;
    167         distinct[i] += (i ? distinct[i - 1] : 0);
    168     }
    169 
    170     fill(freq.begin(), freq.end(), 0);
    171 
    172     int ans = 0, end = n - 1;
    173     total = 0;
    174     for(int i = n - 1; i >= 0; i--) {
    175         freq[v[i]]++;
    176         if(freq[v[i]] == 1) total++;
    177         
    178         if(total == distinct[end]) {
    179             ans++;
    180             for(int j = i; j <= end; j++) freq[v[j]] = 0;
    181             end = i - 1;
    182             total = 0;
    183         }
    184     }
    185 
    186     cout << ans << endl;
    187 }
    188 
    189 int main() {
    190     int t;
    191     cin >> t;
    192     while(t--) solve();
    193 }
    194 ```
    195 
    196 **Solution 2 (written by reirugan)**
    197 
    198 Similarly to the above solution, we can have a segment $[l, r]$ if and only if $[l, r]$ contains all of the same elements as $[1, r]$. We now build our segments greedily from the front, iterating through each element. Suppose the element we are currently on is $a_i$. We make the following claim: if we can end the current segment at $a_i$, we should do so. (There is one exception to this, which is covered after the proof.)
    199 
    200 **Proof**
    201 
    202 Suppose we are able to end the current segment at $a_i$. Clearly, if $a_i$ is the last element of the array, we must end the segment. Otherwise, suppose that instead, it is optimal to end the segment at $a_j$ for $j \gt i$. Then we could just instead end the segment at $a_i$, and merge the elements from $a_{i+1}$ to $a_j$ into the next segment. This doesn't cause any issues with legality, because by assumption, it is legal to end the current segment at $a_i$, and the subsequent segment only gets bigger so it has at least as many distinct values as before. Furthermore, this does not affect the number of segments we have, so this is also an optimal solution.
    203 
    204 Now, we just end segments whenever we can. The only "special" case that needs to be taken care of, is whether or not the last segment is legal. But if it isn't, we can simply merge it into the last legal segment, which only makes this segment bigger and thus doesn't cause any issues since it has at least as many distinct values as before. It turns out that this doesn't really affect the implementation, since we just have to count the number of times we can end the segment.
    205 
    206 So how do we do this quickly? Let's keep a set of all elements in $[1, i]$, and a set of all elements in $[l, i]$. Then if these sets are the same size, we know that $[l, i]$ contains all of the same elements as $[1, i]$. If this is the case, we will end the segment at $i$. Then we will increment our answer, and set $l:=i+1$ (in the implementation, we will clear the set of elements in $[l, i]$).
    207 
    208 **Code (C++)**
    209 
    210 ```
    211 #include <bits/stdc++.h>
    212 using namespace std;
    213  
    214 void solve(){
    215     int n, ans = 0;
    216     cin >> n;
    217     vector<int> a(n);
    218     for(int i=0; i<n; i++) cin >> a[i];
    219     set<int> cur, seen;
    220     for(int i=0; i<n; i++){
    221         cur.insert(a[i]);
    222         seen.insert(a[i]);
    223         if(cur.size() == seen.size()){
    224             ans++;
    225             seen.clear();
    226         }
    227     }
    228     cout << ans << '\n';
    229 }
    230  
    231 int main(){
    232     ios::sync_with_stdio(false);
    233     cin.tie(NULL);
    234     int t;
    235     cin >> t;
    236     while(t--) solve();
    237 }
    238 ```
    239 
    240 **Rate the problem!**
    241 
    242 * Good problem 😁
    243 * Average problem 🤔
    244 * Bad problem 😭
    245 * Did not solve 😴
    246 
    247 #### [2117D — Retaliation](https://codeforces.com/contest/2117/problem/D)
    248 
    249 Author: [yse](/profile/yse "Expert yse")
    250 
    251 **Hint**
    252 
    253 What happens when we do $1$ operation of the first type and $1$ operation of the second type?
    254 
    255 **Solution 1 (written by yse)**
    256 
    257 If we perform both types of the operation once, each element $a_i$ is decreased by $n + 1$. Suppose we are able to explode the array with $x$ operations of the first type and $y$ operations of the second type. Then, let's pair as many operations as we can, allowing us to perform $\min(x, y)$ pairs of operations.
    258 
    259 Now, assume we finished pairing the operations. This leaves us with some operations (possibly none) of only one type, so the array must become an arithmetic sequence; the absolute difference between two consecutive elements is the number of operations that we have to perform.
    260 
    261 We don't yet know the number of pairs of operations $\min(x, y)$ that we have to perform, since we don't know the value of $x$ and $y$, but we now know the number of extra operations we perform after pairing the operations. Since we need to have an arithmetic sequence in order to explode the array, we should verify that the difference between adjacent elements are all the same. Let's call the number of extra operations $k = |x-y|$, which is equal to the difference between adjacent elements. If the array is increasing, the extra operations must be of the first type. Otherwise, they must be of the second type.
    262 
    263 Now, let's first perform the $k$ operations on the array. Since the consecutive differences are all the same, after performing the $k$ extra operations, all elements should be equal. It remains to check that the elements are non-negative and are divisible by $n + 1$, so we can now perform pairs of operations to explode the array.
    264 
    265 **Code (C++)**
    266 
    267 ```
    268 #include <bits/stdc++.h>
    269 
    270 using namespace std;
    271 
    272 void solve() {
    273     int n;
    274     cin >> n;
    275     vector<long long> v(n);
    276     for(auto &it : v) cin >> it;
    277 
    278     long long diff = v[1] - v[0];
    279     bool bad = 0;
    280     for(int i = 2; i < n; i++) if(diff != v[i] - v[i - 1]) bad = 1;
    281     
    282     if(bad) {
    283         cout << "NO" << endl;
    284         return;
    285     }
    286     
    287     for(int i = 0; i < n; i++)
    288         v[i] = v[i] + (diff < 0 ? diff * (n - i) : -diff * (i + 1));
    289         
    290     cout << (v[0] >= 0 && v[0] % (n + 1) == 0 ? "YES" : "NO") << endl;
    291 }
    292 
    293 int main() {
    294     int t;
    295     cin >> t;
    296     while(t--) solve();
    297 }
    298 ```
    299 
    300 **Hint 1**
    301 
    302 Suppose we did $x$ operations of the first type and $y$ operations of the second type to explode the array. What must the value of $a_1$ be?
    303 
    304 **Hint 2**
    305 
    306 From the first hint, we know the first element $a_1 = 1 \cdot x + n \cdot y$. What about the second element?
    307 
    308 **Solution 2 (written by yse)**
    309 
    310 Let's consider the first two elements. Suppose we needed $x$ operations of the first type and $y$ operations of the second type to explode the array, then we know $a_1 = 1 \cdot x + n \cdot y$. For the second element, we know $a_2 = 2 \cdot x + (n - 1) \cdot y$.
    311 
    312 Now, let's solve for $x$ and $y$. Subtracting $a_2$ from $a_1$ gives us
    313 
    314 \begin{align*} a_1 — a_2 &= (x + n \cdot y) — (2 \cdot x + (n — 1) \cdot y) \newline &= y — x \newline \Longrightarrow x &= y — a_1 + a_2 \end{align*}
    315 
    316 Let's substitute $y - a_1 + a_2$ for $x$ in the first formula.
    317 
    318 \begin{align*} a_1 &= (y — a_1 + a_2) + n \cdot y \newline \Longrightarrow y &= \frac{2 \cdot a_1 — a_2}{n + 1} \end{align*}
    319 
    320 Now, we have the value of $y$, which means we can easily find the value of $x$. From the formula $x = y - a_1 + a_2$, substitute $y$ with its value to get $x$. What remains is just to check if the array becomes $a_1 = a_2 = \dots = a_n = 0$ after all the operations.
    321 
    322 **Code (C++)**
    323 
    324 ```
    325 #include <bits/stdc++.h>
    326 
    327 using namespace std;
    328 typedef long long ll;
    329 
    330 void solve() {
    331     ll n;
    332     cin >> n;
    333     vector<ll> v(n);
    334     for(auto &it : v) cin >> it;
    335 
    336     ll y = (2 * v[0] - v[1]) / (n + 1);
    337     ll x = v[1] - v[0] + y;
    338 
    339     if(y < 0 || x < 0) {
    340         cout << "NO" << endl;
    341         return;
    342     }
    343 
    344     for(int i = 0; i < n; i++) {
    345         v[i] -= x * (i + 1);
    346         v[i] -= y * (n - i);
    347     }
    348 
    349     for(int i = 0; i < n; i++) {
    350         if(v[i] != 0) {
    351             cout << "NO" << endl;
    352             return;
    353         }
    354     }
    355 
    356     cout << "YES" << endl;
    357 }
    358 
    359 int main() {
    360     int t;
    361     cin >> t;
    362     while(t--) solve();
    363 }
    364 ```
    365 
    366 **Rate the problem!**
    367 
    368 * Good problem 😁
    369 * Average problem 🤔
    370 * Bad problem 😭
    371 * Did not solve 😴
    372 
    373 #### [2117E — Lost Soul](https://codeforces.com/contest/2117/problem/E)
    374 
    375 Author: [yse](/profile/yse "Expert yse"), [cry](/profile/cry "International Master cry")
    376 
    377 **Hint 1**
    378 
    379 If we can get a match at position $i$, then we can have at least $i$ matches. Why is this true?
    380 
    381 **Hint 2**
    382 
    383 For a certain position $i$, given the ability to remove index $i + 1$, we can pull any value from the range $[i + 2, n]$.
    384 
    385 **Solution (written by yse)**
    386 
    387 It's clear to see that if a match exists at position $i$, then we can repeatedly set $a_j := b_{j+1}$ and $b_j := a_{j+1}$ for all $j$, where $j$ starts as $i - 1$ and goes backwards until the start of the array. This allows us to have at least $i$ matches (including the match at position $i$).
    388 
    389 Therefore, the optimal approach is to maximize the index $i$ where $a_i = b_i$. Suppose we can't remove any element. Then, for some $a_i$, we can set it to any $b_j$ such that $j \pmod 2 \neq i \pmod 2$ and $j \gt i$, or set it to any $a_j$ such that $j \pmod 2 = i \pmod 2$ and $j \gt i$.
    390 
    391 However, if we wanted to set $a_i$ to some $b_j$ where $j \pmod 2 = i \pmod 2$, then we can just remove index $i + 1$ from the array. By similar reasoning, we can set $a_i$ to any $a_j$ where $j \pmod 2 \neq i \pmod 2$ and $j \gt i+1$. Notice that we removed index $i + 1$, so we can't set $a_i := a_{i+1}$. Now, we know that we can set any $a_i$ to any $a_j$ or $b_j$ such that $j \gt i + 1$. This can be generalized for $b_i$ as well.
    392 
    393 So the solution is that, for each position $i$, we want to check if any $a_j$ or $b_j$, such that $j \gt i + 1$, matches $a_i$ or $b_i$, allowing us to get a match at position $i$. We also need to check if position $i$ already contains a match, or if $a_i = a_{i + 1}$ or $b_i = b_{i + 1}$.
    394 
    395 **Code (C++)**
    396 
    397 ```
    398 #include <bits/stdc++.h>
    399 
    400 using namespace std;
    401 
    402 void solve() {
    403     int n;
    404     cin >> n;
    405     vector<int> a(n), b(n);
    406 
    407     for(auto &it : a) cin >> it;
    408     for(auto &it : b) cin >> it;
    409 
    410     vector<bool> seen(n + 1);
    411     if(a.back() == b.back()) {
    412         cout << n << endl;
    413         return;
    414     }
    415 
    416     int ans = -1;
    417     for(int i = n - 2; i >= 0; i--) {
    418         if(a[i] == b[i] || a[i] == a[i + 1] || b[i] == b[i + 1] || seen[a[i]] || seen[b[i]]) {
    419             ans = i;
    420             break;
    421         }
    422 
    423         seen[a[i + 1]] = seen[b[i + 1]] = true;
    424     }
    425 
    426     cout << ans + 1 << endl;
    427 }
    428 
    429 int main() {
    430     int t;
    431     cin >> t;
    432     while(t--) solve();
    433 }
    434 ```
    435 
    436 **Rate the problem!**
    437 
    438 * Good problem 😁
    439 * Average problem 🤔
    440 * Bad problem 😭
    441 * Did not solve 😴
    442 
    443 #### [2117F — Wildflower](https://codeforces.com/contest/2117/problem/F)
    444 
    445 Author: [yse](/profile/yse "Expert yse")
    446 
    447 **Hint 1**
    448 
    449 There can only be at most $2$ leaves. This means the tree can either be a chain or Y-shaped.
    450 
    451 **Hint 2**
    452 
    453 If the tree is a chain, subtree sums will always be strictly increasing as you move towards the root, which means that the answer for any chain is $2^n$.
    454 
    455 **Solution (written by yse)**
    456 
    457 Claim: For an answer to exist, the tree should have at most $2$ leaves.
    458 
    459 **Proof**
    460 
    461 We can use pigeonhole principle.
    462 
    463 Suppose the tree has more than $2$ leaves. Then for each leaf $\ell$, its subtree sum is $a_\ell \in \lbrace 1,2 \rbrace$. By pigeonhole principle, among three leaves there must be two with the same value, forcing subtree sums to not be unique. Thus, it is impossible to make all values in $s$ pairwise distinct if there are $3$ or more leaves.
    464 
    465 We only need to consider two cases, the case of $1$ leaf and the case of $2$ leaves.
    466 
    467 * $1$ leaf case: We can see that $\lbrace 1,2 \rbrace$ are positive values, so $s$ is strictly increasing as you move towards the root. Therefore, any array $a$ will be valid. The answer for this case would be $2^n$.
    468 
    469 * $2$ leaves case: Let $v$ be the lowest common ancestor between leaf $x$ and leaf $y$. From $v$ going up towards the root, we can see that it follows the same idea of the $1$ leaf case, which means that any vertex in the path between the root and $v$ can be assigned to either $1$ or $2$. Without loss of generality, suppose leaf $x$ has smaller depth than leaf $y$. Say we assigned $a_x = 1$ and $a_y = 2$; it is easy to see that we are forced to assign vertices to $2$ as we're going up, until we eventually finish assigning a branch. So the number of vertices that are free to be assigned to either $1$ or $2$ in $y$'s branch is simply $\texttt{depth}_y - \texttt{depth}_x$. If we assign $a_x = 2$ and $a_y = 1$ instead, then $y$ would have one more vertex forced to be assigned to $2$, meaning there are only $\texttt{depth}_y - \texttt{depth}_x - 1$ free vertices in $y$'s branch. Finally, the last case to be checked is if $\texttt{depth}_x = \texttt{depth}_y$. In this case, whether we assign $x$ to $1$ and $y$ to $2$, or we assign $x$ to $2$ and $y$ to $1$, all vertices in both branches are forced, so there are no free vertices in either branch.
    470 
    471 Let the number of leaves be $\texttt{cnt}$. Then we have that: $\texttt{Answer}$ = \begin{cases} 0 &\text{if }\texttt{cnt} > 2 \newline 2^n &\text{if }\texttt{cnt} = 1 \newline (2^{\texttt{depth}_y — \texttt{depth}_x} + 2^{\texttt{depth}_y — \texttt{depth}_x — 1}) \cdot 2^{\texttt{depth}_v} &\text{if }\texttt{cnt} = 2\text{ and }\texttt{depth}_x < \texttt{depth}_y \newline 2^{\texttt{depth}_v} + 2^{\texttt{depth}_v} &\text{if }\texttt{cnt} = 2\text{ and }\texttt{depth}_x = \texttt{depth}_y \end{cases}
    472 
    473 **Code (C++)**
    474 
    475 ```
    476 #include <bits/stdc++.h>
    477  
    478 using namespace std;
    479  
    480 const int N = 2e5 + 10, MOD = 1e9 + 7;
    481 #define int long long
    482  
    483 vector<int> adj[N], lens;
    484 int pw[N];
    485 int lca;
    486  
    487 void dfs(int u, int par, int len) {
    488     if(adj[u].size() > 2) lca = len;
    489     
    490     bool leaf = true;
    491     for(int v : adj[u]) {
    492         if(v != par) {
    493             dfs(v, u, len + 1);
    494             leaf = false;
    495         }
    496     }
    497  
    498     if(leaf) lens.push_back(len);
    499 }
    500 
    501 void solve() {
    502     int n;
    503     cin >> n;
    504 
    505     for(int i = 1; i <= n; i++) adj[i].clear();
    506     lens.clear();
    507     lca = -1;
    508 
    509     for(int i = 0; i < n - 1; i++) {
    510         int u, v;
    511         cin >> u >> v;
    512         adj[u].push_back(v);
    513         adj[v].push_back(u);
    514     }
    515 
    516     adj[1].push_back(0); // dummy node
    517     dfs(1, 0, 1);
    518     if(lens.size() > 2) cout << 0 << endl;
    519     else if(lens.size() == 1) cout << pw[n] << endl;
    520     else {
    521         int diff = abs(lens[0] - lens[1]);
    522         int x = diff + lca;
    523         if(diff) cout << (pw[x] + pw[x - 1]) % MOD << endl;
    524         else cout << (2 * pw[x]) % MOD << endl;
    525     }
    526 }
    527 
    528 signed main() {
    529     pw[0] = 1;
    530     for(int i = 1; i < N; i++) pw[i] = (pw[i - 1] * 2) % MOD;
    531 
    532     int t;
    533     cin >> t;
    534     while(t--) solve();
    535 }
    536 ```
    537 
    538 **Rate the problem!**
    539 
    540 * Good problem 😁
    541 * Average problem 🤔
    542 * Bad problem 😭
    543 * Did not solve 😴
    544 
    545 #### [2117G — Omg Graph](https://codeforces.com/contest/2117/problem/G)
    546 
    547 Author: [Intellegent](/profile/Intellegent "Master Intellegent")
    548 
    549 **Hint**
    550 
    551 Try fixing the minimum edge on the path.
    552 
    553 **Solution (written by Intellegent)**
    554 
    555 There are two common ways to solve this problem; one uses DSU and the other uses Dijkstra. I will explain the Dijkstra approach here:
    556 
    557 The main idea here is to pick some edge $e$ and pretend that $e$ is the minimum-weight edge, then find the smallest maximum edge weight across all paths containing $e$. This method will only ever overestimate the answer, and equality holds when we choose $e$ to be the minimum-weight edge of the optimal path, so the answer must be the minimum of these values across all possible choices.
    558 
    559 Lets define a new cost function. Instead of $cost(w_1,...,w_k) = (\min_{i = 1}^{k}{w_i}) + (\max_{i=1}^{k}{w_i})$, let's define $cost_j(w_1,...,w_k) = w_j + (\max_{i=1}^{k}{w_i})$, i.e. the weight of edge $j$ + the max weight. By the above reasoning, the minimum value of $cost_j(w_1,...,w_k)$ across all $j$ is the same as the minimum value of $cost(w_1,...,w_k)$.
    560 
    561 This function is a lot easier to minimize than the initial one. Let's iterate over each edge $j$ — denote its endpoints to be $u_j$ and $v_j$, and its weight to be $w_j$ — and find the minimum value of $cost_j(w_1,...,w_k)$. Now we just need to find the minimum possible value of $\max_{i=1}^{k}{w_i}$ across all paths that contain $j$. To do this, we just want to minimize the max weight of the path from $1$ to $u$ and from $v$ to $n$, so we have reduced the problem to finding the minimum max weight on a path from $1$ to all other nodes, and finding the minimum max weight on a path from every node to $n$. But how do we do this?
    562 
    563 The idea is very similar to Dijkstra — recall the proof that Dijkstra finds the minimum sum of weights on a path. The main idea is that whenever we pop a node from the heap, we know that the minimum cost to it has already been found. We can use the same reasoning to prove that if we change path cost from path sum to path max, then the algorithm will still work. So all we have to do is simply run this max Dijkstra variation from $1$ and from $n$.
    564 
    565 Now we just need to find the minimum value of $w_i + \max(\mathrm{cost}(1, u_i), \mathrm{cost}(v_i, n), w_i)$ across all edges $i$.
    566 
    567 **Code (C++)**
    568 
    569 ```
    570 #include<bits/stdc++.h>
    571 using namespace std;
    572 typedef long long ll;
    573 #define debug(x) cout << #x << " = " << x << "\n";
    574 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    575 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    576 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    577 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    578 
    579 void solve(){
    580     int n, m;
    581     cin >> n >> m;
    582 
    583     vector<vector<array<int, 2>>> g(n);
    584     for (int i = 0; i < m; i++){
    585         int u, v, w;
    586         cin >> u >> v >> w;
    587         u--;
    588         v--;
    589 
    590         g[u].push_back({v, w});
    591         g[v].push_back({u, w});
    592     }
    593 
    594     auto uwu = [&](int u) -> vector<ll>{
    595         vector<ll> dis(n, 1e18);
    596         vector<bool> vis(n);       
    597 
    598         priority_queue<array<ll, 2>> q;
    599         q.push({0, u});
    600         while (q.size()){
    601             auto [d, c] = q.top();
    602             d = -d;
    603             q.pop();
    604 
    605             if (vis[c])
    606                 continue;
    607             vis[c] = true;
    608             dis[c] = d;
    609 
    610             for (auto [x, w] : g[c]){
    611                 if (vis[x])
    612                     continue;
    613 
    614                 q.push({-max(d, 1LL * w), x});
    615             }
    616         }
    617 
    618         return dis;
    619     };
    620 
    621     ll ans = 1e18;
    622     vector<ll> dis_s = uwu(0), dis_t = uwu(n - 1);
    623     for (int u = 0; u < n; u++){
    624         for (auto [v, w] : g[u]){
    625             ans = min(ans, {max({dis_s[u], dis_t[v], 1LL * w}) + w});
    626         }
    627     }
    628 
    629     cout << ans << "\n";
    630 }
    631 
    632 int main(){
    633     ios::sync_with_stdio(false);
    634     cin.tie(0);
    635     
    636     int t;
    637     cin >> t;
    638     while (t--) solve();
    639 }
    640 ```
    641 
    642 **Rate the problem!**
    643 
    644 * Good problem 😁
    645 * Average problem 🤔
    646 * Bad problem 😭
    647 * Did not solve 😴
    648 
    649 #### [2117H — Incessant Rain](https://codeforces.com/contest/2117/problem/H)
    650 
    651 Author: [cry](/profile/cry "International Master cry")
    652 
    653 **Hint 1**
    654 
    655 Try to think of an offline solution.
    656 
    657 **Hint 2**
    658 
    659 Rephrase the problem to maximum subarray sums.
    660 
    661 **Solution (written by cry)**
    662 
    663 *The unusual memory limit is meant to cut persistent segment tree solutions. Obviously it isn't perfect (I apologize if it caused issues), but it's the best I could do.*
    664 
    665 Let's first pretend that $x$ in the problem is fixed. For example, if $x = 2$, then we want to find the maximum $k$ such that $2$ is a $k$-majority of some subarray. To solve this problem, let's build an array $b_1, b_2, \ldots, b_n$ such that $b_i = 1$ if $a_i = x$, and $b_i = -1$ otherwise. Let $s$ be the maximum subarray sum over all subarrays of $b$. The answer to the problem is $\lfloor \frac{s}{2} \rfloor$.
    666 
    667 Now let's consider how to handle updates. If we are asked to update index $k$ with an element $y$, we have two cases. If $a_k \neq x$ and $y=x$, then we update $b_k = 1$. Otherwise, if $a_k = x$ and $y \neq x$, then we set $b_k = -1$. Then, we can answer the query by finding the maximum subarray sum of $b$ using a segment tree. This is a [standard problem](https://usaco.guide/plat/segtree-ext?lang=cpp#solution---subarray-sum-queries).
    668 
    669 Let $b_i$ denote the sequence of arrays that correspond to the array $b$ that fixes $i$. Now let's stop fixing $x$. For each update, notice that at most two of the arrays in the sequence is modified (precisely, $b_{a_k}$ and $b_y$). To answer the query, let $\texttt{res}_x$ denote the answer maximum subarray sums of arrays $b_x$ for all $x \in [1, n]$ so far. The answer to this query is just $\lfloor \frac{\max(\texttt{res}_1, \texttt{res}_2, \ldots, \texttt{res}_n)}{2} \rfloor$. Additionally, because of the update, notice that only $\texttt{res}_{a_k}$ and $\texttt{res}_y$ might change. This motivates an approach where we track $\texttt{res}_x$ overall all $x$ and extract the maximum.
    670 
    671 For each $x$, let's keep track of all updates that modifies an index $k$ where it was $a_k = x$ originally or $a_k = x$ after the update. Let Notice that for the former case, we are setting $b_{x_k} = -1$ and in the latter case, we are setting $b_{x_k} = -1$. Notice that we are tracking at most $2q$ updates because each update modifies at most two $b_x$, as explained in the previous paragraph. Let's store all such updates in an array $v_x$.
    672 
    673 Let's try to construct $b_x$ for each $x \in [1, n]$ now. To do so, let's first create a global array $b$, where initially $b_i = -1$ over all $1 \leq i \leq n$. Then, we can iterate over all elements of $a$ where $a_j = x$ and set $b_j = 1$. Now we can iterate over the queries in $v_x$. For each query in $v_x$, we can track the maximum subarray sum of $b$ after each update. If this is the $j$'th query, then we must note that after the $j$'th query, we will update $\texttt{res}_x$. We can iterate over all $x \in [1, n]$ and perform the above process in $O((n + q)\log n))$ time total.
    674 
    675 Now, we know when to update $\texttt{res}_x$ for each $x \in [1, n]$. Finally, let's loop through all $q$ queries one last time and store all $\texttt{res}_x$ in a multiset. If the $j$'th query affects $\texttt{res}_y$, then we will erase the old $\texttt{res}_y$ from the multiset and replace it with the new one. To answer the query, we can simply extract the maximum element in the multiset.
    676 
    677 **Solution (written by LMeyling)**
    678 
    679 First, consider the $k$-majority for a single element $y$. By definition, for a subarray $b$, the $k$-majority is given by $\lfloor{\frac{2 \cdot \text{cnt}(y) - |b|}{2}}\rfloor$. Instead of computing this directly, we construct a new array $c$, where $c_i = 1$ if $b_i = y$ and $c_i = -1$ otherwise. Then, the $k$-majority for the element $y$ is equivalent to the maximum sum among all subarrays of $c$, floor-divided by 2. This transformation reduces our problem to finding the maximal subarray sum.
    680 
    681 Since we must efficiently handle updates, we require a dynamic data structure capable of both updates and queries. This can be accomplished using a segment tree that maintains the maximum subarray sum, maximum prefix sum, maximum suffix sum, and total sum within each node.
    682 
    683 To apply this method to all possible values of $y$, we process all queries offline. Initially, we set all elements of array $c$ to $-1$. For each distinct element $y$, we first update the array $c$ by setting $c_i = 1$ wherever $a_i$ initially equals $y$. Next, we sequentially apply all updates involving $y$, calculating the maximal $k$-majority for $y$ after each update. This procedure generates $q + n$ segments, each segment holding the maximal $k$-majority information for an element $y$. By inserting and removing these maximum values into a multiset, we efficiently retrieve the global maximal $k$-majority at every step. Giving $O((n + q)\log n)$.
    684 
    685 **Code (C++)**
    686 
    687 ```
    688 #include <bits/stdc++.h>
    689 using namespace std;
    690 using ll = long long;
    691 #define F first
    692 #define S second
    693 #define all(x) x.begin(), x.end()
    694 #define pb push_back
    695 #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
    696 #define trav(a,x) for(auto& a: x)
    697 #define sz(x) (int)x.size()
    698 template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
    699 
    700 struct Node {
    701     int sum;    // total sum of segment
    702     int pref;   // max prefix sum
    703     int suff;   // max suffix sum
    704     int best;   // max subarray sum
    705     Node(): sum(0), pref(0), suff(0), best(0) {}
    706     Node(int x): sum(x), pref(max(0,x)), suff(max(0,x)), best(max(0,x)) {}
    707 };
    708 
    709 Node merge(const Node &L, const Node &R) {
    710     Node res;
    711     res.sum  = L.sum + R.sum;
    712     res.pref = max(L.pref, L.sum + R.pref);
    713     res.suff = max(R.suff, R.sum + L.suff);
    714     res.best = max({ L.best, R.best, L.suff + R.pref });
    715     return res;
    716 }
    717 
    718 struct segtree {
    719     int n;
    720     vector<Node> st;
    721      segtree(int _n) {
    722         n = _n;
    723         st.resize(4*n);
    724         build(1, 0, n-1);
    725     }
    726     void build(int p, int l, int r) {
    727         if (l == r) {
    728             st[p] = Node(-1);
    729             return;
    730         }
    731         int m = (l + r) / 2;
    732         build(p<<1,   l,   m);
    733         build(p<<1|1, m+1, r);
    734         st[p] = merge(st[p<<1], st[p<<1|1]);
    735     }
    736     void update(int p, int l, int r, int idx, int val) {
    737         if (l == r) {
    738             st[p] = Node(val);
    739             return;
    740         }
    741         int m = (l + r) / 2;
    742         if (idx <= m) update(p<<1,   l,   m, idx, val);
    743         else          update(p<<1|1, m+1, r, idx, val);
    744         st[p] = merge(st[p<<1], st[p<<1|1]);
    745     }
    746     void update(int idx, int val) {
    747         update(1, 0, n-1, idx, val);
    748     }
    749     Node query(int p, int l, int r, int i, int j) {
    750         if (i > r || j < l) {
    751             Node nullnode;
    752             nullnode.sum = 0;
    753             nullnode.pref = nullnode.suff = nullnode.best = INT_MIN;
    754             return nullnode;
    755         }
    756         if (l >= i && r <= j) {
    757             return st[p];
    758         }
    759         int m = (l + r) / 2;
    760         Node L = query(p<<1,   l,   m, i, j);
    761         Node R = query(p<<1|1, m+1, r, i, j);
    762         if (L.best == INT_MIN) return R;
    763         if (R.best == INT_MIN) return L;
    764         return merge(L, R);
    765     }
    766     int max_subarray() {
    767         Node res = query(1, 0, n-1, 0, n-1);
    768         return res.best;
    769     }
    770 };
    771 
    772 void solve() {
    773 	int n, q; cin >> n >> q;
    774 	vector<int> a(n); cin >> a;
    775 	vector<vector<int>> at(n+1);
    776 	FOR(i,0,n) at[a[i]].pb(i);
    777 	vector<vector<array<int, 3>>> updates(n+1);
    778 	FOR(idx,0,q){
    779 		int i, x; cin >> i >> x;
    780 		--i;
    781 		if(x != a[i]){
    782 			updates[a[i]].pb({idx, i, -1});
    783 			a[i] = x;
    784 			updates[x].pb({idx, i, 1});
    785 		}
    786 	}
    787 	vector<vector<int>> final_at(n+1);
    788 	FOR(i,0,n) final_at[a[i]].pb(i);
    789 	segtree st(n);
    790 	vector<int> init(n+1);
    791 	vector<vector<pair<int,int>>> change(q);
    792 	FOR(x,1,n+1){
    793 		trav(i, at[x]){
    794 			st.update(i, 1);
    795 		}
    796 		int cur = st.max_subarray();
    797 		init[x] = cur;
    798 		trav(i, updates[x]){
    799 			st.update(i[1], i[2]);
    800 			int new_cur = st.max_subarray();
    801 			change[i[0]].pb({cur, new_cur});
    802 			cur = new_cur;
    803 		}
    804 		trav(i, final_at[x]){
    805 			st.update(i, -1);
    806 		}
    807 	}
    808 	multiset<int> ms;
    809 	FOR(i,1,n+1) ms.insert(init[i]);
    810 	FOR(i,0,q){
    811 		trav(j, change[i]){
    812 			ms.erase(ms.find(j.F));
    813 			ms.insert(j.S);
    814 		}
    815 		cout << *prev(ms.end())/2 << " ";
    816 	}
    817 	cout << "\n";
    818 }
    819 
    820 signed main() {
    821 	cin.tie(0) -> sync_with_stdio(0);
    822 	int t = 1;
    823 	cin >> t;
    824 	for(int test = 1; test <= t; test++){
    825 		solve();
    826 	}
    827 }
    828 ```
    829 
    830 **Rate the problem!**
    831 
    832 * Good problem 😁
    833 * Average problem 🤔
    834 * Bad problem 😭
    835 * Did not solve 😴