codeforces-scrape

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

2171.md (24376B)


      1 Source: https://codeforces.com/blog/entry/148567
      2 
      3 I hope you all enjoyed the contest! Special thanks to
      4 
      5 * [djm03178](/profile/djm03178 "Master djm03178") for suggesting the inclusion of C1, and for helping with test writing on all problems, especially F
      6 * [satyam343](/profile/satyam343 "Master satyam343") for helping me solve H
      7 * [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069") for providing the idea for one of the solutions to E
      8 * [Intellegent](/profile/Intellegent "Grandmaster Intellegent") for providing one of the proofs for the solution to D, and for providing the idea for one of the solutions to F
      9 
     10 **Rate the contest!**
     11 
     12 **Quality**
     13 
     14 * Excellent contest
     15 * Good contest
     16 * Average contest
     17 * Bad contest
     18 * Horrible contest
     19 
     20 **Difficulty**
     21 
     22 * Trivial contest
     23 * Easy contest
     24 * Average contest
     25 * Hard contest
     26 * Impossible contest
     27 
     28 #### [A — Shizuku Hoshikawa and Farm Legs](https://codeforces.com/contest/2171/problem/A)
     29 
     30 **Solution**
     31 
     32 **Step 1**
     33 
     34 If $n$ is odd, there are clearly zero possible configurations.
     35 
     36 **Step 2**
     37 
     38 Suppose $n$ is even. Then consider the number of legs that belong to cows. This can be any multiple of $4$ that is less than or equal to $n$. The remaining legs will belong to chickens. Thus, the answer is equal to the number of nonnegative multiples of $4$ which are less than or equal to $n$, which is given by $\lfloor \frac{n}{4} \rfloor + 1$.
     39 
     40 **Code (C++)**
     41 
     42 ```
     43 #include <bits/stdc++.h>
     44 using namespace std;
     45  
     46 void solve(){
     47     int n;
     48     cin >> n;
     49     cout << (n & 1 ? 0 : n/4+1) << '\n';
     50 }
     51  
     52 int main(){
     53     ios::sync_with_stdio(false);
     54     cin.tie(NULL);
     55     int t;
     56     cin >> t;
     57     while(t--) solve();
     58 }
     59 ```
     60 
     61 **Rate the problem!**
     62 
     63 **Quality**
     64 
     65 * Excellent problem
     66 * Good problem
     67 * Average problem
     68 * Bad problem
     69 * Horrible problem
     70 
     71 **Difficulty**
     72 
     73 * Trivial problem
     74 * Easy problem
     75 * Average problem
     76 * Hard problem
     77 * Impossible problem
     78 
     79 #### [B — Yuu Koito and Minimum Absolute Sum](https://codeforces.com/contest/2171/problem/B)
     80 
     81 **Solution**
     82 
     83 **Step 1**
     84 
     85 The given expression is equal to $|(a_2 - a_1) + (a_3 - a_2) + \dots + (a_n - a_{n-1})|$.
     86 
     87 **Step 2**
     88 
     89 This simplifies to $|a_n - a_1|$.
     90 
     91 **Step 3**
     92 
     93 We want to minimize the absolute difference between the first and last elements. To do so, if one of them is set and the other one isn't, we will set them to be equal. Now, the remaining blank elements do not affect the given expression, so we can set them all to be zero.
     94 
     95 **Code (C++)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 using namespace std;
    100  
    101 void solve(){
    102     int n;
    103     cin >> n;
    104     vector<int> a(n);
    105     for(int i=0; i<n; i++)
    106         cin >> a[i];
    107     if(a[0] == -1)
    108         a[0] = a[n-1];
    109     if(a[n-1] == -1)
    110         a[n-1] = a[0];
    111     for(int i=0; i<n; i++)
    112         if(a[i] == -1)
    113             a[i] = 0;
    114     cout << abs(a[n-1] - a[0]) << '\n';
    115     for(int i=0; i<n; i++)
    116         cout << a[i] << " \n"[i == n-1];
    117 }
    118  
    119 int main(){
    120     ios::sync_with_stdio(false);
    121     cin.tie(NULL);
    122     int t;
    123     cin >> t;
    124     while(t--) solve();
    125 }
    126 ```
    127 
    128 **Rate the problem!**
    129 
    130 **Quality**
    131 
    132 * Excellent problem
    133 * Good problem
    134 * Average problem
    135 * Bad problem
    136 * Horrible problem
    137 
    138 **Difficulty**
    139 
    140 * Trivial problem
    141 * Easy problem
    142 * Average problem
    143 * Hard problem
    144 * Impossible problem
    145 
    146 #### [C1/C2 — Renako Amaori and XOR Game](https://codeforces.com/contest/2171/problem/C2)
    147 
    148 **Solution (Easy Version)**
    149 
    150 **Step 1**
    151 
    152 The $\mathrm{XOR}$ of all $2n$ elements is invariant. Note that this is also equal to the $\mathrm{XOR}$ between Ajisai and Mai's final scores. Therefore, if this value is zero, the game ends in a tie. Otherwise, Ajisai and Mai's final scores will differ, so the game does not end in a tie.
    153 
    154 **Step 2**
    155 
    156 Suppose the $\mathrm{XOR}$ of all $2n$ elements is nonzero. If $a_i = b_i$, then the $i$-th turn is useless. Now, consider the **largest** $i$ such that $a_i \neq b_i$. This person can control whose score is $0$ and whose score is $1$. Since all future turns are useless, they win. Therefore, if the largest $i$ satisfying $a_i \neq b_i$ is odd, Ajisai wins. Otherwise, Mai wins.
    157 
    158 **Code (C++)**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162 using namespace std;
    163  
    164 void solve(){
    165     int n, x = 0, idx;
    166     cin >> n;
    167     vector<int> a(n), b(n);
    168     for(int i=0; i<n; i++){
    169         cin >> a[i];
    170         x ^= a[i];
    171     }
    172     for(int i=0; i<n; i++){
    173         cin >> b[i];
    174         x ^= b[i];
    175     }
    176     if(!x){
    177         cout << "Tie" << '\n';
    178         return;
    179     }
    180     for(int i=0; i<n; i++)
    181         if(a[i] ^ b[i])
    182             idx = i;
    183     cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
    184 }
    185  
    186 int main(){
    187     ios::sync_with_stdio(false);
    188     cin.tie(NULL);
    189     int t;
    190     cin >> t;
    191     while(t--) solve();
    192 }
    193 ```
    194 
    195 **Solution (Hard Version)**
    196 
    197 **Step 1**
    198 
    199 The $\mathrm{XOR}$ of all $2n$ elements is equal to the $\mathrm{XOR}$ between Ajisai and Mai's final scores. Therefore, we know exactly what bits their scores will differ in.
    200 
    201 **Step 2**
    202 
    203 The most significant of these bits dictates who wins the game. Therefore, we can apply the solution from the easy version to the most significant bit of the $\mathrm{XOR}$ of all $2n$ elements.
    204 
    205 **Code (C++)**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 using namespace std;
    210  
    211 void solve(){
    212     int n, x = 0, bit, idx;
    213     cin >> n;
    214     vector<int> a(n), b(n);
    215     for(int i=0; i<n; i++){
    216         cin >> a[i];
    217         x ^= a[i];
    218     }
    219     for(int i=0; i<n; i++){
    220         cin >> b[i];
    221         x ^= b[i];
    222     }
    223     if(!x){
    224         cout << "Tie" << '\n';
    225         return;
    226     }
    227     for(int i=0; i<20; i++)
    228         if(x&1<<i)
    229             bit = i;
    230     for(int i=0; i<n; i++)
    231         if((a[i]^b[i])&1<<bit)
    232             idx = i;
    233     cout << (idx & 1 ? "Mai" : "Ajisai") << '\n';
    234 }
    235  
    236 int main(){
    237     ios::sync_with_stdio(false);
    238     cin.tie(NULL);
    239     int t;
    240     cin >> t;
    241     while(t--) solve();
    242 }
    243 ```
    244 
    245 **Bonus**
    246 
    247 Can you find the difference between the players' scores, where the winner tries to maximize this value and the loser tries to minimize this value? I don't have a solution, but I suspect this may be impossible in polynomial time. Leave a comment if you have either a solution or a proof that it's impossible.
    248 
    249 **Rate the problem!**
    250 
    251 **Quality**
    252 
    253 * Excellent problem
    254 * Good problem
    255 * Average problem
    256 * Bad problem
    257 * Horrible problem
    258 
    259 **Difficulty**
    260 
    261 * Trivial problem
    262 * Easy problem
    263 * Average problem
    264 * Hard problem
    265 * Impossible problem
    266 
    267 #### [D/F — Rae Taylor and Trees](https://codeforces.com/contest/2171/problem/F)
    268 
    269 **Solution (Easy Version)**
    270 
    271 **Step 1**
    272 
    273 Let $\mathrm{pre}_i$ denote the **minimum** of $p_1, \dots, p_i$, and let $\mathrm{suf}_i$ denote the **maximum** of $p_i, \dots, p_n$. Then if there exists some $i$ such that $\mathrm{pre}_{i-1} \gt \mathrm{suf}_i$, then the answer is $\texttt{No}$. This is because there is no edge from any value in $p_1, \dots, p_{i-1}$ to any value in $p_i, \dots, p_n$.
    274 
    275 **Step 2**
    276 
    277 Otherwise, suppose that for every $i$, we have that $\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$. Then for every $i$, we have that there exists a path from $p_{i-1}$ to $p_i$, by going from $p_{i-1}$ to $\mathrm{pre}_{i-1}$ to $\mathrm{suf}_i$ to $p_i$. Since the graph consisting of these paths is connected, it must have some spanning tree, so the answer is $\texttt{Yes}$.
    278 
    279 **Code (C++)**
    280 
    281 ```
    282 #include <bits/stdc++.h>
    283 using namespace std;
    284  
    285 void solve(){
    286     int n;
    287     cin >> n;
    288     vector<int> p(n+1), pre(n+1, n), suf(n+2);
    289     for(int i=1; i<=n; i++){
    290         cin >> p[i];
    291         pre[i] = min(pre[i-1], p[i]);
    292     }
    293     for(int i=n; i>=1; i--)
    294         suf[i] = max(suf[i+1], p[i]);
    295     for(int i=2; i<=n; i++)
    296         if(pre[i-1] > suf[i]){
    297             cout << "No" << '\n';
    298             return;
    299         }
    300     cout << "Yes" << '\n';
    301 }
    302  
    303 int main(){
    304     ios::sync_with_stdio(false);
    305     cin.tie(NULL);
    306     int t;
    307     cin >> t;
    308     while(t--) solve();
    309 }
    310 ```
    311 
    312 **Solution (Hard Version)**
    313 
    314 **Step 1**
    315 
    316 Suppose that $\mathrm{pre}_{i-1} \lt \mathrm{suf}_i$ for all $i$. Let $s_1 \lt \dots \lt s_k = n$ denote the indices satisfying $p_i = \mathrm{suf}_i$, that is, the suffix maxes of $p$. Then let's partition $p$ into blocks ending at each $s_i$. Now, consider a block consisting of $p[l, r]$ for $l=s_{i-1}+1$ and $r=s_i$. We have that $\mathrm{suf}_l = \mathrm{suf}_r = p_r$ by construction, which means that all values in $p[l, r-1]$ are less than $p_r$. So we can connect all of these values to $p_r$.
    317 
    318 **Step 2**
    319 
    320 Now, each block is connected, so it suffices to connect the blocks to each other. We have that $\mathrm{pre}_{l-1} \lt \mathrm{suf}_l = p_r$, so we can connect $p_r$ to $\mathrm{pre}_{l-1}$. By induction, we see that all blocks are now connected, since each block is connected to some previous block.
    321 
    322 **Code (C++)**
    323 
    324 ```
    325 #include <bits/stdc++.h>
    326 using namespace std;
    327  
    328 void solve(){
    329     int n;
    330     cin >> n;
    331     vector<int> p(n+1), pre(n+1, n);
    332     vector<pair<int, int>> suf(n+2);
    333     for(int i=1; i<=n; i++){
    334         cin >> p[i];
    335         pre[i] = min(pre[i-1], p[i]);
    336     }
    337     for(int i=n; i>=1; i--)
    338         suf[i] = max(suf[i+1], {p[i], i});
    339     for(int i=2; i<=n; i++)
    340         if(pre[i-1] > suf[i].first){
    341             cout << "No" << '\n';
    342             return;
    343         }
    344     cout << "Yes" << '\n';
    345     for(int l=1; l<=n;){
    346         int r = suf[l].second;
    347         for(int i=l; i<r; i++)
    348             cout << p[i] << ' ' << p[r] << '\n';
    349         if(l > 1)
    350             cout << pre[l-1] << ' ' << p[r] << '\n';
    351         l = r+1;
    352     }
    353 }
    354  
    355 int main(){
    356     ios::sync_with_stdio(false);
    357     cin.tie(NULL);
    358     int t;
    359     cin >> t;
    360     while(t--) solve();
    361 }
    362 ```
    363 
    364 **Bonus**
    365 
    366 Can you count the number of satisfactory trees? I don't have a solution to this version; leave a comment if you find one.
    367 
    368 **Rate the problem!**
    369 
    370 **Quality**
    371 
    372 * Excellent problem
    373 * Good problem
    374 * Average problem
    375 * Bad problem
    376 * Horrible problem
    377 
    378 **Difficulty**
    379 
    380 * Trivial problem
    381 * Easy problem
    382 * Average problem
    383 * Hard problem
    384 * Impossible problem
    385 
    386 #### [E — Anisphia Wynn Palettia and Good Permutations](https://codeforces.com/contest/2171/problem/E)
    387 
    388 **Solution**
    389 
    390 **Step 1**
    391 
    392 Let $x$'s denote elements which all share a common divisor, and let $-$'s denote any elements. Then an array of the form $[-, x, x, -, x, x, \dots]$ will have no bad indices. Let's call an array of this form "perfect".
    393 
    394 **Step 2**
    395 
    396 Suppose the $x$'s are even elements. We have roughly $\frac{n}{2}$ even elements, which means we can form a perfect array of length roughly $\frac{3n}{4}$. Now, we have roughly $\frac{n}{6}$ elements which are odd multiples of $3$, which means we can form a disjoint perfect array of length roughly $\frac{n}{4}$. By concatenating these two arrays, we achieve a roughly full permutation with $O(1)$ bad indices. See the next section for a proof of the bound on bad indices.
    397 
    398 **Bound on bad indices**
    399 
    400 Instead of counting bad indices, we will count good indices. We form a perfect array of length $3\lfloor \frac{n}{4} \rfloor$, where all indices are good except for potentially the last one. We also form a perfect array of length $3\lfloor \frac{n+3}{12} \rfloor$ because we gain a new triple for every pair of $\{3, 9\} \pmod{12}$. Again, all indices are good except for potentially the last one. Therefore, we achieve $3\lfloor \frac{n}{4}\rfloor + 3\lfloor \frac{n+3}{12} \rfloor - 2$ good indices. It can be verified for every residue class $\bmod 12$ that this is lower bounded by $n-6$. Since there are $n-2$ indices in total, we have at most $4$ bad indices.
    401 
    402 **Code (C++)**
    403 
    404 ```
    405 #include <bits/stdc++.h>
    406 using namespace std;
    407  
    408 void solve(){
    409     int n;
    410     cin >> n;
    411     vector<vector<int>> a(3);
    412     for(int i=1; i<=n; i++)
    413         if(!(i % 2))
    414             a[0].push_back(i);
    415         else if(!(i % 3))
    416             a[1].push_back(i);
    417         else
    418             a[2].push_back(i);
    419     while(a[2].size() >= 1 && a[0].size() >= 2){
    420         cout << a[2].back() << ' ';
    421         a[2].pop_back();
    422         cout << a[0].back() << ' ';
    423         a[0].pop_back();
    424         cout << a[0].back() << ' ';
    425         a[0].pop_back();
    426     }
    427     while(a[2].size() >= 1 && a[1].size() >= 2){
    428         cout << a[2].back() << ' ';
    429         a[2].pop_back();
    430         cout << a[1].back() << ' ';
    431         a[1].pop_back();
    432         cout << a[1].back() << ' ';
    433         a[1].pop_back();
    434     }
    435     for(int i : a[0])
    436         cout << i << ' ';
    437     for(int i : a[1])
    438         cout << i << ' ';
    439     for(int i : a[2])
    440         cout << i << ' ';
    441     cout << '\n';
    442 }
    443  
    444 int main(){
    445     ios::sync_with_stdio(false);
    446     cin.tie(NULL);
    447     int t;
    448     cin >> t;
    449     while(t--) solve();
    450 }
    451 ```
    452 
    453 **Bonus**
    454 
    455 Let $f(n)$ denote the minimum number of bad indices across all permutations of length $n$. Can you find the value of $\max f(n)$? I suspect the answer is $2$, but I don't have a formal proof. Furthermore, can you find $f(n)$ for all $n$?
    456 
    457 Update: I've heard from several people that $\max f(n) = 1$. Feel free to post a comment with a proof, if you'd like.
    458 
    459 Update:
    460 
    461 **Solution**
    462 
    463 A construction commented by [d1amondzz](/profile/d1amondzz "Specialist d1amondzz") seems to prove an upper bound of $f(3), f(5) \leq 1$ and $f(n) = 0$ for $n\neq 3, 5$. I think several other comments may have alluded to a similar solution as well. The general idea is that for the largest prefix of primes $p_1, ..., p_k$ satisfying $p_{k-1}\cdot p_k \leq n$, we can construct an array $q$ as follows: for each $p_i$, first append $p_i$ to $q$, then append all elements with smallest prime factor $p_i$, ending with $p_i\cdot p_{i+1}$. Then all adjacent elements are not coprime, so as long as this array is of size at least roughly $\frac{2}{3}n$, we can intersperse it with the remaining elements to achieve no bad indices. All composites are included in $q$, because if a composite number has smallest prime factor at least $p_{k+1}$, then its value is at least $(p_{k+1})^2 \gt p_k\cdot p_{k+1} \gt n$ by construction of $k$. So we have that $q$ is of length asympototically at least $n-\frac{n}{\log n}$, which is asymptotically at least $cn$ for any $c \lt 1$. We can furthermore verify that this construction works for all small $n$ except for $3$ and $5$.
    464 
    465 As for the lower bound, it's easy to see that $f(3) \geq 1$ since all pairs are coprime, and that $f(5) \geq 1$ since the only pair that is not coprime is $\{2, 4\}$, but we cannot have that these elements appear in all triples. Therefore, we have that $f(3) = f(5) = 1$ and $f(n) = 0$ for $n\neq 3, 5$.
    466 
    467 **Rate the problem!**
    468 
    469 **Quality**
    470 
    471 * Excellent problem
    472 * Good problem
    473 * Average problem
    474 * Bad problem
    475 * Horrible problem
    476 
    477 **Difficulty**
    478 
    479 * Trivial problem
    480 * Easy problem
    481 * Average problem
    482 * Hard problem
    483 * Impossible problem
    484 
    485 #### [G — Sakura Adachi and Optimal Sequences](https://codeforces.com/contest/2171/problem/G)
    486 
    487 **Solution**
    488 
    489 **Step 1**
    490 
    491 Let's fix the number of double operations we use; call this integer $k$. Now, we can treat each value independently.
    492 
    493 **Step 2**
    494 
    495 Consider a specific pair $a_i, b_i$. If we don't apply any addition operations, we have that $a_i$ becomes $a_i \cdot 2^k$. Clearly we need that $a_i \cdot 2^k \leq b_i$. Now, observe that applying an addition operation before applying $j$ of the $k$ double operations is equivalent to adding $2^j$ to our final sum. We need to add $b_i - a_i \cdot 2^k$, so in total, we apply $\lfloor \frac{b_i - a_i \cdot 2^k}{2^k} \rfloor = \lfloor \frac{b_i}{2^k} \rfloor - a_i$ addition operations at the beginning, each adding $2^k$ to our sum. Then, we apply $\texttt{popcount}((b_i - a_i \cdot 2^k)\pmod{2^k}) = \texttt{popcount}(b_i\pmod{2^k})$ addition operations later, where $\texttt{popcount}(x)$ denotes the number of set bits in $x$. This is because, if the $j$-th bit of $b_i - a_i \cdot 2^k$ is set for some $j \lt k$, we would like to apply an operation before applying $j$ of the double operations so we can add $2^j$ to our sum.
    496 
    497 **Step 3**
    498 
    499 We would like to choose the largest number of double operations possible, since a double operation increases all values by at least one. Furthermore, since $n\geq 2$, a double operation is strictly more effective than an addition operation. However, we still need to satisfy $a_i \cdot 2^k \leq b_i$ for all $i$. Therefore, we will choose $k=\min \log_2{\frac{b_i}{a_i}}$.
    500 
    501 **Step 4**
    502 
    503 Between each double operation, the addition operations can be rearranged. Let's consider all of the addition operations applied before applying exactly $j$ double operations; denote these values $c_1, \dots, c_n$, where $c_i$ is the number of addition operations performed on element $a_i$. Then we can multiply our number of sequences by ${\sum c_i \choose c_1, \dots, c_n}$, the multinomial coefficient of $c_i$. This is equal to $\frac{(\sum c_i)!}{\prod (c_i!)}$. To simplify implementation, note that for $j \lt k$, all $c_i$ are either $0$ or $1$, so the denominator is only nontrivial for $j=k$. The final answer is the product of these values across all $0\leq j\leq k$. See the next section for intuition on multinomial coefficients and some of the details on its implementation.
    504 
    505 **Multinomial coefficients**
    506 
    507 The intuition behind the formula for multinomial coefficients is as follows: let's say $n=3$, and we want to find the number of ways to color $\sum c_i$ balls such that $c_1$ are red, $c_2$ are green, and $c_3$ are blue. Let's call our positions "red $1$" $\dots$ "red $c_1$" $\dots$ "blue $c_3$". Now, it's clear that there are $(\sum c_i)!$ ways to assign each ball to a position, because we have $\sum c_i$ choices of balls to assign to "red $1$", then $\sum c_i - 1$ remaining choices of balls to assign to "red $2$", and so forth, until we only have one choice of balls to assign to "blue $c_3$". However, this overcounts, because there is no difference between assigning ball $1$ to "red $1$" and ball $2$ to "red $2$", and vice versa. We are overcounting the red assignments by a factor of $c_1!$, because every valid selection of red balls achieves $c_1!$ assignments of red balls to positions. Similar reasoning holds for the green and blue balls, so in total, we have $\frac{(\sum c_i)!}{\prod (c_i!)}$ different sequences.
    508 
    509 Multinomial coefficients can be computed by precomputing factorials. For the numerator, note that if $\sum c_i \geq 10^6+3$ then $(\sum c_i)! \equiv 0\pmod{10^6+3}$ because we have a factor of $10^6+3$, so we only need to precompute factorials up to $10^6+2$. For the denominator, we can divide by $c_i!$ by multiplying by the modular inverse of $c_i!$ modulo $10^6+3$. Crucially, note that $c_i \lt 10^6+3$ because the number of addition operations you can apply is at most $b_i - a_i \lt 10^6$, so modular inverses are well-defined.
    510 
    511 **Code (C++)**
    512 
    513 ```
    514 #include <bits/stdc++.h>
    515 #define int long long
    516 using namespace std;
    517  
    518 int mod = 1e6+3;
    519  
    520 vector<int> fact(mod);
    521  
    522 int inv(int a){
    523     return a <= 1 ? a : mod - mod / a * inv(mod % a) % mod;
    524 }
    525  
    526 void solve(){
    527     int n, x, ans = 1;
    528     cin >> n;
    529     vector<int> a(n), b(n);
    530     for(int i=0; i<n; i++)
    531         cin >> a[i];
    532     for(int i=0; i<n; i++)
    533         cin >> b[i];
    534     int k = __lg(b[0] / a[0]);
    535     for(int i=1; i<n; i++)
    536         k = min(k, __lg(b[i] / a[i]));
    537     x = k;
    538     vector<int> cnt(k), c(n);
    539     for(int i=0; i<n; i++){
    540         for(int j=0; j<k; j++){
    541             cnt[j] += b[i] & 1;
    542             b[i] >>= 1;
    543         }
    544         c[i] = b[i] - a[i];
    545     }
    546     for(int j=0; j<k; j++){
    547         x += cnt[j];
    548         ans = ans * fact[cnt[j]] % mod;
    549     }
    550     int last = accumulate(c.begin(), c.end(), 0LL);
    551     ans = (last < mod ? ans * fact[last] % mod : 0);
    552     for(int i : c){
    553         x += i;
    554         ans = ans * inv(fact[i]) % mod;
    555     }
    556     cout << x << ' ' << ans << '\n';
    557 }
    558  
    559 signed main(){
    560     ios::sync_with_stdio(false);
    561     cin.tie(NULL);
    562     fact[0] = 1;
    563     for(int i=1; i<mod; i++) fact[i] = fact[i-1] * i % mod;
    564     int t;
    565     cin >> t;
    566     while(t--) solve();
    567 }
    568 ```
    569 
    570 **Rate the problem!**
    571 
    572 **Quality**
    573 
    574 * Excellent problem
    575 * Good problem
    576 * Average problem
    577 * Bad problem
    578 * Horrible problem
    579 
    580 **Difficulty**
    581 
    582 * Trivial problem
    583 * Easy problem
    584 * Average problem
    585 * Hard problem
    586 * Impossible problem
    587 
    588 #### [H — Shiori Miyagi and Maximum Array Score](https://codeforces.com/contest/2171/problem/H)
    589 
    590 **Solution**
    591 
    592 **Step 1**
    593 
    594 Let's first try to solve this problem with inefficient time and memory, then we will later optimize it. For $1\leq i\leq n$ and $0\leq j\leq m-n$, let $\mathrm{dp}[i][j]$ denote the largest score achievable from the first $i$ indices, while also satisfying $a_i = i+j$. Now, since $a$ must be strictly increasing, we equivalently have that $a_i - i$ is monotonically increasing. Therefore, we can transition as follows: $\mathrm{dp}[i][j] = \max_{k\leq j} \mathrm{dp}[i-1][k] + v(i, i+j)$, because we may choose $a_{i-1}$ to be any value satisfying $a_{i-1} - (i-1) \leq j$, then we choose $a_i = i+j$, adding a score of $v(i, i+j)$.
    595 
    596 **Step 2**
    597 
    598 Now, we will try to remove the first dimension; that is, $\mathrm{dp}[j]$ denotes the largest score achievable while also satisfying $a_i = i+j$, where we will update this array as we iterate through all $i$. We will store this in a data structure that supports quickly querying prefix maximums and increasing point values; in particular, either a Fenwick tree or a segment tree will work.
    599 
    600 Suppose we are at some stage $i$ and would like to update $\mathrm{dp}[j]$. As before, we want to update it to $\max_{k\leq j} \mathrm{dp}[k] + v(i, i+j)$. We should process $j$ in reverse order, as we want to ensure that we are accessing $\mathrm{dp}[i-1][k]$ instead of $\mathrm{dp}[i][k]$.
    601 
    602 However, we only have to update $\mathrm{dp}[j]$ if $v(i, i+j)$ is nonzero. This is because, if $v(i, i+j)$ is zero, then we are updating $\mathrm{dp}[j]$ to $\max_{k\leq j} \mathrm{dp}[k]$. However, since we are only querying prefix maximums, any query involving $j$ will implicitly query all $k\leq j$ anyways, so it is not necessary to explicitly update $\mathrm{dp}[j]$. Our final answer is $\max \mathrm{dp}[j]$. See the next section for runtime analysis.
    603 
    604 **Runtime analysis**
    605 
    606 For simplicity of analysis, assume $m - n \geq c$ for some reasonable $c$, to avoid pathological cases where $\log (m-n)$ is undefined or zero.
    607 
    608 For each $i$, we are updating $O(\frac{m-n}{i})$ values. Therefore, in total, we have $O(\sum \frac{m-n}{i}) = O((m-n)H(n))$ updates. Since harmonic numbers are known to grow logarithmically, this is $O((m-n)\log n)$. Each update takes $O(\log (m-n))$ time, as it involves a query and an update on a Fenwick tree or segment tree of size $m-n+1$. So the updates in total take $O((m-n)\log n\log{(m-n)})$ time.
    609 
    610 However, we also need to compute $v(i, i+j)$ for each update. This will take $O(\sum v(i, i+j))$ time. For a fixed $i$, we have that $O(\frac{m-n}{i})$ values satisfy $v(i, i+j) \geq 1$, $O(\frac{m-n}{i^2})$ values satisfy $v(i, i+j) \geq 2$, and so forth. Therefore, for a fixed $i$, we have that $\sum v(i, i+j) = O(\sum \frac{m-n}{i^k}) = O(\frac{m-n}{i}\sum \frac{1}{i^{k-1}}) = O(\frac{m-n}{i} \cdot \frac{1}{1-\frac{1}{i}}) = O(\frac{m-n}{i} \cdot \frac{i}{i-1}) = O((m-n) \cdot \frac{1}{i-1})$. Across all $i\geq 2$, we have $O((m-n)H(n-1)) = O((m-n)\log n)$. This is dominated by the $O((m-n)\log n\log{(m-n)})$ term from the updates.
    611 
    612 Finally, we have an additional $n$ term, as we have to iterate through all $i\leq n$. Our total runtime is $O((m-n)\log n\log{(m-n)} + n)$.
    613 
    614 **Code (C++)**
    615 
    616 ```
    617 #include <bits/stdc++.h>
    618 using namespace std;
    619  
    620 void solve(){
    621     int n, m;
    622     cin >> n >> m;
    623     vector<int> mx(m-n+1);
    624     function<int(int)> query = [&](int i)->int{
    625         int ret = 0;
    626         for(; i>=0; i=(i&i+1)-1)
    627             ret = max(ret, mx[i]);
    628         return ret;
    629     };
    630     function<void(int, int)> update = [&](int i, int val){
    631         for(; i<=m-n; i|=i+1)
    632             mx[i] = max(mx[i], val);
    633     };
    634     function<int(int, int)> v = [](int b, int x)->int{
    635         int ans = 0;
    636         while(!(x % b)){
    637             ans++;
    638             x /= b;
    639         }
    640         return ans;
    641     };
    642     for(int i=2; i<=n; i++)
    643         for(int j=(m-n+i)/i*i; j>=i; j-=i)
    644             update(j-i, query(j-i) + v(i, j));
    645     cout << query(m-n) << '\n';
    646 }
    647  
    648 int main(){
    649     ios::sync_with_stdio(false);
    650     cin.tie(NULL);
    651     int t;
    652     cin >> t;
    653     while(t--) solve();
    654 }
    655 ```
    656 
    657 **Rate the problem!**
    658 
    659 **Quality**
    660 
    661 * Excellent problem
    662 * Good problem
    663 * Average problem
    664 * Bad problem
    665 * Horrible problem
    666 
    667 **Difficulty**
    668 
    669 * Trivial problem
    670 * Easy problem
    671 * Average problem
    672 * Hard problem
    673 * Impossible problem