2124.md (37770B)
1 Source: https://codeforces.com/blog/entry/144382 2 3 Thanks for participation! We hope you loved the contest. 4 5 #### [2124A - Deranged Deletions](/contest/2124/problem/A) 6 7 Problem Credits: [Lilypad](/profile/Lilypad "Master Lilypad") 8 9 **Hint** 10 11 When is there definitely *not* a solution? 12 13 **Solution** 14 15 First, note that since relative order is preserved no matter which elements are deleted, if $a$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted. 16 17 If $a$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $O(n)$. 18 19 **Code** 20 21 ``` 22 #include <bits/stdc++.h> 23 24 using namespace std; 25 26 void solve(){ 27 int n; 28 29 cin >> n; 30 31 vector<int> arr(n); 32 for(auto &x : arr) cin >> x; 33 34 for(int i = 0; i < n; i++){ 35 for(int j = i + 1; j < n; j++){ 36 if(arr[i] > arr[j]){ 37 cout << "YES\n2\n"; 38 cout << arr[i] << " " << arr[j] << "\n"; 39 return; 40 } 41 } 42 } 43 44 cout << "NO\n"; 45 } 46 47 int main(){ 48 ios_base::sync_with_stdio(false); 49 cin.tie(nullptr); 50 51 int t; 52 cin >> t; 53 while(t--) solve(); 54 } 55 ``` 56 57 **Rate the Problem** 58 59 * Great Problem 60 * Good Problem 61 * Okay Problem 62 * Bad Problem 63 * Did not solve 64 65 #### [2124B - Minimise Sum](/contest/2124/problem/B) 66 67 Problem Credits: [cry](/profile/cry "International Master cry") 68 69 Special thanks to [prvocislo](/profile/prvocislo "Grandmaster prvocislo") for misreading problem G to the statement of this problem, [nifeshe](/profile/nifeshe "Grandmaster nifeshe") for solving it, and [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") for suggesting we use this problem! 70 71 **Hint** 72 73 Write some examples of arrays down. 74 75 **Solution** 76 77 The answer is $\min(a_1,a_2)+a_1$. 78 79 If $a_1 \gt a_2$, we can perform the operation with $i=1$ and $j=2$, so that the prefix minimum after index $2$ will always be $0$ to get $a_1+a_2$ as our answer. 80 81 If $a_1 \lt a_2$, we can perform the operation with $i=2$ and $j=3$. Since $a_1 \lt a_2, min(a_1,a_2)=a_1$. The prefix minimum will be $0$ in index $3$ and later. We should be careful about the edge case $n=2$, as there is no index $3$ we can use. However, if $n=2$, we can simply not perform the operation. 82 83 We can easily show that the above cases are optimal for this problem. The code runs in $O(n)$, bottlenecked by reading the array. 84 85 **Code** 86 87 ``` 88 import sys 89 input = sys.stdin.readline 90 for _ in range(int(input())): 91 n = int(input()) 92 a = list(map(int, input().split())) 93 print(min(2*a[0], a[0] + a[1])) 94 ``` 95 96 **Rate the Problem** 97 98 * Great Problem 99 * Good Problem 100 * Okay Problem 101 * Bad Problem 102 * Did not solve 103 104 #### [2124C - Subset Multiplication](/contest/2124/problem/C) 105 106 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 107 108 **Hint 1** 109 110 Come up with some numbers that $x$ must be a multiple of. 111 112 **Hint 2** 113 114 Take the LCM. Prove its sufficient (optional). 115 116 **Solution** 117 118 First, note that in order for $b$ to be obtainable after an array $a$, each $a_i$ should be a factor of $b_i$. We can find that $x$ must be a multiple of $b_i/gcd(b_i, b_{i+1})$ for each $1 \leq i \lt n$ as a lower bound for the answer. 119 120 Let's prove that these conditions are also sufficient. To do this, let's analyze each pair $(i,i+1)$ separately. We analyze the following cases: 121 122 * if $b_i=a_i\cdot x$ and $b_{i+1}=a_{i+1}\cdot x$, or $b_i=a_i$ and $b_{i+1}=a_{i+1}$: in both cases, the choice of $x$ does not matter. The array is good if $b_i$ divides $b_{i+1}$ initially. 123 * If $b_i=a_i\cdot x$ and $b_{i+1}=a_{i+1}$, then taking the LCM over all $1 \leq i \lt n$ should ensure this case is always correct. 124 * If $b_i=a_i$ and $b_{i+1}=a_{i+1}\cdot x$, then a larger value of $x$ cannot possibly be beneficial, as the product $\frac{a_{i+1}}{a_i}$ decreases. 125 126 Since the problem guarantees $x$ exists, taking the LCM and outputting suffices. The solution runs in $O(n \log{a_i})$. 127 128 **Code** 129 130 ``` 131 import sys 132 input = sys.stdin.readline 133 import math 134 for _ in range(int(input())): 135 n = int(input()) 136 a = list(map(int, input().split())) 137 gcd = 0 138 lcm = 1 139 for i in range(n-1,-1,-1): 140 gcd = math.gcd(gcd, a[i]) 141 lcm = math.lcm(lcm, a[i] // gcd) 142 print(lcm) 143 ``` 144 145 **Bonus** 146 147 Solve the old version of this problem: given the array $b$ (where a solution is no longer guaranteed), output any array $a$ or claim it is not possible to obtain $b$ through a valid array $a$. 148 149 **Rate the Problem** 150 151 * Great Problem 152 * Good Problem 153 * Okay Problem 154 * Bad Problem 155 * Did not solve 156 157 #### [2124D - Make a Palindrome](/contest/2124/problem/D) 158 159 Problem Credits: [satyam343](/profile/satyam343 "Master satyam343") 160 161 **Hint 1** 162 163 Determine which elements you can delete with the operation. 164 165 **Hint 2** 166 167 Come up with a greedy solution that erases as little elements as possible. 168 169 **Solution** 170 171 First, let's come up with some conditions that determines whether erasing an element is possible. 172 173 Claim: as long as the $k-1$ smallest elements remain in the array, we can erase other elements in any way we want. 174 175 Proof: It is obvious why we cannot erase the $k-1$ smallest elements. If we want to erase any other element, we can simply start the following process to determine a pair of $(l,r)$ where we can erase the element: initially, start $l=1$ and $r=n$. Clearly, the element we want to erase is at least the $k$-th smallest element. After that, we can incrementally either increase $l$ or decrease $r$ until the element is exactly the $k$-th smallest. This process should always terminate because after $r-l+1 \lt k$, the element we want to delete is definitely less than the $k$-th smallest. 176 177 Let the $k-1$-th smallest element be $x$. Now, we can categorize each element in the array into three groups: elements less than $x$, elements equal to $x$, and elements greater than $x$. Note there is no point in keeping any elements in the third group, so we can erase them first (by creating a second array $b$ filled with only elements of the first and second groups). Now, we must strategically delete elements of the second group to make a palindrome. Note that we should try to erase as little elements as possible, because we must ensure the number of elements we don't erase is at least $k-1$. We can maintain this process with a two-pointers approach. Initialize $l=1$ and $r=|b|$. Then, if $b_l=b_r$, we can keep both. If $b_l\neq b_r$ and neither elements is $x$, we can conclude it's impossible. If one of $b_l,b_r$ is equal to $x$, we should flag the one equal to $x$ as being deleted and move the pointer. In the end, we can do a final check to ensure we did not erase too many elements. 178 179 The final solution runs in $O(n \log(n))$ due to sorting to find the $k$-th smallest element. 180 181 **Code** 182 183 ``` 184 #include <bits/stdc++.h> 185 using namespace std; 186 187 typedef long long ll; 188 #define all(x) x.begin(), x.end() 189 #define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _; 190 #define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl; 191 192 193 void solve() { 194 int n; cin >> n; 195 int k; cin >> k; 196 vecin(aa, n); 197 if (k == 1) { 198 cout << "YES" << endl; 199 return; 200 } 201 202 vector<int> bb = aa; 203 sort(all(bb)); 204 int cutoff = bb[k - 2]; 205 vector<int> cc; 206 for (auto a : aa) 207 if (a <= cutoff) 208 cc.push_back(a); 209 int spare = cc.size() - k + 1; 210 int L = 0, R = cc.size() - 1; 211 bool bad = false; 212 while (L < R) { 213 if (cc[L] != cc[R]) { 214 if (spare == 0) { 215 bad = true; break; 216 } 217 if (cc[L] == cutoff) { 218 L ++; 219 spare --; 220 } else if (cc[R] == cutoff) { 221 R --; 222 spare --; 223 } else { 224 bad = true; break; 225 } 226 continue; 227 } 228 L ++; 229 R --; 230 } 231 if (bad) { 232 cout << "NO" << endl; 233 } else { 234 cout << "YES" << endl; 235 } 236 } 237 238 int main() { 239 ios_base::sync_with_stdio(false); 240 cin.tie(NULL); 241 int tt = 1; 242 243 cin >> tt; 244 245 while (tt--) solve(); 246 return 0; 247 } 248 ``` 249 250 **Rate the Problem** 251 252 * Great Problem 253 * Good Problem 254 * Okay Problem 255 * Bad Problem 256 * Did not solve 257 258 #### [2124E - Make it Zero](/contest/2124/problem/E) 259 260 Problem Credits: [satyam343](/profile/satyam343 "Master satyam343") 261 262 **Hint 0** 263 264 Solve the $n=3$ case first. 265 266 **Hint 1** 267 268 The answer is either $-1$, $1$, or $2$. 269 270 **Hint 2** 271 272 First, find a construction in $3$. Then, optimize that to be done in $2$ moves. 273 274 **Solution** 275 276 First, let's determine when the answer is $-1$. Let $s$ be the sum of all elements in the array. The answer is $-1$ if: 277 278 * $s$ is odd, or 279 * There exists an element that is greater than half of $s$. 280 281 If neither of the above conditions hold, we can definitely get a solution in finitely many moves by simply subtracting $1$ from the largest element and $1$ from an arbitrary element in one move. 282 283 Let's now solve the $n=3$ case to grab some intuition. There's of course trivial cases where the answer is $1$ (where the first or last element is the sum of the other two). One array we may want to examine is where the second element is the sum of the first and last, like $[1,3,2]$. We can of course solve this in two moves, by setting $a_1$ to $0$ and $a_2$ to $a_3$ on the first move. What about some array where the middle element is less than the sum of the other two? For example, the array $[3,4,3]$. One thing we can try is trying to subtract from $a_1$ and $a_3$ so we can reduce to the $a_1+a_3=a_2$ case. Is this always possible? Turns out, it is always possible as long as $a_2 \lt a_1+a_3$ and $a_1+a_2+a_3$ is even (in this case, we would turn it into $[2,4,2]$ after our first move). We can even optimize it to two moves by combining two moves into one. In the case of $[3,4,3]$, we can transform the array to $[2,2,0]$ after the first move, combining two of the moves. 284 285 It turns out we can generalize the $n=3$ case for any $n$, by simply finding one "pivot" element to act as $a_2$, then letting $a_1$ be the sum of prefix before that and $a_3$ be the sum of suffix after that. Let $pos$ be the unique position in the array where $a_1+a_2+\ldots+a_{pos-1} \lt \frac{s}{2}$ and $a_1+a_2+\ldots+a_{pos}\geq\frac{s}{2}$. Let $x,y,z$ denote $a_1+a_2+\ldots+a_{pos-1}$, $a_{pos}$, and $a_{pos+1}+a_{pos+2}+\ldots+a_n$ respectively. Precisely, our goal is to make $x+z=y$ in the first move after subtracting a non-negative integer $w$ from both $x$ and $y$, make $x=0$ and $z=y$ after the second move, and $x=y=z=0$ after the third. To prove the first move is always possible, note that $x+z-y$ is always even (since sum of all elements in the array is even), and because $y\leq \frac{s}{2}$ implies $x+z\geq\frac{s}{2}$. 286 287 Finally, to optimize this solution to $2$ moves, instead of subtracting $w$ from both $x$ and $z$ in the first move, let's subtract $x$ from the first block, $x-w$ from the second block, and $w$ from the third block. Essentially, we are combining the first two operations into one. 288 289 The solution runs in $O(n)$. 290 291 **Code** 292 293 ``` 294 #include <bits/stdc++.h> 295 296 using namespace std; 297 298 using ll = long long; 299 const ll MOD = 1E9 + 7; 300 const int INF = 1E9; const ll INFLL = 1E18; 301 302 int n; 303 304 int main() { 305 ios_base::sync_with_stdio(false); 306 cin.tie(0); 307 int T; cin >> T; 308 for(int test = 1; test <= T; test++) { 309 cin >> n; 310 vector<ll> a(n); 311 for(int i = 0; i < n; i++) { 312 cin >> a[i]; 313 } 314 ll sum = 0; 315 for(ll i : a) { 316 sum += i; 317 } 318 if(sum % 2) { 319 cout << "-1\n"; 320 continue; 321 } 322 ll mx = 0; 323 for(ll i : a) { 324 mx = max(mx, i); 325 } 326 if(mx * 2 > sum) { 327 cout << "-1\n"; 328 continue; 329 } 330 ll cur = 0; int ind = 0; 331 for(; ind < n; ind++) { 332 if(cur + a[ind] > sum / 2) { 333 ind--; 334 break; 335 } 336 cur += a[ind]; 337 } 338 if(cur == sum / 2) { 339 cout << "1\n"; 340 for(ll i : a) { 341 cout << i << " "; 342 } 343 cout << "\n"; 344 } else { 345 cout << "2\n"; 346 vector<ll> aa(n); 347 ll extra = sum - 2 * cur; 348 aa[ind + 1] = extra / 2; 349 a[ind + 1] -= aa[ind + 1]; 350 extra /= 2; 351 for(int i = n - 1; i > ind + 1 && extra; i--) { 352 if(a[i] >= extra) { 353 aa[i] = extra; 354 a[i] -= extra; 355 extra = 0; 356 } else { 357 aa[i] = a[i]; 358 extra -= a[i]; 359 a[i] = 0; 360 } 361 } 362 for(int i = 0; i < n; i++) { 363 cout << a[i] << " "; 364 } 365 cout << "\n"; 366 for(int i = 0; i < n; i++) { 367 cout << aa[i] << " "; 368 } 369 cout << "\n"; 370 } 371 } 372 } 373 ``` 374 375 **Rate the Problem** 376 377 * Great Problem 378 * Good Problem 379 * Okay Problem 380 * Bad Problem 381 * Did not solve 382 383 #### [2124F1 - Appending Permutations (Easy Version)](/contest/2124/problem/F1) and [2124F2 - Appending Permutations (Hard Version)](/contest/2124/problem/F2) 384 385 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 386 387 Huge thanks to [Benq](/profile/Benq "Legendary Grandmaster Benq") for transforming my original problem (which is solvable using a sequence found in OEIS) to the current problem! 388 389 **Original Problem** 390 391 Given an integer $n$ and no restrictions, count the number of possible arrays you can form $(n \leq 2\cdot 10^5)$. 392 393 **Hint 1** 394 395 Characterize the arrays that we might overcount. 396 397 **Hint 2** 398 399 Optimize the DP using some cumulative sums. 400 401 **Solution** 402 403 **Coming up with a polynomial solution** 404 405 It's clear we need to do some sort of dynamic programming to count for this task. Initially, one may come up with let $dp_i$ be the number of ways to fill completely permutations with total length $i$. 406 407 Unfortunately, one downfall of the above solution is that some arrays are obtainable through many ways: for example, the array $[1,2,1]$ can be constructed with $[1]+[2,1]$ or $[1,2]+[1]$. 408 409 Upon further investigation, we can see that this occurs when we add two identity permutations of size $x$ and $y$ with $x \gt y$, as this can also be counted with a permutation of size $y$ and a shifted permutation of size $x$. We will choose to ban the second option (appending a shifted permutation that starts with $y+1$ when we just added a permutation of size $y$). We can come up with a counterexample to banning two identity permutations (a bigger one following a smaller one) with the array $[1,2,3,1,2,1]$, which can be counted as both $[1,2]+[3,1,2]+[1]$ and $[1]+[2,3,1]+[2,1]$. 410 411 This gives us a $O(n^4)$ solution. Let $dp(i,j)$ be the number of ways to make the sequence from indices $1$ through $i$, such that the last permutation added was an identity permutation of length $j$ (or not an identity permutation if $j=0$). We can build a solution by looping through (index, length of permutation, which cyclic shift to use), and checking if we can add this permutation naively. 412 413 **Optimizing the solution to $O(n^2)$** 414 415 There are several ways to do this part. Below shows one approach. 416 417 First, let's precalculate $chain(i,j)$, which returns the largest integer $k$ such that it is possible to fill numbers $i, i+1, \ldots, i+k-1$ with numbers $j,j+1,\ldots,j+k-1$. We can calculate this as $chain(i,j)=0$ if $a_i\neq j$ is a requirement, and $1+chain(i+1,j+1)$ otherwise. Let 418 419 * $dp(i,j)$ be the number of ways to fill indices $i,i+1,\ldots,n$ such that $a_i=j$ 420 * $dp_2(i)$ be the sum of $dp(i,j)$ over all $1 \leq j \leq n$. 421 * $suff(i,j)$ be the number of ways such that we are ready to insert $j$ to complete the suffix from $i$ to $n$, but without taking into account restrictions. 422 423 We can calculate $suff(i,j)$ as $\sum_{x=i}^n(chain(x,1)\geq j-1)\cdot dp_2(x+j-1)$. Why is this helpful? Let's create an example. Suppose we fix $j=3$, and we have $chain(x,1)\geq 2$ is true for $x=3,4,6$. That is, it's possible to place $1$ and $2$ in positions $(3,4)$, $(4,5)$, and $(6,7)$. Then, we should have $suff(2,3)=dp_2(5)+dp_2(6)+dp_2(8)$. This is because suppose we set $a_2=3$. Then our $suff(2,3)$ means that we can theoretically put $(3,1,2), (3,4,1,2), (3,4,5,6,1,2)$ starting at index $2$, assuming there are no further restrictions. 424 425 Now our actual DP loop: 426 427 * Calculate $suff(i,j)$ as above 428 * Calculate $dp(i,1)$ by looping through all identity permutations we can append at index $i$. Say we are trying to add identity permutation of length $x$. We should add $dp_2(i+x)$ and subtract $dp(i+x,x+1)$ (this is to prevent overcounting as outlined before). 429 * Calculate $dp(i,j)$ for $j \gt 1$ as $suff(i+1,j)-suff(i+1+chain(i,j),j)$. The subtraction is to remove contribution from $suff$ that is not accessible due to constraints on $a_i \neq j$ using our chain array. 430 431 This solution works in $O(n^2+m)$. $m$ was kept low to allow $O(nm+n^2)$ to pass as well. 432 433 **Code** 434 435 ``` 436 #include <bits/stdc++.h> 437 using namespace std; 438 439 const int MOD = 998244353; 440 template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { 441 os << "[ "; 442 for(const auto& elem : vec) { 443 os << elem << " "; 444 } 445 os << "]"; 446 return os; 447 } 448 struct Mint { 449 int v; 450 Mint(long long val = 0) { 451 v = int(val % MOD); 452 if (v < 0) v += MOD; 453 } 454 Mint operator+(const Mint &o) const { return Mint(v + o.v); } 455 Mint operator-(const Mint &o) const { return Mint(v - o.v); } 456 Mint operator*(const Mint &o) const { return Mint(1LL * v * o.v); } 457 Mint operator/(const Mint &o) const { return *this * o.inv(); } 458 Mint& operator+=(const Mint &o) { v += o.v; if (v >= MOD) v -= MOD; return *this; } 459 Mint& operator-=(const Mint &o) { v -= o.v; if (v < 0) v += MOD; return *this; } 460 Mint& operator*=(const Mint &o) { v = int(1LL * v * o.v % MOD); return *this; } 461 Mint pow(long long p) const { 462 Mint a = *this, res = 1; 463 while (p > 0) { 464 if (p & 1) res *= a; 465 a *= a; 466 p >>= 1; 467 } 468 return res; 469 } 470 Mint inv() const { return pow(MOD - 2); } 471 friend ostream& operator<<(ostream& os, const Mint& m) { 472 os << m.v; 473 return os; 474 } 475 }; 476 void solve() { 477 int N, K; 478 cin >> N >> K; 479 480 vector<vector<bool>> banned(N, vector<bool>(N)); 481 for (int i = 0; i < K; ++i) { 482 int x, y; 483 cin >> x >> y; 484 banned[x - 1][y - 1] = true; 485 } 486 487 vector<Mint> tot(N + 1); 488 tot[N] = 1; 489 vector<vector<Mint>> dp(N + 1, vector<Mint>(N + 1)); 490 vector<vector<int>> chain(N + 1, vector<int>(N + 1)); 491 492 for (int i = N - 1; i >= 0; --i) { 493 for (int j = N - 1; j >= 0; --j) { 494 chain[i][j] = 1 + chain[i + 1][j + 1]; 495 if (banned[i][j]) chain[i][j] = 0; 496 } 497 } 498 499 vector<vector<Mint>> ssum(N + 2, vector<Mint>(N + 1)); 500 501 for (int i = N - 1; i >= 0; --i) { 502 for (int j = 0; j <= N - i; ++j) { 503 if (j == 0) { 504 for (int len = 1; len <= N - i; ++len) { 505 bool ok = chain[i][0] >= len; 506 if (!ok) break; 507 dp[i][j] += tot[i + len]; 508 dp[i][j] -= dp[i + len][j + len]; 509 } 510 } else { 511 if (chain[i][j]) { 512 dp[i][j] += ssum[i + 1][j]; 513 if (i + 1 + chain[i][j] <= N) { 514 dp[i][j] -= ssum[i + 1 + chain[i][j]][j]; 515 } 516 } 517 } 518 tot[i] += dp[i][j]; 519 } 520 521 for (int j = 1; j < N; ++j) { 522 ssum[i][j] = ssum[i + 1][j]; 523 if (chain[i][0] >= j) { 524 ssum[i][j] += tot[i + j]; 525 } 526 } 527 } 528 // cout << dp << endl; 529 // cout << ssum << endl; 530 cout << tot[0].v << '\n'; 531 } 532 int main() { 533 ios::sync_with_stdio(false); 534 cin.tie(nullptr); 535 int t; 536 cin >> t; 537 while(t--) { 538 solve(); 539 } 540 541 return 0; 542 } 543 ``` 544 545 **Rate the Problem (F1)** 546 547 * Great Problem 548 * Good Problem 549 * Okay Problem 550 * Bad Problem 551 * Did not solve 552 553 **Rate the Problem (F2)** 554 555 * Great Problem 556 * Good Problem 557 * Okay Problem 558 * Bad Problem 559 * Did not solve 560 561 #### [2124G - Maximise Sum](/contest/2124/problem/G) 562 563 Problem Credits: [cry](/profile/cry "International Master cry") 564 Special thanks to [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") and [Friedrich](/profile/Friedrich "Candidate Master Friedrich") for solving this problem! 565 566 **Hint 0** 567 568 Disregard cost first. Find the maximum sum of prefix minimums. 569 570 **Hint 1** 571 572 Come up with a way to have $O(n)$ $(i,j)$ pairs to test. 573 574 **Hint 2** 575 576 Let $f(a)=\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n)$. Can you come up with a way to solve $q$ queries of what $f(a)$ will be after performing the operation on $(i,j)$? (queries are not persistent here) 577 578 **Solution** 579 580 Let's disregard the cost part of the problem completely and try to solve the problem just for the maximum sum. 581 582 To solve this problem, we make the following observations: 583 584 1. If $i$ is not a prefix minimum, there is no point in using the operation to increase $a_i$. 585 2. If $j$ is not a suffix maximum, there is no point in using the operation to set $a_j:=0$. This is because we can instead use the closest suffix maximum to its right, and the final answer can only be larger. 586 587 Knowing this, let's enumerate $i$. If $i$ is not a prefix minima, we can skip it. Otherwise, there is no point to increasing $a_i$ past the previous prefix minima. Let's enumerate the number that we would like to increase $a_i$ to, and there should be a clear candidate on which suffix maximum to use as $j$. Since each $a_i$ is bounded by $n$, there is only $O(n)$ pairs of $(i,j)$ produced. 588 589 We now have to solve for what the score is after each operation. Suppose we increased $a_i$ to $x$. Let $k$ be the smallest index $k \gt i$ with $a_k\leq x$ ($k$ can be found by using a sparse table and binary search). We can now decompose $score(a)$ into the sum of the following four parts: 590 591 1. The prefix sum up to index $i$ — this can be precomputed easily 592 2. The score from $i$ to $k-1$ — this can be calculated easily as $x\cdot(k-i)$. 593 3. The score from $k$ to $n$ assuming $a_k$ is the prefix minimum. Call this $suffix(k)$. This can be precalculated as well using a monotonic stack. We can find the smallest number $l \gt k$ with $a_l \lt a_k$, then compute the answer as $suffix(l)+a_k\cdot(l-k)$. 594 4. Finally, we have to subtract the contribution from $j$ to $n$ since we set $a_j:=0$. Note that up to index $j$, the minimum $M$ is now $\min(a_1,a_2,\ldots,a_i-1, x, a_{i+1},a_{i+2},\ldots,a_{j-1})$. Now, we can use the same trick — binary search and sparse table to find the first $m\geq j$ with $a_m\leq M$, and subtract $suffix(m)+M(m-j)$ from our count here. 595 596 Now that we have a way to solve the full array, let's solve for all possible costs. 597 598 It can be shown that the same $O(n)$ queries from before will necessarily obtain the correct answers (proof is left as an exercise). Thus, to solve the problem, let's create an array $ans$, and while processing each $(i,j)$ pair, update $ans_{j-i}$. After that, taking the suffix maximum will suffice. 599 600 **Code** 601 602 ``` 603 #ifdef DEBUG 604 #define _GLIBCXX_DEBUG 605 #endif 606 //#pragma GCC optimize("O3") 607 #include<bits/stdc++.h> 608 using namespace std; 609 610 #ifdef DEBUG 611 #include "lib/debug.h" 612 #else 613 #define debug(...) 228 614 #endif 615 616 #define pb push_back 617 618 typedef long long ll; 619 typedef long double ld; 620 621 int n; 622 const int maxN = 1e6 + 10; 623 int a[maxN]; 624 ll best[maxN]; 625 ll pref[maxN]; 626 int sec_mn[maxN]; 627 ll pref_sec[maxN]; 628 int MN[maxN]; 629 int f[maxN]; 630 void solve() { 631 cin >> n; 632 for (int i = 1; i <= n; i++) cin >> a[i]; 633 for (int i = 0; i <= n - 1; i++) { 634 best[i] = 0; 635 } 636 vector<int> suf_max; 637 suf_max.reserve(n); 638 for (int i = n; i >= 1; i--) { 639 if (suf_max.empty() || a[i] > a[suf_max.back()]) { 640 suf_max.emplace_back(i); 641 } 642 } 643 int mn = 1e9; 644 sec_mn[0] = 1e9; 645 MN[0] = 1e9; 646 int ind = -1; 647 for (int i = 1; i <= n; i++) { 648 sec_mn[i] = sec_mn[i - 1]; 649 if (a[i] < mn) { 650 if (ind != -1) { 651 f[ind] = i; 652 } 653 sec_mn[i] = mn; 654 mn = a[i]; 655 ind = i; 656 } 657 else if (a[i] < sec_mn[i]) { 658 sec_mn[i] = a[i]; 659 } 660 MN[i] = mn; 661 pref[i] = pref[i - 1] + mn; 662 pref_sec[i] = pref_sec[i - 1] + sec_mn[i]; 663 } 664 assert(ind != -1); 665 f[ind] = n + 1; 666 best[0] = pref[n]; 667 vector<int> st{n + 1}; 668 a[n + 1] = -1e9; 669 for (int i = n; i >= 1; i--) { 670 if (MN[i - 1] > a[i]) { 671 for (int id: suf_max) { 672 if (id <= i) break; 673 int cur_mn = min(a[i] + a[id], MN[i - 1]); 674 int l = 0; 675 int r = st.size(); 676 while (r - l > 1) { 677 int mid = (l + r) / 2; 678 if (a[st[mid]] <= cur_mn) l = mid; 679 else r = mid; 680 } 681 int upto = min(id - 1, st[l] - 1); 682 ll val = pref[i - 1] + cur_mn * 1LL * (upto - i + 1); 683 // if (i == 3 && id == 5) { 684 // cout << " HI " << endl; 685 // cout << val << " " << cur_mn << " " << upto << endl; 686 // } 687 if (upto + 1 < id) { 688 int upup = min(f[i], id); 689 // if (i == 1 && id == 4) { 690 // cout << val << " ???? " << upup << endl; 691 // } 692 assert(upup - 1 >= upto); 693 val += pref_sec[upup - 1] - pref_sec[upto]; 694 val += pref[id - 1] - pref[upup - 1]; 695 } 696 best[id - i] = max(best[id - i], val); 697 if (a[i] + a[id] >= MN[i - 1]) break; 698 } 699 } 700 while (!st.empty() && a[i] <= a[st.back()]) st.pop_back(); 701 st.emplace_back(i); 702 } 703 for (int i = n - 2; i >= 0; i--) best[i] = max(best[i], best[i + 1]); 704 for (int i = 0; i < n; i++) cout << best[i] << " "; 705 cout << '\n'; 706 } 707 int main() { 708 ios_base::sync_with_stdio(false); 709 cin.tie(nullptr); 710 auto start = std::chrono::high_resolution_clock::now(); 711 #ifdef DEBUG 712 freopen("input.txt", "r", stdin); 713 #endif 714 int tst; 715 cin >> tst; 716 while (tst--) { 717 solve(); 718 } 719 return 0; 720 } 721 ``` 722 723 **Rate the Problem** 724 725 * Great Problem 726 * Good Problem 727 * Okay Problem 728 * Bad Problem 729 * Did not solve 730 731 #### [2124H - Longest Good Subsequence](/contest/2124/problem/H) 732 733 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 734 735 Special thanks to [satyam343](/profile/satyam343 "Master satyam343") for helping with improving the problem, and [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") for the full solution! 736 737 **Hint 1** 738 739 Characterize what a good subsequence is. 740 741 **Hint 2** 742 743 Use a range DP approach and some greedy techniques to find the answer 744 745 **Solution** 746 747 Let's first determine whether a given sequence can be good. We claim that a sequence $b$ is good if for each index $1 \leq i \leq |b|$, if $b_i=x$, then one of the following must be true: 748 749 1. $x=i$ 750 2. $b_x=x$ and $min(b_x,b_{x+1},\ldots,b_i)\geq x$. 751 752 To prove this, we can note that this is necessary by transitivity of $ \gt $, and sufficient as we can construct a permutation (the method of doing so is left as an exercise to the reader). 753 754 Another way of thinking about this is: let $(i,j)$ be an interval where $b_i=i$, $b_j=i$, and there exists no index $k \gt j$ such that $b_k=i$. The condition $b_p \geq i$ should be satisfied for all indices $i \leq p \leq j$. 755 756 Uisng the above, we can construct a range DP solution. Let $dp(i,j)$ be the maximum length of a sequence if $b_{a_i}=a_i$, and we only consider numbers greater than or equal to $a_i$ from $i$ to $j$ while building the subsequence (essentially, this acts as one complete segment). We can initialize $dp(i,i)=a_i$ for each $i$. Then, we can enumerate $i$ from the back, and calculate the answer for each possible $j$. As we travel from $dp(i,j-1)$ to $dp(i,j)$, there are a few cases to consider: 757 758 1. $a_j=a_i$: we can simply add $1$ to $dp(i,j-1)$ to get $dp(i,j)$ as we can append it to our sequence for no cost. 759 2. $a_j \lt a_i$: we cannot append this due to the definition of good, so $dp(i,j)=dp(i,j-1)$. 760 3. $a_j \gt a_i$: Let's use a greedy approach to find where the segment beginning with $a_j$ should start. Clearly, it should start as soon as possible (since the starting point must have length $j$ already, and we cannot append anything less than $j$ before we begin). To do this, maintain a new array $first$ such that $first_k$ holds the smallest index $y$ where $dp(i,y)\geq a_y$ (so it is possible to start another segment with $a_y$ here, since we can delete any elements from a good sequence, and the sequence will still be good). Then, we can make the transition $dp(i,j)=\max(dp(i,j-1), dp(y,j))$. 761 762 The problem is solved in $O(n^2)$ time. 763 764 **Code** 765 766 ``` 767 #include <bits/stdc++.h> 768 using namespace std; 769 #define int short 770 #define INF (int)1e18 771 772 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 773 774 void Solve() 775 { 776 int n; cin >> n; 777 778 vector <int> a(n + 1); 779 for (int i = 1; i <= n; i++){ 780 cin >> a[i]; 781 } 782 783 vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); 784 785 for (int i = n; i >= 1; i--){ 786 vector <int> good(n + 1, -1); 787 int curr = a[i]; 788 789 dp[i][i] = curr; 790 791 for (int j = i + 1; j <= n; j++){ 792 if (a[j] < a[i]){ 793 continue; 794 } 795 796 if (a[j] == a[i]){ 797 curr += 1; 798 dp[i][j] = curr; 799 continue; 800 } 801 802 if (good[a[j]] == -1 && a[j] <= curr + 1){ 803 good[a[j]] = j; 804 } 805 806 if (good[a[j]] != -1){ 807 int idx = good[a[j]]; 808 curr = max(curr, dp[idx][j]); 809 } 810 } 811 } 812 813 // for (int l = 1; l <= n; l++){ 814 // for (int r = l; r <= n; r++){ 815 // if (dp[l][r]) 816 // cout << l << " " << r << " " << dp[l][r] << "\n"; 817 // } 818 // } 819 820 int curr = 0; 821 vector <int> good(n + 1, -1); 822 for (int j = 1; j <= n; j++){ 823 if (good[a[j]] == -1 && a[j] <= curr + 1){ 824 good[a[j]] = j; 825 } 826 827 if (good[a[j]] != -1){ 828 int idx = good[a[j]]; 829 curr = max(curr, dp[idx][j]); 830 } 831 } 832 833 cout << curr << "\n"; 834 } 835 836 int32_t main() 837 { 838 auto begin = std::chrono::high_resolution_clock::now(); 839 ios_base::sync_with_stdio(0); 840 cin.tie(0); 841 int t = 1; 842 // freopen("in", "r", stdin); 843 // freopen("out", "w", stdout); 844 845 cin >> t; 846 for(int i = 1; i <= t; i++) 847 { 848 //cout << "Case #" << i << ": "; 849 Solve(); 850 } 851 auto end = std::chrono::high_resolution_clock::now(); 852 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 853 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 854 return 0; 855 } 856 ``` 857 858 **Rate the Problem** 859 860 * Great Problem 861 * Good Problem 862 * Okay Problem 863 * Bad Problem 864 * Did not solve 865 866 #### [2124I - Lexicographic Partition](/contest/2124/problem/I) 867 868 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") 869 870 **Hint 1** 871 872 Solve the inverse of this problem first. That is, given a permutation $p$, output $f(p)$. 873 874 **Hint 2** 875 876 Analyze the case of $x=[1,2,2,3,3]$. There is no solution to this $x$. Why? 877 878 **Solution** 879 880 Let's first come up with an algorithm to find $b$ given $p$. 881 882 Let $i$ be the first index with $p_i \lt p_1$. We can easily prove that the first subarray cannot go up to index $i$. This is because otherwise, the first element in $b$ will decrease, and this will be lexicographically smaller than a partition that does not include $i$. 883 884 Now, if $i=2$, then of course we should partition $p_1$ by itself. Otherwise, we should find the index $j$ with $1 \leq j \leq i$ and $p_j$ is the maximum element in the segment $[1,i]$, and partition up to $j-1$ (since this maximises the second element, which is what we want to do after maximising the first). We can now continue the process recursively, but assuming that $p_j$ is the front of the array. 885 886 Let's solve the actual problem now. Suppose we have $x_i=k$. Let $j$ be the largest index with $j \lt i$ and $x_j=k-1$. We can show that the sequence we obtain up to $i$ is the sequence up to $j$, plus $p_i$. This means that we can see the input array $b$ as the depths in a tree, where $j$ is the parent of $i$. We make the following observations: 887 888 1. If $x_i-x_{i-1} \gt 1$, then this is a trivial impossible case (the sequence up to $i$ or $i-1$ is invalid). 889 2. What does it mean if $i-j \gt 1$? This means that the sequence up to $i$ is an extension of $j$ (which is more than $1$ index ago), plus one number. From our analysis above, we know this means that all of $p_{j+1},p_{j+2},\ldots,p_i$ is greater than $p_j$, and $p_i$ is the largest of them all. 890 3. What does it mean if $i-j=1$? In this case, we cannot make any conclusions about the comparison of $p_i$ and $p_{i-1}$. Because index $i$ will be included no matter the comparison. 891 4. What does point $2$ mean? Observe the $[1,2,2,3,3]$ case again. Here, we should have $p_1 \lt p_2 \lt p_3$ and $p_3 \lt p_4 \lt p_5$. This implies $p_1 \lt p_2 \lt p_3 \lt p_4 \lt p_5$, but if this were the case then the array $x$ would be $[1,2,2,2,2]$ instead. More formally, looking at the tree, if node $i$ has more than one children, all of its children must have at most one children, or this contradiction will occur. 892 893 Using this, let's come up with a recursive function that traverses this tree and finds the permutation. Let $f(i,j,a,b)$ fill in $p_i,p_{i+1},p_{i+2},\ldots,p_j$ with numbers $a,a+1,a+2,\ldots,b$, where $i$ to $j$ is one full subtree, assuming that $i$ is already filled. First, let's find all direct children of node $i$ — that is all of the indices with $x_k=x_i+1$. If $i$ has more than one child and any of its children has more than one child, this is the impossible case as above. If $i$ has more than one child, then each of its children should have at most one child. First, let's assume that $p_i$ is already the smallest in the entire subtree. Let the sizes of subtrees of children be $b_1,b_2,\ldots,b_y$. We can reserve $b_i$ numbers for each subtree, and set each direct child to the largest number possible in each interval, and call our function recursively. Finally, if there is only one direct child, we can assume that $p_i$ is the largest number in the subtree, and we can assign the direct child to either be the largest or smallest number, depending on the number of children. We can first assign $p_1$ to be either $1$ or $n$ depending on how many indices $x_i=2$ there are, then call the recursive function. This will create the valid permutation. 894 895 **Code** 896 897 ``` 898 #include <bits/stdc++.h> 899 using namespace std; 900 using ll = long long; 901 #define vt vector 902 903 vt<int> solve(const vt<int>& b, vt<vt<int>>& inv) { 904 int n = b.size(); 905 if (inv[1].size() > 1) return {}; 906 907 vt<int> a(n); 908 stack<array<int,5>> s; 909 if (inv[2].size() > 1) { 910 a[0] = 1; 911 s.push({0, n-1, 2, n, 1}); 912 } else { 913 a[0] = n; 914 s.push({0, n-1, 1, n-1, 1}); 915 } 916 917 while (!s.empty()) { 918 auto tp = s.top(); 919 s.pop(); 920 int l = tp[0], r = tp[1], leftNum = tp[2], rightNum = tp[3], ok = tp[4]; 921 if (l == r) continue; 922 if(b[l+1]!=b[l]+1) return {}; 923 int num = b[l] + 1; 924 if (num >= inv.size()) return {}; 925 926 vt<int> nxt; 927 while (inv[num].size() && inv[num].back() > l) { 928 nxt.push_back(inv[num].back()); 929 inv[num].pop_back(); 930 } 931 if (nxt.size()==0) return {}; 932 if(!ok && nxt.size()!=1) return {}; 933 if (nxt.size() == 1) { 934 if (num+1 < inv.size() && inv[num+1].size() > 1 && inv[num+1][inv[num+1].size()-2] > l) { 935 a[nxt[0]] = leftNum++; 936 } else { 937 a[nxt[0]] = rightNum--; 938 } 939 s.push({l+1, r, leftNum, rightNum, 1}); 940 } else { 941 rightNum -= nxt.size(); 942 int nx = rightNum + 1; 943 reverse(nxt.begin(), nxt.end()); 944 int curLeft = leftNum; 945 for (int i = 0; i < (int)nxt.size(); ++i) { 946 int pos = nxt[i]; 947 a[pos] = nx++; 948 int nextInd = (i+1 < (int)nxt.size() ? nxt[i+1] - 1 : r); 949 int sz = nextInd - pos - 1; 950 s.push({pos, nextInd, curLeft, curLeft + sz, 0}); 951 curLeft += sz + 1; 952 } 953 } 954 } 955 956 return a; 957 } 958 959 int main() { 960 ios::sync_with_stdio(false); 961 cin.tie(nullptr); 962 963 int t; 964 cin >> t; 965 while (t--) { 966 int n; 967 cin >> n; 968 vt<int> x(n); 969 for (int i = 0; i < n; ++i) cin >> x[i]; 970 971 vt<vt<int>> inv(n+3); 972 for (int i = 0; i < n; ++i) inv[x[i]].push_back(i); 973 974 auto a = solve(x, inv); 975 if (a.empty()) { 976 cout << "NO\n"; 977 } else { 978 cout << "YES\n"; 979 for (int v : a) cout << v << ' '; 980 cout << "\n"; 981 } 982 } 983 return 0; 984 } 985 ``` 986 987 **Rate the Problem** 988 989 * Great Problem 990 * Good Problem 991 * Okay Problem 992 * Bad Problem 993 * Did not solve