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  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  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  258 259 The blue shape can be further split into these two rectangles: 260 261 **Picture** 262 263  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)$