codeforces-scrape

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

1909.md (25000B)


      1 Source: https://codeforces.com/blog/entry/123584
      2 
      3 The official implementations of all the problems are [here](https://drive.google.com/file/d/1q2PHS9nJt84FRwfMoiMslQULFE4dTMU4/view?usp=sharing).
      4 
      5 **Timeline of the round proposal (may contain spoilers)**
      6 
      7 (problems D', H', etc. were not used)
      8 
      9 * Feb 19, 2022: I proposed problem D' to [Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)](/contest/1654), but it was not used.
     10 * Mar 13, 2023: I invented problem A.
     11 * May 16: I invented problem H'.
     12 * May 19: I realized problem G can be solved in $O(n)$ time and we used it in the Italian team selection test for IOI.
     13 * Jul 04: I opened a Div. 1 proposal containing A, D', G, H' and other problems which are not going to be used.
     14 * Aug 09: I invented problem I, with intended solution in $O(n^3)$.
     15 * Sep 27: I invented problem C.
     16 * Oct 14: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") replied to my contest proposal.
     17 * Nov 02: I invented problem D''. [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") solved problem I in $O(n^2 \log n)$.
     18 * Nov 08: I invented problems E and F. I didn't propose problem F because I thought it was too easy.
     19 * Nov 10: I invented problem H with $O(n \log n)$ operations. We had a preliminary problemset, with problems A, D', C, D'', E, H1, G, H', I. I started preparing the problems.
     20 * Nov 14: I finished preparing the problems, and the round was ready for testing. [dario2994](/profile/dario2994 "International Grandmaster dario2994") tested and didn't solve problem D''. I realized the official solution of problem D'' was wrong (and now I don't have any solution).
     21 * Nov 15: I removed problem D'' from the contest and replaced it with problem F.
     22 * Nov 17: I invented problem E'.
     23 * Nov 19: I invented problem F', which was rejected because it was proposed independently to [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") by the authors of another round.
     24 * Nov 22: [gamegame](/profile/gamegame "Legendary Grandmaster gamegame") tested and said problem H' is well-known in China. I removed it.
     25 * Nov 26: we realized problem D' was too hard for position B.
     26 * Nov 28: I invented problem D with $k = 1$ and $a_i \geq 2$, and I proposed it as B.
     27 * Nov 29: I invented problem B. [Endagorion](/profile/Endagorion "International Grandmaster Endagorion") solved problem H in $2n$ operations.
     28 * Dec 07: the problemset was A, B, C, D', F1, F2, E, G, H1, H2, I, but there was a huge gap between D' and the next problems. We ended up using A, B, C, D, E', E, F2, G, H2, I (i.e., 10 problems). D still had $k = 1$ and $a_i \geq 2$.
     29 * Dec 13: we removed the constraints $k = 1$ and $a_i \geq 2$ from problem D.
     30 * Dec 18: problem E' appeared in [Educational Codeforces Round 160 (Rated for Div. 2)](/contest/1913 "Educational Codeforces Round 160 (Rated for Div. 2)"). We removed it and we decided to use subtasks on problem F.
     31 
     32 [1909A - Distinct Buttons](/contest/1909/problem/A)
     33 
     34 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
     35  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     36 
     37 **Hint 1**
     38 
     39 Suppose you can only use $\texttt{U}$, $\texttt{R}$, $\texttt{D}$. Which cells can you reach?
     40 
     41 **Solution**
     42 
     43 If you only use buttons $\texttt{U}$, $\texttt{R}$, $\texttt{D}$, you can never reach the points with $x \lt 0$. However, if all the special points have $x \geq 0$, you can reach all of them with the following steps:
     44 
     45 * visit all the special points with $x = 0$, using the buttons $\texttt{U}$, $\texttt{D}$;
     46 * press the button $\texttt{R}$ to reach $x = 1$;
     47 * visit all the special points with $x = 1$, using the buttons $\texttt{U}$, $\texttt{D}$;
     48 * $\dots$
     49 * visit all the special points with $x = 100$, using the buttons $\texttt{U}$, $\texttt{D}$.
     50 
     51 Similarly, if you use at most $3$ buttons in total, you can reach all the special points if at least one of the following conditions is true:
     52 
     53 * all $x_i \geq 0$;
     54 * all $x_i \leq 0$;
     55 * all $y_i \geq 0$;
     56 * all $y_i \leq 0$.
     57 
     58 Complexity: $O(n)$
     59 
     60 [1909B - Make Almost Equal With Mod](/contest/1909/problem/B)
     61 
     62 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
     63  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     64 
     65 **Hint 1**
     66 
     67 Find a value of $k$ that works in many cases.
     68 
     69 **Hint 2**
     70 
     71 $k = 2$ works in many cases. What if it does not work?
     72 
     73 **Hint 3**
     74 
     75 If $k = 2$ does not work, either all the numbers are even or all the numbers are odd. Which $k$ can you try now?
     76 
     77 **Solution**
     78 
     79 Let $f(k)$ be the number of distinct values after the operation, using $k$.
     80 
     81 Let's try $k = 2$. It works in all cases, except when either all the numbers are even or all the numbers are odd.
     82 
     83 Let's generalize. If $a_i \text{ mod } k = x$, one of the following holds:
     84 
     85 * $a_i \text{ mod } 2k = x$;
     86 * $a_i \text{ mod } 2k = x+k$;
     87 
     88 It means that, if $f(k) = 1$ (i.e., all the values after the operations are $x$), either $f(2k) = 1$ (if either all the values become $x$, or they all become $x+k$), or $f(2k) = 2$.
     89 
     90 Therefore, it is sufficient to try $k = 2^1, \dots, 2^{57}$. In fact, $f(1) = 1$ and $f(2^{57}) = n$, so there must exist $m \lt 57$ such that $f(2^m) = 1$ and $f(2^{m+1}) \neq 1 \implies f(2^{m+1}) = 2$.
     91 
     92 Alternative (more intuitive?) interpretation:
     93 
     94 * $a_i \text{ mod } 2^j$ corresponds to the last $j$ digits in the binary representation of $a_i$. There must exist $j$ such that the last $j$ digits make exactly $2$ distinct blocks.
     95 
     96 In the following picture, $a = [1005, 2005, 7005, 11005, 16005]$ and $k = 16$:
     97 
     98 **Picture**
     99 
    100 ![ ](/predownloaded/04/d4/04d40ed602b2fa79759cb44fa5c66a3c954fa123.png)
    101 
    102 Complexity: $O(n \log(\max a_i))$
    103 
    104 [1909C - Heavy Intervals](/contest/1909/problem/C)
    105 
    106 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    107  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    108 
    109 **Hint 1**
    110 
    111 Assign bigger costs to shorter intervals.
    112 
    113 **Hint 2**
    114 
    115 Solve the problem with $n = 2$.
    116 
    117 **Hint 3**
    118 
    119 Solve the following case: $l = [1, 2]$, $r = [3, 4]$, $c = [1, 2]$. Can you generalize it?
    120 
    121 **Solution**
    122 
    123 You have to match each $l_i$ with some $r_j \gt l_i$.
    124 
    125 Construct $v = {l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n}$ and sort it. If you replace every $l_i$ with the symbol $\texttt{(}$ and every $r_i$ with the symbol $\texttt{)}$, you get a [regular bracket sequence](https://cp-algorithms.com/combinatorics/bracket_sequences.html) (sketch of proof: $l_i \lt r_i$ for each $i$, so each prefix of symbols contains at least as many $\texttt{(}$ as $\texttt{)}$, so the bracket sequence is regular).
    126 
    127 Now match each $\texttt{(}$ with the [corresponding](https://en.wikipedia.org/wiki/Bracket_matching) $\texttt{)}$. You can show that this is the optimal way to rearrange the $l_i$ and the $r_i$. (From now, let the $l_i$, $r_i$ and $c_i$ be the values after your rearrangement.)
    128 
    129 Proof:
    130 
    131 * If you match the brackets in any other way, you get two intervals such that their intersection is non-empty but it is different from both intervals (i.e., you get $l_i \lt l_j \lt r_i \lt r_j$).
    132 * You have also assigned some cost $c_i$ to $[l_i, r_i]$ and $c_j$ to $[l_j, r_j]$. Without loss of generality, $c_i \leq c_j$ (the other case is symmetrical).
    133 * If you swap $r_i$ and $r_j$, the cost does not increase.
    134 * Keep swapping endpoints until you get the "regular" bracket matching. You can show that the process ends in a finite number of steps. For example, you can show that $\sum ((r_i - l_i)^2)$ strictly increases after each step, and it is an integer $\leq \sum (r_i^2)$.
    135 
    136 **Picture**
    137 
    138 ![ ](/predownloaded/d4/3c/d43c6e5e6bff870dd305fe383df68b0d8705fe3c.png)
    139 
    140 Now, you can get the minimum cost by sorting the intervals by increasing length and sorting the $c_i$ in decreasing order.
    141 
    142 Alternative (more intuitive?) interpretation:
    143 
    144 * If you solve the problem with $n = 2$ and try to generalize, you can notice that it seems optimal to match every $r_i$ with the largest unused $l_i$ (if you iterate over $r_i$ in increasing order).
    145 
    146 You can implement the solution by using either a stack (to simulate the bracket matching) or a set (to find the largest unused $l_i$).
    147 
    148 Complexity: $O(n \log n)$
    149 
    150 [1909D - Split Plus K](/contest/1909/problem/D)
    151 
    152 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    153  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    154 
    155 **Hint 1**
    156 
    157 Solve the problem with $k = 0$.
    158 
    159 **Hint 2**
    160 
    161 Solve the problem with generic $k$. When is the answer $-1$?
    162 
    163 **Hint 3**
    164 
    165 Do you notice any similarities between the cases with $k = 0$ and with generic $k$?
    166 
    167 **Solution**
    168 
    169 Consider the "shifted" problem, where each $x$ on the blackboard (at any moment) is replaced with $x' = x-k$.
    170 
    171 Now, the operation becomes "replace $x$ with $y+z$ such that $y+z = x+k \implies (y'+k)+(z'+k) = (x'+k)+k \implies y'+z' = x'$". Therefore, in the shifted problem, $k' = 0$.
    172 
    173 Now you can replace every $a'_i := a_i - k$ with any number of values with sum $a'_i$, and the answer is the amount of numbers on the blackboard at the end, minus $n$.
    174 
    175 If we want to make all the values equal to $m'$, it must be a divisor of every $a'_i$.
    176 
    177 * If all the $a'_i$ are positive, it is optimal to choose $m' = \gcd a'_i$.
    178 * If all the $a'_i$ are zero, the answer is $0$.
    179 * If all the $a'_i$ are negative, it is optimal to choose $m' = -\gcd -a'_i$.
    180 * Otherwise, the answer is $-1$.
    181 
    182 Alternative way to get this result:
    183 
    184 * You have to split each $a_i$ into $p_i$ pieces equal to $m$, and their sum must be equal to $a_i + k(p_i - 1) = (a_i - k) + kp_i = mp_i$. Then, $(a_i - k) = (m - k)p_i$, so $m' = m-k$ must be a divisor of every $a'_i = a_i - k$.
    185 
    186 In both the positive and the negative case, you will only write positive elements (in the original setup), as wanted.
    187 
    188 * If all the $a'_i$ are positive, the numbers you will write on the shifted blackboard are positive, so they will be positive also in the original blackboard.
    189 * If all the $a'_i$ are negative, the numbers you will write on the shifted blackboard are greater than the numbers you will erase, so they will be greater than the numbers in input (and positive) in the original blackboard.
    190 
    191 Complexity: $O(n + \log(\max a_i))$
    192 
    193 [1909E - Multiple Lamps](/contest/1909/problem/E)
    194 
    195 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    196  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    197 
    198 **Hint 1**
    199 
    200 Find a strategy that turns "few" lamps on in most cases.
    201 
    202 **Hint 2**
    203 
    204 Pressing all the buttons turns $\lfloor \sqrt n \rfloor$ lamps on.
    205 
    206 **Hint 3**
    207 
    208 If the strategy in Hint 2 does not work, at most $3$ lamps must be on at the end.
    209 
    210 **Hint 4**
    211 
    212 Iterate over all subsets of at most $3$ lamps that must be on at the end.
    213 
    214 **Solution**
    215 
    216 If you press all the buttons, lamp $i$ is toggled by all the divisors of $i$, so it will be on if $i$ has an odd number of divisors, i.e., if $i$ is a perfect square.
    217 
    218 Then, the strategy of pressing all the buttons works if $\lfloor \sqrt n \rfloor \leq \lfloor n/5 \rfloor$, which is true for $n \geq 20$.
    219 
    220 If $n \leq 19$, at most $\lfloor 19/5 \rfloor = 3$ lamps must be turned on at the end.
    221 
    222 If you know which lamps must be turned on at the end, you can iterate over the buttons from $1$ to $n$ and press button $i$ if and only if lamp $i$ is in the wrong state. So you can iterate over all subsets of at most $3$ lamps, and check if the corresponding choice of buttons is valid (i.e., the $m$ constraints hold). You can remove a $\log n$ factor by precalculating the choice of buttons for all small subsets before running the testcases.
    223 
    224 Complexity for each test: $O(\sum n + (\sum m \cdot k^{2k-4}))$ (if $\lfloor n/k \rfloor$ lamps must be on; in this case, $k = 5$).
    225 
    226 [1909F1 - Small Permutation Problem (Easy Version)](/contest/1909/problem/F1), [1909F2 - Small Permutation Problem (Hard Version)](/contest/1909/problem/F2)
    227 
    228 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    229  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    230 
    231 **Hint 1**
    232 
    233 Find a clean way to visualize the problem.
    234 
    235 **Hint 2**
    236 
    237 Draw a $n \times n$ grid, with tokens in $(i, p_i)$. Which constraints on the tokens do you have?
    238 
    239 **Hint 3**
    240 
    241 You have some "L" shapes, and each of them must contain a fixed number of tokens (in [1909F1 - Small Permutation Problem (Easy Version)](/contest/1909/problem/F1) the shapes are $1$ cell wide and must contain at most $2$ tokens). Iterate over the shapes in increasing order of $i$.
    242 
    243 **Hint 4**
    244 
    245 Split each shape into $2$ rectangles and iterate over the number of tokens in the first rectangle.
    246 
    247 **Solution**
    248 
    249 Draw a $n \times n$ grid, with tokens in $(i, p_i)$.
    250 
    251 Consider any $a_i \neq -1$ and the nearest $a_j \neq -1$ on the left (if it does not exist, let's set $j = a_j = 0$). Then, there must be $a_i$ tokens in the subgrid $[1, i] \times [1, i]$. We can suppose we have already inserted the $a_j$ tokens in $[1, j] \times [1, j]$, and we have to insert $a_i - a_j$ tokens in the remaining cells of $[1, i] \times [1, i]$ (they make an "L" shape).
    252 
    253 WLOG, the $a_j$ tokens in $[1, j] \times [1, j]$ are in the cells $(1, 1), \dots, (a_j, a_j)$. Then, we can put tokens in the blue cells in the picture.
    254 
    255 **Picture**
    256 
    257 ![ ](/predownloaded/45/00/4500d16e6248a16dd83e5e3b4ebb335cf62c64a4.png)
    258 
    259 The blue shape can be further split into these two rectangles:
    260 
    261 **Picture**
    262 
    263 ![ ](/predownloaded/41/08/4108cefdf6bef4ed914152e1e2c1742fd90444fc.png)
    264 
    265 Iterate over $k$, the number of tokens in the first rectangle ($0 \leq k \leq a_i - a_j$). Then, you have to insert $k$ tokens into a $h_1 \times w_1$ rectangle, and the remaining $a_i - a_j - k$ tokens into a $h_2 \times (w_2 - k)$ rectangle.
    266 
    267 The number of ways to insert $k$ tokens into a $h \times w$ rectangle is equal to the product of the number of ways to choose $k$ rows, the number of ways to choose $k$ columns, and the number of ways to fill the resulting $k \times k$ subgrid: the result is $\binom{h}{k} \binom{w}{k} k!$.
    268 
    269 $a_n = n$ automatically (if $a_n \neq n$ and $a_n \neq -1$, the answer is $0$). If the non-negative $a_i$ are non-decreasing, the sum of the $a_i - a_j + 1$ (i.e., the $k$ over which you have to iterate) is $O(n)$, so the algorithm is efficient enough. Otherwise, the answer is $0$.
    270 
    271 Complexity: $O(n)$
    272 
    273 [1909G - Pumping Lemma](/contest/1909/problem/G)
    274 
    275 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    276  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    277 
    278 **Hint 1**
    279 
    280 If you remove the condition $s = x+y+z$, the problem becomes harder.
    281 
    282 **Hint 2**
    283 
    284 Solve for a fixed $|y|$ (length of $y$).
    285 
    286 **Hint 3**
    287 
    288 Suppose you have found a valid $y$. Shift it one position to the right. When is it still valid?
    289 
    290 **Hint 4**
    291 
    292 The valid $y$ with $|y| = l$ start in consecutive positions.
    293 
    294 **Hint 5**
    295 
    296 Using the same idea of the proof of Hint 4, you can find all the valid $y$.
    297 
    298 **Solution**
    299 
    300 Let's use $s[l, r]$ to indicate the substring $[l, r]$ of $s$. Let's use $(a, b)$ to indicate the triple of strings $(s[1, a], s[a+1, b], s[b+1, n])$.
    301 
    302 Suppose $(a, b)$ is valid. Then, $(a+1, b+1)$ is valid if and only if $s_{b+1} = t_{b+1}$.
    303 
    304 If $(a, b)$ is valid, $s[1, b] = t[1, b]$; so if $s_b \neq t_b$, $(a+k, b+k)$ is invalid for $k \geq 0$. Therefore, if $(a, b)$ is the first valid pair with $b-a=l$ (i.e., with $|y| = l$), and $k$ is the smallest positive integer such that $(a+k, b+k)$ is invalid, then $s_{b+k} \neq t_{b+k}$, so the only valid pairs with $|y| = l$ are the $(a+j, b+j)$ with $0 \leq j \lt k$ (i.e., the valid $y$ with $|y| = l$ start in consecutive positions).
    305 
    306 Now let's find all the valid $y$ with $|y| = l$. Suppose $(a, b)$ is valid, and $c$ is the minimum index such that $s_c \neq t_c$. Then, $b \lt c$, and $(a+k, b+k)$ is valid for all $b \leq b+k \lt c$. Similarly, if $d$ is the minimum integer such that $s_{n-d} \neq t_{m-d}$, $(a+k, b+k)$ is valid for all $n-d \lt a+k \leq a \implies n-d+l \lt b+k \leq b$.
    307 
    308 Therefore, it's enough to check only one pair for each length, with $b$ in $[n-d+l+1, c-1]$ (because either all these pairs are valid or they are all invalid). This is possible by precomputing the rolling hash of the two strings. Alternatively, you can use z-function.
    309 
    310 Complexity: $O(n)$
    311 
    312 [1909H - Parallel Swaps Sort](/contest/1909/problem/H)
    313 
    314 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    315  Full solution: [Endagorion](/profile/Endagorion "International Grandmaster Endagorion"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn")  
    316  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse"), [francesco](/profile/francesco "Candidate Master francesco")
    317 
    318 **Hint 1**
    319 
    320 Find a strategy which is as simple and "easy to handle" as possible.
    321 
    322 **Hint 2**
    323 
    324 Only perform operations such that all swapped pairs have $a_i \gt a_{i+1}$. Let's call such subarrays "swappable".
    325 
    326 **Hint 3**
    327 
    328 First, for each $i$ from left to right, do the operation on $[j, i]$, where $j$ is the minimum index such that $[j, i]$ is swappable.
    329 
    330 **Hint 4**
    331 
    332 Repeat the same algorithm from right to left.
    333 
    334 **Hint 5**
    335 
    336 After Hints 3 and 4, the array is sorted. Prove it (it will be useful).
    337 
    338 **Hint 6**
    339 
    340 Assign $\texttt{B}$ to the indices $i$ such that $a_i \lt a_{i-1}$ and $\texttt{A}$ to the other indices. During the process in Hint 3, after the operation on index $i$, which properties do $\texttt{A}$, $\texttt{B}$ have in the prefix $[1, i]$?
    341 
    342 **Hint 7**
    343 
    344 Answer to Hint 6:
    345 
    346 * the values of type $\texttt{A}$ are increasing;
    347 * there are no two consecutive elements of type $\texttt{B}$.
    348 
    349 **Hint 8**
    350 
    351 The rest of the proof (i.e., what happens during the process in Hint 4) is relatively easy.
    352 
    353 Now let's find an efficient implementation. We have to use the properties in Hint 7.
    354 
    355 **Hint 9**
    356 
    357 You have to find the longest $\texttt{AB} \dots \texttt{AB}$ ending in position $i$, and perform the operation on it. What happens during the operation?
    358 
    359 **Hint 10**
    360 
    361 $\texttt{A}$ will always remain $\texttt{A}$. For each $\texttt{B}$, you have to detect when it becomes $\texttt{A}$.
    362 
    363 **Hint 11**
    364 
    365 For each $\texttt{B}$, you can precompute the number of moves needed to make it $\texttt{A}$.
    366 
    367 **Hint 12**
    368 
    369 For example, you can use a segment tree with the following information: the type of each element, the positions of the elements of type $\texttt{B}$, and the number of moves required for each $\texttt{B}$ to become $\texttt{A}$.
    370 
    371 **Solution**
    372 
    373 Let's only perform operations such that all swapped pairs have $a_i \gt a_{i+1}$. Let's call such subarrays "swappable".
    374 
    375 * First, for each $i$ from left to right, do the operation on $[j, i]$, where $j$ is the minimum index such that $[j, i]$ is swappable (let's call it "operation $1.i$").
    376 * Then, for each $i$ from right to left, do the operation on $[j, i]$, where $j$ is the minimum index such that $[j, i]$ is swappable (let's call it "operation $2.i$").
    377 
    378 After these operations, the array is sorted. Let's prove it.
    379 
    380 Assign $\texttt{B}$ to the indices $i$ such that $a_i \lt a_{i-1}$ and $\texttt{A}$ to the other indices. After operation $1.i$, only assign letters in the prefix $[1, i]$ and ignore the other elements. During the operations $2.i$, assign letters to all the elements.
    381 
    382 Most of the following proofs are by induction. After the operation $1.i$ (supposing the properties were true after the operation $1.(i-1)$):
    383 
    384 * An element of type $\texttt{A}$ will always remain of type $\texttt{A}$. Proof: the only elements of type $\texttt{A}$ whose previous element changes are the ones in the subarray $[j, i]$, which are swapped with a smaller element of type $\texttt{B}$.
    385 * There are no two consecutive elements of type $\texttt{B}$. Proof: if you swap $[j, i]$, $p_{j-1}$ (if it exists) must be of type $\texttt{A}$ (otherwise $[j-2, i]$ is swappable).
    386 * The elements of type $\texttt{A}$ are increasing. Proof: it's true if no $\texttt{B}s$ become $\texttt{A}s$, and it's also true if some $\texttt{B}s$ become $\texttt{A}s$ because any of them is adjacent to two $\texttt{A}s$.
    387 
    388 After the operation $2.i$:
    389 
    390 * The three properties above are still true.
    391 * The suffix $[i, n]$ contains the values in $[i, n]$ in order. Proof: $a_i$ is an $\texttt{A}$, so it must be the largest $p_i$ in $[1, i]$, which is $i$.
    392 
    393 Now let's understand how we can implement the algorithm. Example implementation:
    394 
    395 * We maintain a segment tree. The $i$-th position of the segment tree contains information about the element which was initially $p_i$. Note that the relative position of $\texttt{B}s$ never changes: for example, if you want information about the last $k$ $\texttt{B}s$ in the current permutation, and you search them in the segment tree, you will find exactly the last $k$ $\texttt{B}s$, even though their indices will not correspond to the current indices.
    396 * We have to find the longest swappable subarray ending at $i$. It means we need the current positions of the $\texttt{B}s$. For each $\texttt{B}$ maintain the current position, and assume the position of all the $\texttt{A}s$ is $0$. Also maintain, for each element, if it is a $\texttt{B}$ or not. Note that the $\texttt{B}s$ that are affected by each operation can be found in a suffix of the segment tree.
    397 * In this way, finding the longest swappable subarray can be done with a binary search on the segment tree: since $\texttt{B}s$ cannot be consecutive, you have to find the longest suffix such that the sum of the positions of the $\texttt{B}s$ is the maximum possible (i.e., if there are $k$ $\texttt{B}s$ and the last of them is in position $i$, the sum of their positions must be $k(i-k+1)$).
    398 * After finding the longest subarray in the segment tree, you have to perform the operation on it, i.e., subtract $1$ from all the nonzero positions.
    399 * Some $\texttt{B}s$ may become $\texttt{A}s$. How to detect them? Since $\texttt{A}s$ never become $\texttt{B}s$, a $\texttt{B}$ becomes $\texttt{A}$ after it is swapped with all the elements greater than it on its left. So you can precompute the number of swaps that every $\texttt{B}$ needs to become $\texttt{A}$, and put it in the segment tree as well. Again, the operation is "subtract $1$ from a range".
    400 * Detecting $\texttt{A}s$ means detecting elements which need $0$ swaps to become $\texttt{A}s$. You can find them after each operation by traversing the segment tree (which must support "range min" on the number of swaps needed), and set their position to $0$ and the number of swaps needed to $\infty$.
    401 
    402 Complexity: $2n-3$ moves, $O(n \log n)$ time.
    403 
    404 [1909I - Short Permutation Problem](/contest/1909/problem/I)
    405 
    406 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    407  Full solution: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn")  
    408  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    409 
    410 **Hint 1**
    411 
    412 Insert the elements into the permutation in some comfortable order.
    413 
    414 **Hint 2**
    415 
    416 Suppose $m$ is even. You can insert elements in the order $[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$.
    417 
    418 **Hint 3**
    419 
    420 You can solve for a single $m$ with DP. Can you calculate the DP for multiple $m$ simultaneously?
    421 
    422 **Hint 4**
    423 
    424 The first part of the DP (where you insert both "small" and "big" elements) is the same for each $m$ (but with a different length), and for the second part (where you only insert "small" elements) you don't need DP.
    425 
    426 **Hint 5**
    427 
    428 The second part of the DP can be replaced with combinatorics formulas.
    429 
    430 **Hint 6**
    431 
    432 Binomials are compatible with NTT.
    433 
    434 **Solution**
    435 
    436 Let's solve for a single $m$. Suppose $m$ is even. Start from an empty array, and insert the elements in the order $[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$. At any moment, all the elements are concatenated, and you can insert new elements either at the beginning, at the end or between two existing elements.
    437 
    438 * When you insert an element $\geq m/2$, the sum with any of the previous inserted elements is $\geq m$.
    439 * Otherwise, the sum is $ \lt m$.
    440 
    441 So you can calculate $dp_{i,j} =$ number of ways to insert the first $i$ elements (of $[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$) and make $j$ "good" pairs (with sum $\geq m$).
    442 
    443 You can split the ordering $[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$ into two parts:
    444 
    445 * small and big elements alternate;
    446 * there are only small elements.
    447 
    448 For the second part, you don't need DP. Suppose you have already inserted $i$ elements, and there are $j$ good pairs, but when you will have inserted all elements you want $k$ good pairs. The number of ways to insert the remaining elements can be computed with combinatorics in $O(1)$ after precomputing factorials and inverses (you have to choose which pairs to break and use stars and bars; we skip exact formulas because they are relatively easy to find).
    449 
    450 If you rearrange the factorials correctly, you can get that all the answers for a fixed $m$ can be computed by multiplying two polynomials, one of which contains the $dp_{i,j}$, where $i$ is equal to the length of the "alternating" prefix. NTT is fast enough.
    451 
    452 Complexity: $O(n^2 \log n)$