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 😴