codeforces-scrape

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

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