1853.md (43863B)
1 Source: https://codeforces.com/blog/entry/116940 2 3 We hope you enjoyed these problems :) This contest has been in the works for almost a year. 4 5 **About the Authors** 6 7 This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative! 8 9 CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.com/gym/103886). 10 11 **UPD: D1D Editorial have been updated** 12 13 **UPD 2: D1D Editorial now has images by [EmeraldBlock](/profile/EmeraldBlock "Master EmeraldBlock"). As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).** 14 15 #### [1853A - Desorting](/contest/1853/problem/A "Codeforces Round 887 (Div. 2)") 16 17 Problem Credits: [buffering](/profile/buffering "Expert buffering") 18 19 Analysis: [buffering](/profile/buffering "Expert buffering") 20 21 **Hint 1** 22 23 To make $a$ not sorted, we just need to pick one index $i$ so $a_i \gt a_{i + 1}$. How do we do this? 24 25 **Solution** 26 27 To make $a$ not sorted, we just have to make $a_i \gt a_{i + 1}$ for one $i$. 28 29 In one operation, we can reduce the gap between two adjacent elements $i, i + 1$ by $2$ by adding $1$ to $1 \dots i$ and subtracting $1$ from ${i + 1} \dots n$. 30 31 It is clearly optimal to pick the smallest gap between a pair of adjacent elements to minimize the number of operations we have to do. If we have $a_i = x, a_{i + 1} = y$, we can make $x \gt y$ within $\lfloor \frac{(y - x)}{2} \rfloor + 1$ operations. 32 33 Thus, we can just go through $a$, find the minimum difference gap, and calculate the minimum operations using the above formula. Note that if $a$ is not sorted, we can just output $0$. 34 35 The time complexity is $O(n)$. 36 37 **Code (C++)** 38 39 ``` 40 #include <bits/stdc++.h> 41 #include <numeric> 42 using namespace std; 43 44 int main(){ 45 46 ios::sync_with_stdio(false); 47 cin.tie(0); 48 49 int T; cin >> T; 50 51 while (T--) { 52 53 int n; cin >> n; 54 vector<int> nums(n); 55 int diff = 1e9; 56 bool sorted = true; 57 for (int i = 0; i < n; i++) { 58 cin >> nums[i]; 59 if (i > 0) { 60 diff = min(nums[i] - nums[i - 1], diff); 61 sorted &= nums[i] >= nums[i - 1]; 62 } 63 } 64 65 if (!sorted) { 66 cout << 0 << endl; 67 continue; 68 } 69 70 cout << diff/2 + 1 << endl; 71 } 72 } 73 ``` 74 75 #### [1853B - Fibonaccharsis](/contest/1853/problem/B "Codeforces Round 887 (Div. 2)") 76 77 Problem Credits: [ntarsis30](/profile/ntarsis30 "Specialist ntarsis30"), [cry](/profile/cry "Candidate Master cry") 78 79 Analysis: [cry](/profile/cry "Candidate Master cry") 80 81 **Hint 1** 82 83 Can a sequence involving $n$, which is up to $10^5$, really have up to $10^9$ terms? 84 85 **Solution** 86 87 The terms of the fibonacci sequence will increase exponentially. This is quite intuitive, but mathematically, fibonnaci-like sequences will increase at a rate of phi to the power of $n$, where phi (the golden ratio) is about $1.618$. Thus, the maximum number of terms a sequence can have before it reaches $10^9$, or the maximum value of $n$, is pretty small (around $\log n$). 88 89 Instead of trying to fix the first two elements of the sequence and counting how many sequences $s$ will have $s_k = n$, note that we already have $n$ fixed. If we loop over the $k-1$th element of the sequence, the sequence is still fixed. If we know the $x$th element and $x-1$th element of $s$, we can find that $s_{x - 2} = s_{x} - s_{x - 1}$. 90 91 Thus, we can just go backwards and simulate for $k$ iterations in $O(\log n)$ since $k$ is small, breaking at any point if the current sequence is not fibonnaci-like (there are negative elements or it is not strictly increasing). Otherwise, we add $1$ to our answer. 92 93 The time complexity is $O(n \cdot \log n)$. 94 95 **Code (C++)** 96 97 ``` 98 #include <bits/stdc++.h> 99 using namespace std; 100 101 int main() 102 { 103 ios::sync_with_stdio(false); 104 cin.tie(0); 105 106 int T; cin >> T; 107 108 while (T--) { 109 110 int n; int k; 111 cin >> n >> k; 112 113 int ans = 0; 114 115 for (int i = 1; i <= n; i++) { 116 int second = n; //xth element where x is k 117 int first = i; //fixing x-1th element where x is k-1 118 bool valid_seq = true; 119 for (int j = 0; j < k - 2; j++) { 120 //for s_x and s_x-1, s_x-2 = s_x - s_x-1 121 int fx = first; 122 first = second - fx; 123 second = fx; 124 valid_seq &= first <= second; 125 valid_seq &= min(first, second) >= 0; 126 if (!valid_seq) break; //break if the sequence is not fibonacci-like 127 } 128 if (valid_seq) ans++; 129 } 130 131 cout << ans << endl; 132 } 133 134 } 135 ``` 136 137 Bonus: Solve for $n, k \leq 10^9$ 138 139 **Bonus Solution** 140 141 Analysis by [awesomeguy856](/profile/awesomeguy856 "Candidate Master awesomeguy856") 142 143 $f[k] = F_{k-2}f[0]+F_{k-1}f[1]$ 144 145 By the Extended Euclidean Algorithm, we can find one integral solution for this equation, since $\gcd (F_{k-2}, F_{k-1}) = 1 | f[k].$ Let this solution be $(f[0], f[1]) = (x, y).$ Then all other integral solutions are in the form $(x+cF_{k-1}, y-cF_{k-2}),$ for $c \in Z$ so we can find all valid solutions by binary search on $f[1],f[0] \geq 0$ and $f[1] \gt f[0]$, or just by some calculations. 146 147 #### [1852A - Ntarsis' Set](/contest/1852/problem/A "Codeforces Round 887 (Div. 1)") 148 149 Problem Credits: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog") 150 151 Analysis: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog"), [buffering](/profile/buffering "Expert buffering") 152 153 **Hint 1** 154 155 Suppose that the numbers are arranged in a line in increasing order. Take a look at each number $x$ before some day. If it isn't deleted on that day, what new position does it occupy, and how is that impacted by its previous position? 156 157 **Answer** 158 159 If $x$ is between $a_i$ and $a_{i+1}$, it will move to a new position of $x-i$, since $i$ positions before it are deleted. 160 161 **Hint 2** 162 163 Take this observation, and apply it to simulate the process backwards. 164 165 **Solution** 166 167 Suppose the numbers are arranged in a line in increasing order. Consider simulating backwards; instead of deleting the numbers at positions $a_1,a_2,\ldots,a_n$ in each operation, then checking the first number after $k$ operations, we start with the number $1$ at the front, try to insert zeroes right after positions $a_1-1, a_2-2, \ldots, a_{n}-n$ in each operation so that the zeroes will occupy positions $a_1, a_2, \ldots, a_n$ after the insertion, and after $k$ insertions, we will check the position that $1$ will end up at. 168 169 If $a_1$ is not equal to $1$, the answer is $1$. Otherwise, each insertion can be processed in $O(1)$ if we keep track of how many of $a_1-1, a_{2}-2,\ldots,a_{n}-n$ are before the current position $x$ of $1$; if $a_1-1$ through $a_i-i$ are before $x$, then we will insert $i$ zeroes before $x$. 170 171 The time complexity is $O(n+k)$ per test case. The editorial code additionally processes every insertion with the same $i$ value in $O(1)$, for $O(n)$ overall complexity. 172 173 There are alternative solutions using binary search with complexity $O(k\log nk)$ or $O(k\log n\log nk)$, and we allowed them to pass. In fact, this problem was originally proposed with $k \leq 10^9$ but we lowered the constraints. 174 175 **Code (C++) -- Model Solution** 176 177 ``` 178 #include <bits/stdc++.h> 179 using namespace std; 180 181 int n, k, a[200010]; 182 183 void solve() { 184 cin >> n >> k; 185 for (int i = 0; i < n; i++) { 186 cin >> a[i]; 187 a[i] -= i; 188 } 189 if (a[0] != 1) { 190 cout << 1 << "\n"; 191 return; 192 } 193 a[n] = 2e9; 194 //start at position 1, and find what number moves to its position 195 long long ans = 1; 196 int inc = 1; //how many zeroes to insert 197 while (inc < n) { 198 int days = (a[inc] - ans + inc - 1) / inc; 199 if (days >= k){ 200 ans += k * inc; 201 k = 0; 202 break; 203 } 204 ans += days * inc; 205 k -= days; 206 while (a[inc] <= ans) inc++; 207 } 208 ans += 1ll * k * n; 209 cout << ans << "\n"; 210 } 211 212 int main() { 213 ios::sync_with_stdio(0); 214 cin.tie(nullptr); 215 216 int t; cin >> t; 217 while (t--) solve(); 218 } 219 ``` 220 221 **Code (C++) -- Simulation (more readable)** 222 223 ``` 224 #include <bits/stdc++.h> 225 using namespace std; 226 227 using ll = long long; 228 const int inf = 1e9+10; 229 const ll inf_ll = 1e18+10; 230 #define all(x) (x).begin(), (x).end() 231 #define pb push_back 232 #define cmax(x, y) (x = max(x, y)) 233 #define cmin(x, y) (x = min(x, y)) 234 235 #ifndef LOCAL 236 #define debug(...) 0 237 #else 238 #include "../../debug.cpp" 239 #endif 240 241 int main() { 242 ios_base::sync_with_stdio(0); cin.tie(0); 243 int t; cin >> t; 244 while (t--) { 245 ll n, k; cin >> n >> k; 246 vector<ll> a(n); 247 for (int i = 0; i < n; i++) 248 cin >> a[i]; 249 250 ll j = 0, x = 1; 251 while (k--) { 252 while (j < n && a[j] <= x+j) 253 j++; 254 x += j; 255 } 256 257 cout << x << "\n"; 258 } 259 } 260 ``` 261 262 #### [1852B - Imbalanced Arrays](/contest/1852/problem/B "Codeforces Round 887 (Div. 1)") 263 264 Problem Credits: [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog") 265 266 Analysis: [buffering](/profile/buffering "Expert buffering"), [nsqrtlog](/profile/nsqrtlog "Expert nsqrtlog") 267 268 **Hint 1** 269 270 You can solve the problem by picking one number from each pair $(n, -n)$, $(n - 1, -n + 1) \dots$, $(1, -1)$. 271 272 **Hint 2** 273 274 $b_i \gt b_j$ implies $a_i \gt a_j$. 275 276 **Hint 3** 277 278 First, try to determine **one** index in $O(n)$, or determine if that's impossible. 279 280 **Hint 4** 281 282 Sort the array $a$ to optimize the $O(n^2)$ solution. 283 284 **Solution** 285 286 At the start, let $x$ be an index such that $b_x$ has the greatest absolute value. If $b_x$ is negative, we have $a_x=0$, and else $a_x=n$. Moreover, we can't have $a_y=0,a_z=n$ for any indices $y$ and $z$, because that implies $b_y+b_z$ is both positive and negative, contradiction. Hence, the necessary and sufficient condition to check if we can determine an element in array $b$ with maximum absolute value is (there exists an element of array $a$ equal to $0$) xor (there exists an element of array $a$ equal to $n$). Then, we can remove that element and re-calculate the $a$ array, leading to an $O(n^2)$ solution. If the check fails at any moment, there is no valid solution. 287 288 To optimize it further, note that we can sort array $a$ at the start and keep track of them in a deque-like structure. We only need to check the front and end of the deque to see if our key condition holds. Finally, we can use a variable to record the number of positive elements deleted so far and subtract it from the front and end of the deque when checking our condition, so that each check is $O(1)$. The overall complexity becomes $O(n\log n)$ due to sorting. 289 290 **Code (C++)** 291 292 ``` 293 #include <bits/stdc++.h> 294 using namespace std; 295 296 int n, ans[100010]; 297 vector<pair<int,int>> arr; 298 299 void solve() { 300 cin >> n; 301 arr.resize(n); 302 for (int i = 0; i < n; i++) { 303 cin >> arr[i].first; 304 arr[i].second = i; 305 } 306 sort(arr.begin(), arr.end()); 307 int l = 0, r = n - 1, sz = n; 308 while (l <= r) { 309 if ((arr[r].first == n - l) ^ (arr[l].first == n - 1 - r)) { 310 if (arr[r].first == n - l) { 311 ans[arr[r--].second] = sz--; 312 } 313 else { 314 ans[arr[l++].second] = -(sz--); 315 } 316 } 317 else { 318 cout << "NO" << "\n"; 319 return; 320 } 321 } 322 cout << "YES" << "\n"; 323 for (int i = 0; i < n; i++) cout << ans[i] << " "; 324 cout << "\n"; 325 } 326 327 int main() { 328 ios::sync_with_stdio(0); 329 cin.tie(nullptr); 330 331 int t; cin >> t; 332 while(t--) solve(); 333 } 334 ``` 335 336 #### [1852C - Ina of the Mountain](/contest/1852/problem/C "Codeforces Round 887 (Div. 1)") 337 338 Problem Credits: [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem") 339 340 Analysis: [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem"), [EmeraldBlock](/profile/EmeraldBlock "International Master EmeraldBlock"), [GusterGoose27](/profile/GusterGoose27 "Master GusterGoose27") 341 342 **Hint One** 343 344 Suppose you knew in advance how many times each octopus will regenerate. Could you solve the problem then? 345 346 **Solution** 347 348 To make things easier, replace health values of $k$ with health values of $0$, so the goal is to reach $0$ health. Regeneration is now from $0$, which was formerly $k$, to $k-1$, instead of $1$ to $k$, which is now $1$ to $0$. For clarity, create a new array $b$ such that $b[i] = a[i] \% k$. 349 350 Now, instead of letting health values wrap around, we can just initially give each octopus a multiple of $k$ more health. For example, if $k=3$ and an octopus with initially $2$ health regenerates twice, we can pretend it initially had $2 + 2 \cdot 3 = 8$ health. 351 352 Create a new array $c$ storing these new healths. Since all healths will reach $0$, it also represents the number of boulders that will hit each octopus. 353 354 To find the minimum number of boulder throws, represent the health values with a histogram, where the heights of blocks are equal to the values of $c$: 355 356  357 358 Then, erase all vertical borders between blocks. The resulting segments each represent a boulder throw: 359 360  361 362 Intuitively, this should minimize the number of boulders, since any sequence of boulder throws should be rearrangeable into horizontal segments covering this histogram. 363 364 We can easily calculate the number of boulders as the sum of all **positive** adjacent differences, treating the far left and far right as having health $0$. 365 366  367 368 Formally, pad $c$ with an extra $0$ to the left and right (i.e. $c[0] = c[n+1] = 0$) and let the adjacent differences be $d[i] = c[i+1]-c[i]$. We claim the minimum number of boulder throws is $\mathrm{throws} = \sum_{i=0}^n{\max\{d[i],0\}}$. 369 370 * This many is necessary, since if $d[i]$ is positive, octopus $i+1$ gets crushed $d[i]$ more times than octopus $i$, so at least $d[i]$ boulders' ranges have left endpoint $l = i+1$. 371 * This many is achievable, as depicted above. Crush all octopuses with the highest health exactly once (crushing consecutive octopuses with the same boulder), then all octopuses with the new highest health, and so on. Each boulder's range's left endpoint corresponds with part of a positive adjacent difference. 372 373 **Hint 2** 374 375 Can you figure out an $O(n^2)$ solution? And can you improve on it? 376 377 **Hint 3** 378 379 Suppose you already had the optimal solution for the subarray $a[1 \ldots i]$. How could you extend it to $a[1 \ldots i+1]$? 380 381 **Tutorial** 382 383 Read the solution in Hint One before continuing with this tutorial; it provides important definitions. 384 385 To reduce the number of possibilities for each $c[i]$, we prove the following lemma: There exists an optimal choice of $c$ (minimizing $\mathrm{throws}$) where all differences between adjacent $c[i]$ have absolute value less than $k$. 386 387 Intuitively, this is because we can decrease a $c[i]$ by $k$. Formally: 388 389 **Proof of Lemma** 390 391 We can prove this using a monovariant on the sum of all values in $c$. 392 393 Start with an optimal choice of $c$. If there does not exist an $i$ with $\lvert d[i]\rvert \geq k$, we are done. 394 395 Otherwise, choose one such $i$. Without loss of generality, we can assume $d[i]$ is positive, as the problem is symmetrical when flipped horizontally. 396 397 Now, decrease $c[i+1]$ by $k$. This decreases $d[i]$ by $k$ to a still-positive value, which decreases $\mathrm{throws}$ by $k$. This also increases $d[i+1]$ by $k$, which increases $\mathrm{throws}$ by **at most** $k$. Thus, $\mathrm{throws}$ does not increase, so the new $c$ is still optimal. 398 399 We can apply this operation repeatedly on any optimal solution until we do not have any more differences with absolute value $\geq k$. Since each operation decreases the sum of values in $c$ by $k$, this algorithm terminates since the sum of values in $c$ is finite. 400 401 By the previous lemma, if we have determined $c[i]$, there are at most $2$ choices for $c[i+1]$. (There is $1$ choice when $b[i] = b[i+1]$, resulting in $d[i] = 0$, $c[i] = c[i+1]$, effectively merging the two octopuses.) 402 403 We can visualize this as a DAG in the 2D plane over all points $(i,c[i])$ (over all possible choices of $c[i]$). Each point points to the points in the next column that are the closest above and below (if it exists), forming a grid-like shape. Our goal is to find a path of minimum cost from $(0,0)$ to $(n+1,0)$. 404 405 This is the DAG for the second testcase in samples:  406 407 Call each time we choose a $c[i+1] \gt c[i]$ (i.e. positive $d[i]$) an *ascent*. Note that the number of ascents is fixed because each nonzero $d[i]$ is either $x$ or $x+k$ for some fixed negative $x$, and there must be a fixed number of $+k$'s to make the total change from $c[0]$ to $c[n+1]$ zero. 408 409 Each ascent brings the path up to the next "row" of descents. Since these rows slope downwards, the $j$th ascent must take place at or before some index $i_j$, because otherwise $c[i_j+1]$ would be negative. 410 411 We can use the following strategy to find a path which we claim is optimal: 412 413 If we can descend, then we descend. Otherwise, either we ascend, or alternatively, we change a previous descent into an ascent so we can descend here. (This can be further simplified by having a hypothetical "descent" here, so you do not need to compare two possibilities in the implementation.) Now, the best such location for an ascent is the one with **minimum cost.** 414 415 **Proof** 416 417 We show how to improve (or preserve the optimality of) any other path into the one chosen by this strategy. Index the ascents by the order they are chosen by the strategy, not in left-to-right order. 418 419 Let $j$ be the index of first ascent this strategy chooses that is not in the compared path. Besides the $j-1$ matching ascents, the compared path must contain at least $1$ more ascent at or before $i_j$, and because of how the strategy chooses ascents, said ascent(s) must have cost no less than the strategy’s $j$th ascent. Any can be changed to match the strategy, since the matching ascents already guarantee that each of the first $j-1$ ascents in left-to-right order happens early enough. 420 421 Repeating the above operation will obtain the strategy’s path. 422 423 We can implement the above strategy with a priority queue, where for each descent we push on the cost of the corresponding ascent, and when an ascent is required, we then pop off the minimum element. In particular, if $b[i] \lt b[i+1]$, then the corresponding ascent has cost $b[i+1]-b[i]$, while if $b[i] \gt b[i+1]$, it has cost $b[i+1]-b[i]+k$. Also, since the bottom of the DAG corresponds to $c[i] = b[i]$, an ascent is required exactly when $b[i] \lt b[i+1]$. 424 425 **Code (C++)** 426 427 ``` 428 #include <bits/stdc++.h> 429 using namespace std; 430 typedef long long ll; 431 432 void solve() { 433 int n, k; 434 cin >> n >> k; 435 priority_queue<int, vector<int>, greater<int>> differences; 436 int previous = 0; 437 ll ans = 0; 438 for (int i = 0; i < n; i++) { 439 int x; 440 cin >> x; 441 x %= k; 442 if (x > previous) { 443 differences.push(x - previous); 444 ans += differences.top(); 445 differences.pop(); 446 } else { 447 differences.push(k + x - previous); 448 } 449 previous = x; 450 } 451 cout << ans << "\n"; 452 } 453 454 int main() { 455 int t; 456 cin >> t; 457 while (t--) 458 solve(); 459 } 460 ``` 461 462 #### [1852D - Miriany and Matchstick](/contest/1852/problem/D "Codeforces Round 887 (Div. 1)") 463 464 Problem Credits: [ArielShehter](/profile/ArielShehter "Newbie ArielShehter") 465 466 Analysis: [EmeraldBlock](/profile/EmeraldBlock "International Master EmeraldBlock"), [emorgan](/profile/emorgan "International Grandmaster emorgan") 467 468 **Hint 1** 469 470 Solve the samples for all values of $k$. 471 472 **Hint 2** 473 474 What does constructing a second row from left to right look like? 475 476 **Hint 3** 477 478 How does knowing the possible $k$ for any first row help you construct a second row? 479 480 **Hint 4** 481 482 Apply dynamic programming to calculate the possible $k$, and use the information in the DP to construct a solution. 483 484 **Solution** 485 486 Call the number of adjacent pairs of cells with different characters the *cost*. 487 488 If we construct the second row from left to right, the amount each character adds to the cost only depends on the previous character. Thus, we can represent the problem with a DAG whose vertices represent choices for each character and whose edges represent the cost of choosing two adjacent characters. Our goal is to find a path starting from the far left and ending at the far right of cost $k$. For example, below is the DAG for the third testcase in the sample. (For convenience, we include the cost of cells in the top row with the corresponding cells in the bottom row.) 489 490  491 492 A general way to find such a path is as follows: For each vertex, store all possible costs of a path starting from the far left and ending at that vertex, which can be calculated with dynamic programming. Then we construct our path backwards from the right. For each candidate previous vertex, we check that the constructed path's cost plus the cost of the edge from this vertex plus some stored cost in this vertex equals $k$, in which case we know that some completion of the path from the far left to this vertex exists and we can choose this vertex. 493 494 Naively calculating this DP would require $O(n)$ time per operation. However, intuitively, each set of possible costs should contain almost all values between its minimum and maximum, and experiments suggest it always consists of at most two intervals. We will first formalize the DP and then prove this observation. 495 496 Let $\mathrm{dp}_A[i]$ store the set of possible values of $k$ when the grid is truncated to the first $i$ columns and the last character in the second row is $A$. Define $\mathrm{dp}_B[i]$ similarly. 497 498 Using the notation $[\mathrm{true}] = 1$, $[\mathrm{false}] = 0$, $S+x = \{s+x \mid s \in S\}$, we have the recurrences 499 500 $\begin{align*} \mathrm{dp}_A[i] &= \mathrm{dp}_A[i-1]\cup(\mathrm{dp}_B[i-1]+1)+[s_i \ne A]+[s_i \ne s_{i-1}] \\ \mathrm{dp}_B[i] &= \mathrm{dp}_B[i-1]\cup(\mathrm{dp}_A[i-1]+1)+[s_i \ne B]+[s_i \ne s_{i-1}] \end{align*}$ 501 502 with initial values $\mathrm{dp}_A[1] = [s_1 \ne A]$ and $\mathrm{dp}_B[1] = [s_1 \ne B]$. 503 504 Now either we hope that each set consists of $O(1)$ intervals, or we have to prove that each set indeed consists of at most two intervals: 505 506 **Proof** 507 508 We will use induction to prove that the following stronger property holds for all $i \ge 2$: $\mathrm{dp}_A[i]$ and $\mathrm{dp}_B[i]$ are overlapping intervals, except that possibly one (non-endpoint) value $v$ is missing from one interval, but in that case either $v-1$ or $v+1$ is present in the other interval. ($i = 1$ must be treated separately, but it can easily be checked.) 509 510 **Base case.** To prove this holds for $i = 2$, WLOG let $s_1 = A$ so $\mathrm{dp}_A[1] = \{0\}$ and $\mathrm{dp}_B[1] = \{1\}$. If $s_2 = A$, then 511 512 $\begin{align*} \mathrm{dp}_A[2] &= \{0\}\cup(\{1\}+1)+0+0 = \{0,2\} \\ \mathrm{dp}_B[2] &= \{1\}\cup(\{0\}+1)+1+0 = \{2\} \end{align*}$ 513 514 which satisfies the property with $v = 1$. If $s_2 = B$, then 515 516 $\begin{align*} \mathrm{dp}_A[2] &= \{0\}\cup(\{1\}+1)+1+1 = \{2,4\} \\ \mathrm{dp}_B[2] &= \{1\}\cup(\{0\}+1)+0+1 = \{2\} \end{align*}$ 517 518 which satisfies the property with $v = 3$. 519 520 **Induction step.** Suppose the property holds for $i-1$. 521 522 Since the conditions of the property only depend on relative positions, for convenience we shift the sets $\mathrm{dp}_A[i]$ and $\mathrm{dp}_B[i]$ left by $h = [s_i \ne A]+[s_i \ne s_{i-1}]$ to get 523 524 $\begin{align*} \mathrm{dp}'_A[i] &= \mathrm{dp}_A[i]-h = \mathrm{dp}_A[i-1]\cup(\mathrm{dp}_B[i-1]+1) \\ \mathrm{dp}'_B[i] &= \mathrm{dp}_B[i]-h = \mathrm{dp}_B[i-1]\cup(\mathrm{dp}_A[i-1]+1)+(s_i = A\ ?\ 1 : -1). \end{align*}$ 525 526 If the property holds for $\mathrm{dp}'$, then it holds for $\mathrm{dp}$. 527 528 First, we show that a missing value in $\mathrm{dp}'_A[i]$ or $\mathrm{dp}'_B[i]$ can only come directly from a missing value in $\mathrm{dp}_A[i-1]$ or $\mathrm{dp}_B[i-1]$ and not from the union operation merging two non-adjacent intervals. This is true because $\mathrm{dp}_A[i-1]$ and $\mathrm{dp}_B[i-1]$ overlap, so even after $1$ is added to either, they are still at least adjacent. 529 530 If a value $v$ is missing, WLOG let it be missing from $\mathrm{dp}_A[i-1]$. 531 532 * If $v+1 \in \mathrm{dp}_B[i-1]$, then $\mathrm{dp}'_A[i]$ may be missing $v$ while $\mathrm{dp}'_B[i]$ does not miss any value. Also, since $v-1$ is adjacent to the missing value (which isn't an endpoint), it is in $\mathrm{dp}_A[i-1]$, so either $v+1$ or $v-1$ is in $\mathrm{dp}'_B[i]$. This also guarantees the intervals overlap, satisfying the property for $i$. 533 * The case for $v-1 \in \mathrm{dp}_B[i-1]$ is very similar. $\mathrm{dp}'_B[i]$ may be missing either $v$ or $v+2$, and since $v+1 \in \mathrm{dp}_A[i-1]$, $v+1$ is in $\mathrm{dp}'_A[i]$. 534 535 If no value is missing, let $x$ be a common value in both $\mathrm{dp}_A[i-1]$ and $\mathrm{dp}_B[i-1]$. Then, $\mathrm{dp}'_A[i] \supseteq \{x,x+1\}$ and $\mathrm{dp}'_B[i]$ is a superset of either $\{x-1,x\}$ or $\{x+1,x+2\}$, so the intervals overlap. 536 537 To find the union of two sets of intervals, sort them by left endpoint and merge adjacent overlapping intervals. After computing the DP, apply the aforementioned backwards construction to obtain a valid second row. 538 539 Below is a visualization of solving the third testcase in the sample. Generate your own [here](https://artofproblemsolving.com/texer/codeforces)! 540 541  542 543 **Code (C++)** 544 545 ``` 546 #include <bits/stdc++.h> 547 using namespace std; 548 549 #define all(x) (x).begin(), (x).end() 550 551 struct state { 552 553 // represents a set of integers compressed as a vector 554 // of non-overlapping intervals [l, r] 555 556 basic_string<array<int, 2>> a; 557 558 // add d to everything in the set 559 friend state add(state x, int d) { 560 for (auto& [l, r] : x.a) 561 l += d, r += d; 562 return x; 563 } 564 565 // union of two sets of integers 566 friend state unite(state x, state y) { 567 state z; 568 merge(all(x.a), all(y.a), back_inserter(z.a)); 569 int j = 0; 570 for (int i = 1; i < z.a.size(); i++) { 571 if (z.a[i][0] <= z.a[j][1]+1) 572 z.a[j][1] = max(z.a[j][1], z.a[i][1]); 573 else 574 z.a[++j] = z.a[i]; 575 } 576 z.a.erase(z.a.begin() + j + 1, z.a.end()); 577 return z; 578 } 579 580 // whether integer k is in the set 581 friend bool contains(state x, int k) { 582 for (auto& [l, r] : x.a) 583 if (k >= l && k <= r) 584 return true; 585 return false; 586 } 587 }; 588 589 // set containing only one integer d 590 state from_constant(int d) { 591 return state({{{d, d}}}); 592 } 593 594 int main() { 595 ios_base::sync_with_stdio(0); cin.tie(0); 596 int t; cin >> t; 597 while (t--) { 598 int n, k; cin >> n >> k; 599 string s; cin >> s; 600 601 vector<array<state, 2>> dp(n); 602 603 dp[0][0] = from_constant(s[0] != 'A'); 604 dp[0][1] = from_constant(s[0] != 'B'); 605 606 for (int i = 1; i < n; i++) { 607 dp[i][0] = add(unite(dp[i-1][0], add(dp[i-1][1], 1)), (s[i] != 'A') + (s[i] != s[i-1])); 608 dp[i][1] = add(unite(dp[i-1][1], add(dp[i-1][0], 1)), (s[i] != 'B') + (s[i] != s[i-1])); 609 } 610 611 if (!(contains(dp[n-1][0], k) || contains(dp[n-1][1], k))) { 612 cout << "NO\n"; 613 continue; 614 } 615 616 string ans; 617 618 for (int i = n-1; i >= 0; i--) { 619 char c = contains(dp[i][0], k - (i == n-1 ? 0 : (ans.back() != 'A'))) ? 'A' : 'B'; 620 k -= (c != s[i]); 621 if (i > 0) 622 k -= (s[i] != s[i-1]); 623 if (i < n-1) 624 k -= (c != ans.back()); 625 ans += c; 626 } 627 628 reverse(all(ans)); 629 cout << "YES\n" << ans << "\n"; 630 } 631 } 632 ``` 633 634 #### [1852E - Rivalries](/contest/1852/problem/E "Codeforces Round 887 (Div. 1)") 635 636 Problem Credits: [buffering](/profile/buffering "Expert buffering"), [ArielShehter](/profile/ArielShehter "Newbie ArielShehter"), [fast-fourier-transfem](/profile/fast-fourier-transfem "Candidate Master fast-fourier-transfem") 637 638 Analysis: [oursaco](/profile/oursaco "Master oursaco") 639 640 **Hint 1** 641 642 For each distinct value, only the leftmost and rightmost positions actually have an effect on the power. 643 644 **Hint 2** 645 646 Think of each distinct value as an interval corresponding to its leftmost and rightmost positions, and let that distinct value be the value of its interval. If interval $x$ strictly contains an interval $y$ with greater value, then $x$ will not have an effect on the power and it can be discarded. 647 648 **Hint 3** 649 650 In order to not change the power, we can only add intervals that strictly contain an interval with greater value. Afterwards, if $i$ is not the endpoint of an interval, $b_i$ equals the largest value of an interval containing $i$. 651 652 **Hint 4** 653 654 There will only be at most one interval that we have to add. Assume that there are multiple intervals that we can add without changing the answer. In this case it is easy to see that its more optimal to combine the interval with smaller value into the interval with larger value. Thus, it is never optimal to add multiple intervals. 655 656 **Solution** 657 658 Read the hints. 659 660 We can remove all intervals that will not affect the power by iterating over them in decreasing order of value and maintain a segment tree that stores for each left endpoint of any processed intervals, the right endpoint that corresponds to it. Checking if an interval is strictly contained then becomes a range minimum query. 661 662 Assume that we know the value $x$ of the interval that we want to add. We can immediately fill the value for the interior of all intervals that correspond to a value greater than $x$. However, we also have to guarantee that $x$ is strictly contained by an interval with greater value, so we can try each interval to contain $x$. If are no unfilled indices the left or right side of the interval, then we want to replace the smallest filled on either side value with $x$. Otherwise, we can just fill in all the unfilled indices with $x$. Note that it is also possible for $x$ to not be able to be contained by any interval. 663 664 Thus, we can just try every possible $x$ in decreasing order and maintain the filled indices as we iterate. There are only at most $n$ values of $x$ to check, which is just the set of $a_i - 1$ that does not appear in $a$. 665 666 **Code (C++)** 667 668 ``` 669 #include <bits/stdc++.h> 670 using namespace std; 671 672 #define pb push_back 673 #define ff first 674 #define ss second 675 676 typedef long long ll; 677 typedef pair<int, int> pii; 678 typedef pair<ll, ll> pll; 679 680 const int INF = 1e9 + 1; 681 682 void setIO() { 683 ios_base::sync_with_stdio(0); cin.tie(0); 684 } 685 686 pii seg[400005]; 687 int n; 688 689 void build(int l = 0, int r = n - 1, int cur = 0){ 690 seg[cur] = {INF, INF}; 691 if(l == r) return; 692 int mid = (l + r)/2; 693 build(l, mid, cur*2 + 1); 694 build(mid + 1, r, cur*2 + 2); 695 } 696 697 void update(int x, int v, int l = 0, int r = n - 1, int cur = 0){ 698 if(l == r){ 699 seg[cur] = {v, l}; 700 return; 701 } 702 int mid = (l + r)/2; 703 if(x <= mid) update(x, v, l, mid, cur*2 + 1); 704 else update(x, v, mid + 1, r, cur*2 + 2); 705 seg[cur] = min(seg[cur*2 + 1], seg[cur*2 + 2]); 706 } 707 708 pii query(int l, int r, int ul = 0, int ur = n - 1, int cur = 0){ 709 if(l <= ul && ur <= r) return seg[cur]; 710 if(l > r || ur < l || ul > r) return {INF, INF}; 711 int mid = (ul + ur)/2; 712 return min(query(l, r, ul, mid, cur*2 + 1), query(l, r, mid + 1, ur, cur*2 + 2)); 713 } 714 715 int main(){ 716 setIO(); 717 int t; 718 cin >> t; 719 for(int tt = 1; tt <= t; tt++){ 720 cin >> n; 721 map<int, vector<int>> m; 722 int arr[n]; 723 for(int i = 0; i < n; i++){ 724 cin >> arr[i]; 725 m[arr[i]].pb(i); 726 } 727 vector<int> rel; //relevant numbers 728 for(auto &i : m){ 729 rel.pb(i.ff); 730 for(int j = 1; j < i.ss.size() - 1; j++){ 731 arr[i.ss[j]] = 0; 732 } 733 } 734 reverse(rel.begin(), rel.end()); 735 vector<int> nw; 736 build(); 737 for(int i : rel){ 738 int l = m[i].front(), r = m[i].back(); 739 if(query(l, r).ff <= r){ 740 arr[l] = arr[r] = 0; 741 } else { 742 update(l, r); 743 nw.pb(i); 744 } 745 } 746 swap(rel, nw); 747 set<int> s; 748 for(int i = 0; i < n; i++) if(!arr[i]) s.insert(i); 749 vector<int> vals; //possible target values 750 for(int i = rel.size() - 1; i >= 0; i--){ 751 if(i == rel.size() - 1 || rel[i] - 1 != rel[i + 1]){ 752 vals.pb(rel[i] - 1); 753 } 754 } 755 ll sum = 0, mx = 0, mxval = 0; 756 int lex = -1, rex = -1; 757 build(); 758 for(int i = 0; i < n; i++) if(!arr[i]) update(i, -1); 759 reverse(vals.begin(), vals.end()); 760 queue<pii> upd; 761 int ind = 0; 762 //try to add an interval with value i 763 for(int i : vals){ 764 vector<int> nxt; 765 //try filling in all intervals > i 766 while(ind < rel.size() && rel[ind] > i){ 767 int l = m[rel[ind]].front(), r = m[rel[ind]].back(); 768 set<int>::iterator it = s.lower_bound(l); 769 while(it != s.end() && *it < r){ 770 sum += rel[ind]; 771 update(*it, rel[ind]); 772 upd.push({*it, rel[ind]}); 773 it = s.erase(it); 774 } 775 nxt.pb(rel[ind++]); 776 } 777 //try each necessary interval to be strictly contained by i 778 for(int j : nxt){ 779 int l = m[j].front(), r = m[j].back(); 780 if(s.size() && 0 < l && r < n - 1){ 781 //find which indeces on each side to replace with i 782 pii rnw = query(r + 1, n); 783 pii lnw = query(0, l - 1); 784 if(rnw.ff == INF || lnw.ff == INF) continue; 785 ll add = (ll)i*s.size() + (rnw.ff == -1 ? 0 : i - rnw.ff) + (lnw.ff == -1 ? 0 : i - lnw.ff); 786 if(i && sum + add > mx){ 787 mx = sum + add; 788 mxval = i; 789 lex = (lnw.ff == -1 ? -1 : lnw.ss); 790 rex = (rnw.ff == -1 ? -1 : rnw.ss); 791 //it is optimal to fill in all intervals > i 792 while(!upd.empty()){ 793 arr[upd.front().ff] = upd.front().ss; 794 upd.pop(); 795 } 796 } 797 } 798 } 799 } 800 //don't want to add any intervals 801 if(s.size() == 0 && sum > mx){ 802 mx = sum; 803 lex = rex = -1; 804 //it is optimal to fill in all remaining intervals 805 while(!upd.empty()){ 806 arr[upd.front().ff] = upd.front().ss; 807 upd.pop(); 808 } 809 } 810 if(lex != -1) arr[lex] = 0; 811 if(rex != -1) arr[rex] = 0; 812 for(int i = 0; i < n; i++) cout << (arr[i] ? arr[i] : mxval) << " "; 813 cout << endl; 814 } 815 } 816 ``` 817 818 #### [1852F - Panda Meetups](/contest/1852/problem/F "Codeforces Round 887 (Div. 1)") 819 820 Problem Credits: [Benq](/profile/Benq "Legendary Grandmaster Benq") 821 822 Analysis: [Benq](/profile/Benq "Legendary Grandmaster Benq"), [oursaco](/profile/oursaco "Master oursaco") 823 824 **Hint 1** 825 826 If we want to answer one of the questions (say, the question involving all the events) in polynomial time, how do we do it? 827 828 **Hint 2** 829 830 Construct a network with edges from the source to each of the red panda events with capacities equal to the number of red pandas, edges from red panda events to blue panda events with innite capacities if the red pandas can catch the corresponding blue pandas, and edges from each of the blue panda events to the sink with capacities equal to the number of blue pandas. 831 832 **Hint 3** 833 834 The next step is to use the max-flow min-cut theorem: the maximum flow is equal to the minimum number of red pandas plus blue pandas we need to remove from the graph such that no remaining red panda can reach any remaining blue panda. 835 836 How do we go from here? 837 838 **Hint 4** 839 840 For any cut, consider the region of the $x$-$t$ plane reachable by the remaining red pandas. No remaining blue pandas can lie in this region, and its border is a polyline that intersects each vertical line in the $x$-$t$ plane exactly once. Furthermore, the slope of every segment in this polyline has slope plus or minus $1$. Conversely, we can associate every polyline satisfying this condition with a cut; we just need to remove every red panda lying below the polyline and every blue panda lying on or above the polyline. 841 842 Now, figure out how to answer the queries online. 843 844 **Solution** 845 846 Read the hints to understand the solution better. 847 848 We can answer the queries online. For each $x$-coordinate $x$, maintain a treap that stores for every $x$-coordinate, the minimum cut $dp[x][t]$ associated with a polyline satisfying the condition above that starts at $x = -\infty$ and ends at $(x, t)$ when only considering events with $x$-coordinate at most $x$. When transitioning from to $x$ to $x+1$, we need to set for every $dp[x+1][t] = min(dp[x][t-1], dp[x][t], dp[x][t+1])$ for every $t$. To do this quickly, we maintain the values of $t$ where $dp[x][t+1] - dp[x][t] \neq 0$ in increasing order, of which there are at most $n$. When $x$ increases by one, each value of increases or decreases by one, depending on the sign of $dp[x][t+1]-dp[x][t]$, and some of the values of $t$ merge, decreasing the size of our treap. As long as we can process each merge in $\log n$ time, our solution will run in $O(n\log n)$ total time. When processing an event, we need to increase all $dp$ values in a suffix for red panda events, and all $dp$ values in a prefix for blue panda events. To answer a query, we just need to return the minimum prefix sum in our treap. 849 850 **Code (C++)** 851 852 ``` 853 #include <bits/stdc++.h> 854 using namespace std; 855 856 #define pb push_back 857 #define ff first 858 #define ss second 859 860 typedef long long ll; 861 typedef pair<int, int> pii; 862 typedef pair<ll, ll> pll; 863 864 const int INF = 1e9 + 1; 865 866 void setIO() { 867 ios_base::sync_with_stdio(0); cin.tie(0); 868 } 869 870 struct node { 871 //mnpos - leftmost negative 872 //mxpos - rightmost positive 873 int pos, tag, mnpos, mxpos; 874 //minimum distance 875 pair<int, pii> mndif; 876 ll sum, pre, val; 877 int weight; 878 879 node(){} 880 881 node(int pos_, ll val_){ 882 pos = pos_; 883 val = val_; 884 sum = val; 885 pre = min((ll)0, val); 886 mxpos = -INF; 887 mnpos = INF; 888 mndif = {INF, {INF, INF}}; 889 if(val > 0) mxpos = pos; 890 if(val < 0) mnpos = pos; 891 tag = 0; 892 weight = rand(); 893 } 894 }; 895 896 int sz = 1; 897 node treap[1000005]; 898 int left0[1000005]; 899 int right0[1000005]; 900 901 int newnode(int pos, ll val){ 902 treap[sz] = node(pos, val); 903 return sz++; 904 } 905 906 pair<int, pii> comb(int a, int b){ 907 if(a == -INF || b == INF) return {INF, {INF, INF}}; 908 return {b - a, {a, b}}; 909 } 910 911 void pull(int x){ 912 treap[x].sum = treap[x].val; 913 treap[x].pre = min((ll)0, treap[x].val); 914 treap[x].mxpos = -INF; 915 treap[x].mnpos = INF; 916 treap[x].mndif = {INF, {INF, INF}}; 917 if(treap[x].val > 0) treap[x].mxpos = treap[x].pos; 918 if(treap[x].val < 0) treap[x].mnpos = treap[x].pos; 919 if(left0[x]){ 920 treap[x].mndif = min(treap[x].mndif, treap[left0[x]].mndif); 921 treap[x].mndif = min(treap[x].mndif, comb(treap[left0[x]].mxpos, treap[x].mnpos)); 922 treap[x].mnpos = min(treap[x].mnpos, treap[left0[x]].mnpos); 923 treap[x].mxpos = max(treap[x].mxpos, treap[left0[x]].mxpos); 924 treap[x].pre = min(treap[left0[x]].pre, treap[left0[x]].sum + treap[x].pre); 925 treap[x].sum += treap[left0[x]].sum; 926 } 927 if(right0[x]){ 928 treap[x].mndif = min(treap[x].mndif, treap[right0[x]].mndif); 929 treap[x].mndif = min(treap[x].mndif, comb(treap[x].mxpos, treap[right0[x]].mnpos)); 930 treap[x].mnpos = min(treap[x].mnpos, treap[right0[x]].mnpos); 931 treap[x].mxpos = max(treap[x].mxpos, treap[right0[x]].mxpos); 932 treap[x].pre = min(treap[x].pre, treap[x].sum + treap[right0[x]].pre); 933 treap[x].sum += treap[right0[x]].sum; 934 } 935 } 936 937 int move(node& x, int shift){ 938 int ret = x.pos; 939 if(x.val < 0) ret -= shift; 940 if(x.val > 0) ret += shift; 941 return ret; 942 } 943 944 void apply(int x, int tag){ 945 treap[x].pos = move(treap[x], tag); 946 treap[x].tag += tag; 947 if(treap[x].mnpos != INF) treap[x].mnpos -= tag; 948 if(treap[x].mxpos != -INF) treap[x].mxpos += tag; 949 if(treap[x].mndif.ff != INF){ 950 treap[x].mndif.ff -= 2*tag; 951 treap[x].mndif.ss.ff += tag; 952 treap[x].mndif.ss.ss -= tag; 953 } 954 } 955 956 void push(int x){ 957 if(!treap[x].tag) return; 958 if(left0[x]) apply(left0[x], treap[x].tag); 959 if(right0[x]) apply(right0[x], treap[x].tag); 960 treap[x].tag = 0; 961 } 962 963 int merge(int a, int b){ 964 if(!a) return b; 965 if(!b) return a; 966 if(treap[a].weight < treap[b].weight){ 967 push(a); 968 right0[a] = merge(right0[a], b); 969 pull(a); 970 return a; 971 } else { 972 push(b); 973 left0[b] = merge(a, left0[b]); 974 pull(b); 975 return b; 976 } 977 } 978 979 //splits rt's tree into [0, k) [k, INF) 980 pair<int, int> split(int x, int k){ 981 if(!x) return pair<int, int>{0, 0}; 982 push(x); 983 pair<int, int> ret; 984 if(treap[x].pos < k){ 985 ret = split(right0[x], k); 986 right0[x] = ret.first; 987 ret.first = x; 988 } else { 989 ret = split(left0[x], k); 990 left0[x] = ret.second; 991 ret.second = x; 992 } 993 pull(x); 994 return ret; 995 } 996 997 int rt = 0; 998 999 void erase(int x){ 1000 pair<int, int> a = split(rt, x); 1001 pair<int, int> b = split(a.second, x + 1); 1002 rt = merge(a.first, b.second); 1003 } 1004 1005 //position, value 1006 void insert(int a, ll b){ 1007 if(!rt){ 1008 rt = newnode(a, b); 1009 return; 1010 } 1011 pair<int, int> nw = split(rt, a); 1012 rt = merge(nw.first, merge(newnode(a, b), nw.second)); 1013 } 1014 1015 //value 1016 ll query(int x){ 1017 pair<int, int> a = split(rt, x); 1018 pair<int, int> b = split(a.second, x + 1); 1019 ll ret = (b.first ? treap[b.first].val : 0); 1020 rt = merge(a.first, merge(b.first, b.second)); 1021 return ret; 1022 } 1023 1024 int main(){ 1025 setIO(); 1026 int n; 1027 cin >> n; 1028 int prv = 0; 1029 ll st = 0; 1030 for(int i = 1; i <= n; i++){ 1031 int x, t, c; 1032 cin >> x >> t >> c; 1033 int dif = x - prv; 1034 //remove overlap 1035 while(rt && treap[rt].mndif.ff <= 2*dif){ 1036 pair<int, pii> x = treap[rt].mndif; 1037 ll a = query(x.ss.ff), b = query(x.ss.ss); 1038 ll sub = min(a, -b); 1039 erase(x.ss.ff); 1040 erase(x.ss.ss); 1041 a -= sub, b += sub; 1042 if(a != 0) insert(x.ss.ff, a); 1043 if(b != 0) insert(x.ss.ss, b); 1044 } 1045 //shift everything 1046 if(rt){ 1047 treap[rt].pos = move(treap[rt], dif); 1048 treap[rt].tag += dif; 1049 if(treap[rt].mnpos != INF) treap[rt].mnpos -= dif; 1050 if(treap[rt].mxpos != -INF) treap[rt].mxpos += dif; 1051 if(treap[rt].mndif.ff != INF){ 1052 treap[rt].mndif.ff -= 2*dif; 1053 treap[rt].mndif.ss.ff += dif; 1054 treap[rt].mndif.ss.ss -= dif; 1055 } 1056 } 1057 ll cur = query(t + 1); 1058 if(cur != 0) erase(t + 1); 1059 if(cur - c != 0) insert(t + 1, cur - c); 1060 if(c > 0) st += c; 1061 cout << st + (!rt ? 0 : treap[rt].pre) << endl; 1062 prv = x; 1063 } 1064 } 1065 ```