codeforces-scrape

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

1654.md (21930B)


      1 Source: https://codeforces.com/blog/entry/100127
      2 
      3 [1654A - Maximum Cake Tastiness](/contest/1654/problem/A)
      4 
      5 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
      6  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
      7 
      8 **Hint 1**
      9 
     10 Suppose you want to choose pieces of cake $i$, $j$. Can you make them adjacent in $1$ move?
     11 
     12 **Solution**
     13 
     14 The answer is the sum of the $2$ maximum weights.
     15 
     16 You can always pick the $2$ maximum weights: if they are $a_i$ and $a_j$ ($i \lt j$), you can flip the subsegment $[i, j-1]$ to make them adjacent.
     17 
     18 The result can't be larger, because the sum of the weights of any $2$ pieces of cake is never greater than the sum of the $2$ maximum weights.
     19 
     20 Iterating over all pairs of pieces of cake is enough to get AC, but you can solve the problem in $O(n \log n)$ by sorting the weights and printing the sum of the last $2$ values, or even in $O(n)$ if you calculate the maximum and the second maximum in linear time.
     21 
     22 Complexity: $O(t \cdot n^2)$, $O(t \cdot n \log n)$ or $O(t \cdot n)$
     23 
     24 Official solution: [150288088](/contest/1654/submission/150288088 "Submission 150288088 by emorgan")
     25 
     26 [1654B - Prefix Removals](/contest/1654/problem/B)
     27 
     28 Author: [emorgan](/profile/emorgan "International Grandmaster emorgan")  
     29  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     30 
     31 **Hint 1**
     32 
     33 Are there any characters that you can never remove?
     34 
     35 **Hint 2**
     36 
     37 You can't remove the rightmost occurrence of each letter. Can you remove the other characters?
     38 
     39 **Hint 3**
     40 
     41 If you can remove $s_1, s_2, \dots, s_{i-1}$ and $s_i$ is not the rightmost occurrence of a letter, you can also remove $s_i$.
     42 
     43 **Solution**
     44 
     45 Let $a$ be the initial string. For a string $z$, let's define $z(l, r) = z_lz_{l+1} \dots z_r$, i.e., the substring of $z$ from $l$ to $r$. The final string is $a(k, n)$ for some $k$.
     46 
     47 In the final string, $x = 0$, so the first character doesn't appear anywhere else in $s$. This means that $a_k\not=a_{k+1}, a_{k+2}, \dots, a_n$. In other words, $a_k$ is the rightmost occurrence of a letter in $s$.
     48 
     49 Can you ever remove $a_i$, if $a_i\not=a_{i+1}, a_{i+2}, \dots, a_n$? Notice that you would need to remove $a(l, r)$ ($l \leq i \leq r$): this means that there must exist $a(l', r') = a(l, r)$ for some $l' \gt l$. So, $a_{i+l'-l} = a_i$, and this is a contradiction.
     50 
     51 Therefore, $k$ is the smallest index such that $a_k\not=a_{k+1}, a_{k+2}, \dots, a_n$.
     52 
     53 You can find $k$ by iterating over the string from right to left and updating the frequency of each letter. Indeed $a_i\not=a_{i+1}, a_{i+2}, \dots, a_n$ if and only if the frequency of the letter $a_i$ is $0$ up to now (in the iteration from right to left we are performing). The value of $k$ is the minimum such index $i$.
     54 
     55 Complexity: $O(n)$
     56 
     57 Official solution: [150288210](/contest/1654/submission/150288210 "Submission 150288210 by emorgan")
     58 
     59 [1654C - Alice and the Cake](/contest/1654/problem/C)
     60 
     61 Author: [emorgan](/profile/emorgan "International Grandmaster emorgan")  
     62  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     63 
     64 **Hint 1**
     65 
     66 Can you find the initial weight which results in $a$?
     67 
     68 **Hint 2**
     69 
     70 The initial weight is the sum of the final weights. Let's simulate the division, starting from a new cake. How to choose fast which splits to do?
     71 
     72 **Hint 3**
     73 
     74 If the largest piece is not in $a$, you have to split it. How to find the largest piece efficiently?
     75 
     76 **Hint 4**
     77 
     78 Keep $a$ and the new cake in two multisets or priority queues.
     79 
     80 **Solution**
     81 
     82 First, let's find the initial weight. When a piece of cake is split, the sum of weights is $\lfloor\frac{w}{2}\rfloor + \lceil\frac{w}{2}\rceil$:
     83 
     84 * if $w$ is even, $\lfloor\frac{w}{2}\rfloor + \lceil\frac{w}{2}\rceil = \frac{w}{2} + \frac{w}{2} = w$;
     85 * if $w$ is odd, $\lfloor\frac{w}{2}\rfloor + \lceil\frac{w}{2}\rceil = \frac{w-1}{2} + \frac{w+1}{2} = w$.
     86 
     87 Therefore, the sum of weights is constant, and the initial weight is the sum of the final weights.
     88 
     89 Now let's start from a cake $b$ of weight $b_1 = \sum_{i=1}^n a_i$, split it (into pieces of weight $b_i$) and try to make it equal to $a$. At any moment, it's convenient to consider the largest $b_i$, because you can determine if you can split it or not.
     90 
     91 More specifically,
     92 
     93 * if $b_i$ is not in $a$, you have to split it;
     94 * if $b_i = a_j$ for some $j$, you can only match $a_j$ with $b_i$ or with a $b_k$ such that $b_k = a_j = b_i$ (because there doesn't exist any larger $b_k$): that's equivalent to removing $a_j$ and $b_i$ from $a$, $b$, respectively.
     95 
     96 Notice that, if at any moment the maximum element of $b$ is smaller than the maximum element of $a$, the answer is `NO`.
     97 
     98 If can keep $a$ and $b$ in any data structure that supports inserting an integer, asking for the maximum and removing the maximum (e.g., multiset or priority queue), the following algorithm works.
     99 
    100 While either $a$ or $b$ is not empty,
    101 
    102 * if the maximum element of $b$ is smaller than the maximum element of $a$, print `NO` and break;
    103 * if the maximum element of $b$ is equal to the maximum element of $a$, remove it from both $a$ and $b$;
    104 * if the maximum element $m$ of $b$ is larger than the maximum element of $a$, remove it from $b$ and split the piece of cake (i.e., insert $\lfloor\frac{w}{2}\rfloor$ and $\lceil\frac{w}{2}\rceil$ into $b$).
    105 
    106 If $a$ or $b$ are both empty at the end, the answer is `YES`.
    107 
    108 Complexity: $O(n \log n)$
    109 
    110 Official solution: [150288232](/contest/1654/submission/150288232 "Submission 150288232 by emorgan")
    111 
    112 [1654D - Potion Brewing Class](/contest/1654/problem/D)
    113 
    114 Author: [emorgan](/profile/emorgan "International Grandmaster emorgan")  
    115  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    116 
    117 **Hint 1**
    118 
    119 The $n-1$ facts make a tree.
    120 
    121 **Hint 2**
    122 
    123 Assume that the amount of ingredient $1$ is $1$. For each $i$, the amount of ingredient $i$ would be $c_i/d_i$ for some integer $c_i, d_i \gt 0$. How to make an integer amount of each ingredient?
    124 
    125 **Hint 3**
    126 
    127 The optimal amount of ingredient $1$ is $\text{lcm}(d_1, d_2, \dots, d_n)$.
    128 
    129 **Hint 4**
    130 
    131 Can you find the exponent of each prime $p \leq n$ in $\text{lcm}(d_1, d_2, \dots, d_n)$?
    132 
    133 **Hint 5**
    134 
    135 If you visit the nodes in DFS order, each edge changes the exponent of $O(\log n)$ primes. At each moment, keep the factorization of $c_i/d_i$ of the current node, i.e., the exponents of each $p \leq n$ (they can be negative). For each $p$, also keep the minimum exponent so far.
    136 
    137 **Solution**
    138 
    139 Read the hints. The rest is just implementation.
    140 
    141 Start a DFS from node $1$. Keep an array $f$ such that $f_p$ is the exponent of $p$ in the amount of ingredients of the current node. Keep also $v_i = c_i/d_i \,\, \text{mod} \,\, 998\,244\,353$. At the beginning, the amount of ingredients (of node $1$) is $1$, so $f_p = 0$ for each $p$. Whenever you move from node $i$ to node $j$, and $r_i/r_j = x/y$,
    142 
    143 * for each $p^k$ such that $p^k \mid x$ and $p^{k+1} \nmid x$, decrease $f_p$ by $k$;
    144 * for each $p^k$ such that $p^k \mid y$ and $p^{k+1} \nmid y$, increase $f_p$ by $k$.
    145 
    146 Notice that there exist $O(\log n)$ such values of $p^k$ for each edge, and you can find them by precalculating either the smallest prime factor (with the sieve of Eratosthenes) or the whole factorization of every integer in $[2, n]$.
    147 
    148 Let $g_p$ be the minimum value of $f_p$ during the DFS. Then, for every $p$, you have to multiply the amount of ingredients of node $1$ by $p^{-g_p}$.
    149 
    150 The answer is the sum of $v_i$, multiplied by the amount of ingredients of node $1$.
    151 
    152 Complexity: $O(n \log n)$
    153 
    154 Official solution: [150288255](/contest/1654/submission/150288255 "Submission 150288255 by emorgan")
    155 
    156 [1654E - Arithmetic Operations](/contest/1654/problem/E)
    157 
    158 Author: [emorgan](/profile/emorgan "International Grandmaster emorgan")  
    159  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    160 
    161 **Hint 1**
    162 
    163 Consider each element of the array as being a point in the plane $(i, a_i)$. Then all of the elements that *don't* get affected by an operation lie on a single line in the plane. Find a line that maximizes the number of points on it.
    164 
    165 **Hint 2**
    166 
    167 Let $m$ be the upper bound on $a_i$. The intended complexity is $O(n \sqrt m)$.
    168 
    169 **Hint 3**
    170 
    171 Let $m$ be the upper bound on $a_i$. Let $d$ be the difference between adjacent elements in the final array. Create a piecewise algorithm for the cases where $|d| \lt \sqrt m$ and $|d| \geq \sqrt m$
    172 
    173 **Solution**
    174 
    175 As explained in the hints, instead of computing the fewest number of operations, we will compute the largest number of elements that don't have an operation on them, and we will create a piecewise algorithm with final complexity $O(n\sqrt m)$ , where $m$ is the upper bound on $a_i$.
    176 
    177 Let $d$ be the common difference between elements in our final sequence. First of all, I will assume that $d \geq 0$, since solving the problem for negative $d$ is as simple as reversing the array and running the solution again. If $d$ is fixed beforehand, we can solve the problem in $O(n)$ by putting element $i$ into bucket $a_i-d\cdot i$ and returning $n$ minus the size of the biggest bucket.
    178 
    179 For $d \lt \sqrt m$, we can use the above algorithm to handle all of these $d$ in $O(n \sqrt m)$ time. We can keep a hashmap from bucket index $\to$ number of elements in the bucket, or we can just keep an array since the bucket indices have a range of at most $O(n \sqrt m)$ which is not enough to exceed the memory limit.
    180 
    181 For $d \geq \sqrt m$, we observe that if we have two indices $i, j$ such that $j \gt i+\sqrt m$, then at least one of them definitely has to have an operation performed on it, because the difference between them would have to be $a_j-a_i \geq \sqrt m \cdot d \gt m$ which is not possible. In other words, if we consider the set of elements which are not edited, that set will have gaps between pairs of elements of size at most $\sqrt m$.
    182 
    183 So, we can build a graph between indices with an edge $i \to j$ with label $x$ if $i \lt j \leq i+\sqrt m$ and $\frac{a_j-a_i}{j-i} = x$. This graph has at most $n\sqrt m$ edges. Then we just have to find the longest path in the graph where all edges have the same label. You can do this with dynamic programming -- let $dp_{i,d}$ be the length of the longest path ending at index $i$, where all edges have label $d$. For each $i$, we only need to check edges to $j$ where $i - \sqrt m \lt j \lt i$. This means the time complexity is $O(n\sqrt m)$. To store the values $dp_{i,d}$ sparsely, we can use either a hash map or a rotating buffer (where we only store $dp_{i,d}$ for $i$ in a sliding window of width $\sqrt m$).
    184 
    185 Complexity: $O(n \sqrt m)$
    186 
    187 Official solution: [150288285](/contest/1654/submission/150288285 "Submission 150288285 by emorgan")
    188 
    189 [1654F - Minimal String Xoration](/contest/1654/problem/F)
    190 
    191 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994"), [emorgan](/profile/emorgan "International Grandmaster emorgan")  
    192  Preparation: [dario2994](/profile/dario2994 "International Grandmaster dario2994"), [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    193 
    194 **Hint 1**
    195 
    196 Let $f(s, x)$ be the string $t$ such that $t_i = s_{i\oplus x}$. The intended solution not only finds the $x$ such that $f(s, x)$ is lexicographically minimized, but produces an array of all $0 \leq x \lt 2^n$ sorted according the comparator $f(s, i) \lt f(s, j)$.
    197 
    198 **Hint 2**
    199 
    200 The solution is similar to the standard method to construct a suffix array.
    201 
    202 **Hint 3**
    203 
    204 Let $a_k$ be an array of the integers $0$ through $2^n-1$, sorted according to the lexicographic ordering of the first $2^k$ characters of $f(s, x)$. The answer to the problem is $f(s, a_{n,0})$. Given the array $a_{k-1}$, can you compute $a_k$?
    205 
    206 **Solution**
    207 
    208 Let $f(s, x)$ be the string $t$ such that $t_i = s_{i\oplus x}$.
    209 
    210 The solution is inspired by the standard method to construct a suffix array. Let $a_k$ be an array containing the integers $0, 1, 2,\dots, 2^n-1$, sorted according to the lexicographic ordering of the prefixes of length $2^k$ of the strings $f(s, 0), f(s, 1), \dots, f(s, 2^n-1)$ (i.e., the prefix of length $2^k$ of $f(s, a_k[i])$ is lexicographically smaller or equal than the prefix of length $2^k$ of $f(s, a_k[i+1])$). We can construct $a_k$ using $a_{k-1}$, and $a_0$ is easy to construct as a base case.
    211 
    212 In order to construct $a_k$ from $a_{k-1}$, we will first construct an auxiliary array of integers $v$ using $a_{k-1}$, where $v_i \lt v_j$ iff $f(s, i)_{0..2^{k-1}} \lt f(s, j)_{0..2^{k-1}}$. Then, we will sort the array $a_k$ according to the comparison of tuples $(v_i, v_{i\oplus {2^{k-1}}}) \lt (v_j, v_{j\oplus {2^{k-1}}})$.
    213 
    214 Once we have $a_n$, then we just print $f(s, a_{n,0})$. In total, the solution takes $O(2^n n^2)$ time, which can be optimized to $O(2^n n)$ using the fact that tuples of integers in the range $[0, m]$ can be sorted using radix sort in $O(m)$ time. This optimization was not required to get AC.
    215 
    216 Official solution: [150288326](/contest/1654/submission/150288326 "Submission 150288326 by emorgan")
    217 
    218 [1654G - Snowy Mountain](/contest/1654/problem/G)
    219 
    220 Author: [emorgan](/profile/emorgan "International Grandmaster emorgan")  
    221  Preparation: [dario2994](/profile/dario2994 "International Grandmaster dario2994"), [emorgan](/profile/emorgan "International Grandmaster emorgan"), [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    222 
    223 **Hint 1**
    224 
    225 Let's say that a vertex is "flippable" if it has at least one neighbor of the same height. The optimal strategy for a skier is to ski to a flippable vertex with lowest height, flip back and forth between that vertex and its neighbor until all energy is used, and then ski to a base lodge.
    226 
    227 **Hint 2**
    228 
    229 Assuming the skier starts at vertex $v$ and chooses vertex $u$ as the flippable vertex to flip back and forth at, this skier will "waste" a total of $h_u$ units of kinetic energy for a total path length of $2h_v-h_u$. Note that if no such $u$ exists, then the maximum amount of $h_v$ will be wasted as the skier goes straight to a base lodge. Let $w_v$ be this "wasted" amount. Instead of computing the maximum path length for the skier starting at vertex $v$, compute $w_v$. The answer for that vertex is $2h_v-w_v$.
    230 
    231 **Hint 3**
    232 
    233 Try to solve this seemingly unrelated problem: Let $S$ be the set of flippable vertices. What is the largest possible value of $\sum\limits_{v\in S}h_v$?
    234 
    235 **Hint 4**
    236 
    237 The largest possible value of $\sum\limits_{v\in S}h_v$ is $O(n)$. Therefore, there are at most $O(\sqrt n)$ distinct values of $w_v$ across all vertices. Solve for each value of $w_v$ separately.
    238 
    239 **Solution**
    240 
    241 Read the hints. The rest is just implementation.
    242 
    243 For each set of flippable vertices of the same height, we can calculate the set of starting vertices which are able to reach at least one vertex in that flippable set. To do this, split the graph up into layers of equal height. Let $c_v$ be the minimum required energy to reach a vertex in the flippable set. $c_v$ can be computed via shortests paths, where edges in the same layer have weight $1$ and edges from layer $i$ to $i+1$ have weight $-1$. We can use bfs to relax the costs of vertices in a single layer, and then easily transition to the next layer. We do this for $O(\sqrt n)$ different starting heights, so the total complexity is $O(n\sqrt n)$.
    244 
    245 Official solution: [150288345](/contest/1654/submission/150288345 "Submission 150288345 by emorgan")
    246 
    247 [1654H - Three Minimums](/contest/1654/problem/H)
    248 
    249 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994"), [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    250  Preparation: [dario2994](/profile/dario2994 "International Grandmaster dario2994"), [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    251 
    252 **Hint 1**
    253 
    254 If $p_1,\dots, p_n$ is good and $p_i=1$, what can you say about $p_1,p_2,\dots, p_i$ and $p_i,p_{i+1},\dots, p_n$?
    255 
    256 **Hint 2**
    257 
    258 Find a quadratic solution ignoring the constraints given by the string $s$.
    259 
    260 **Hint 3**
    261 
    262 Find an $O(n^2 + nm)$ solution taking care of the constraints given by the string $s$.
    263 
    264 **Hint 4**
    265 
    266 Optimize the $O(n^2+nm)$ solution using generating functions.
    267 
    268 **Hint 5**
    269 
    270 The solution to the ODE $y'(t) = a(t)y(t) + b(t)$ with $y(0)=1$ is given by $\exp(\smallint a)\Big(1+\int b\exp(-\smallint a)\Big)$
    271 
    272 **Solution**
    273 
    274 First of all, let us state the following lemma (which is sufficient to solve the problem in $O(n^2)$ if one ignores the constraints given by the string $s$). We omit the proof as it is rather easy compared to the difficulty of the problem as a whole.
    275 
    276 **Lemma**: The following statements hold for a permutation $p_1,p_2,\dots, p_n$.
    277 
    278 * $p$ is good if and only if $p[1:i]$ and $p[i:n]$ are good, where $p_i = 1$.
    279 * If $p_1=1$, then $p$ is good if and only if $p[1:i]$ and $p[i:n]$ are good, where $p_i = 2$.
    280 * If $p_1=1$ and $p_n=2$, then $p$ is good if and only if it is bitonic, i.e., $p_1 \lt p_2 \lt p_3 \lt \cdots \lt p_i \gt p_{i+1} \gt \cdots p_{n-1} \gt p_n$, where $p_i=n$.
    281 
    282 Given $1\le l \lt r\le n$, we say that a permutation $q_1,q_2,\dots, q_{r-l+1}$ of ${1,2,\dots, r-l+1}$ is *$[l,r]$-consistent* if for any $l\le i \le \min(r, m-1)$:
    283 
    284 * $q_{i-l+1} \lt q_{i-l+2}$ if $s_i = \texttt{ \lt }$;
    285 * $q_{i-l+1} \gt q_{i-l+2}$ if $s_i = \texttt{ \gt }$.
    286 
    287 Informally speaking, a permutation is $[l,r]$-consistent if it satisfies the constraints given by $s$ when it is written in the positions $[l, r]$.
    288 
    289 For $1\le l \lt r\le n$, let $a_{\ast\ast}(l, r)$, $a_{1\ast}(l, r)$, $a_{\ast 1}(l, r)$, $a_{12}(l, r)$, $a_{21}(l, r)$ be the the number of good permutations which are $[l,r]$-consistent and, respectively,
    290 
    291 * No additional conditions;
    292 * Start with $1$;
    293 * End with $1$;
    294 * Start with $1$ and end with $2$;
    295 * Start with $2$ and end with $1$.
    296 
    297 For $1\le i \lt n$ and $c\in{\texttt{ \lt }, \texttt{ \gt }}$, let $q(i, c) := [i \gt m\text{ or } s_i= c]$. Informally speaking, $q(i, \texttt{ \lt })$ is $1$ if and only if it can be $p_i \lt p_{i+1}$ and $q(i, \texttt{ \gt })$ is $1$ if and only if it can be $p_i \gt p_{i+1}$.
    298 
    299 Thanks to the Lemma, one has the following relations:
    300 
    301 * $a_{\ast\ast}(l, r) = \sum_{i=l}^r a_{\ast1}(l, i) a_{1\ast}(i, r) \binom{r-l}{i-l}$.
    302 * $a_{1\ast}(l, l) = 1$. For $l \lt r$, $a_{1\ast}(l, r) = \sum_{i=l+1}^r a_{12}(l, i)a_{1\ast}(i, r)\binom{r-l-1}{i-l-1}$.
    303 * Analogous formula for $a_{\ast 1}$.
    304 * $a_{12}(l, l) = 0$ and $a_{12}(l, l+1)= q(l, \texttt{ \lt })$ and $a_{12}(l, l+2)= q(l, \texttt{ \lt })\cdot q(l+1, \texttt{ \gt })$. For $l \lt l+1 \lt r$, $a_{12}(l, r) = q(l, \texttt{ \lt })a_{21}(l+1, r) + q(r-1, \texttt{ \gt })a_{12}(l, r-1)$.
    305 * Analogous formula for $a_{21}$.
    306 
    307 The problem asks to compute $a_{\ast\ast}(1, n)$. Thanks to the formulas stated above, it is straightforward to implement an $O(n^2)$ solution. Now we will tackle the hard task of optimizing it to $O(nm + n\log(n))$.
    308 
    309 In order to compute $a_{\ast\ast}(1, n)$, we will compute $a_{\ast1}(1, k)$ and $a_{1\ast}(k, n)$ for all $1\le k\le n$.
    310 
    311 We have the recurrence relation (for $k\ge 2$)
    312 
    313 $\tag{1} a_{\ast1}(1, k) = \sum_{i=1}^k a_{\ast1}(1, i) a_{21}(i, k) \binom{k-2}{i-1} $
    314 
    315 Setting $x_{k-1} := a_{\ast1}(1, k) / (k-1)!$, (1) is equivalent to (for $k\ge 1$, and also for $k=0$!)
    316 
    317 $\tag{2} k\cdot x_k = \sum_{i=0}^{k-1} x_i \frac{a_{21}(i+1, k+1)}{(k-1-i)!}. $
    318 
    319 This looks very similar to an identify between generating functions (a derivative on the left, a product on the right); but for the fact that $a_{21}$ depends on two parameters. To overcome this issue let us proceed as follows.
    320 
    321 Notice that, if we set $b$ to any of the functions $a_{\ast\ast}$, $a_{\ast1}$, $a_{1\ast}$, $a_{12}$, $a_{21}$, it holds $b(l, r) = b(l+1, r+1)$ whenever $l \gt m$. Hence, let us define $b_{\ast\ast}(k) = a_{\ast\ast}(n+1, n+k)$ and analogously $b_{1\ast}(k)$, $b_{\ast 1}(k)$, $b_{12}(k)$, $b_{21}(k)$.
    322 
    323 With these new definitions, (2) becomes (for $k\ge 0$)
    324 
    325 $\tag{3} k\cdot x_k = \sum_{i=0}^{k-1} x_i \frac{b_{21}((k-1-i) + 2)}{(k-1-i)!} + \sum_{i=0}^{\min(k-1, m-1)} x_i \frac{a_{21}(i+1, k+1) - b_{21}(k+1-i)}{(k-1-i)!} . $
    326 
    327 Let $u_i:= \frac{b_{21}(i+2)}{i!}$ and $v_{k-1}:= \sum_{i=0}^{\min(k-1, m-1)} x_i \frac{b_{21}(k+1-i) - a_{21}(i+1, k+1)}{(k-1-i)!}$. So, (3) simplifies to
    328 
    329 $ \tag{4} k\cdot x_k = v_{k-1} + \sum_{i=0}^{k-1} x_i u_{k-1-i} .$
    330 
    331 We precompute in $O(nm)$ the values of $a_{12}(l, r)$ and $a_{21}(l, r)$ for $1\le l\le m$, $l \lt r\le n$. We can also precompute in $O(n)$ the values of $b_{12}(k), b_{21}(k)$ for $1\le k\le n$. In $O(m^2)$ we compute also $x_i$ for all $0\le i\le m-1$. Thus, in $O(nm)$ we can compute, for all $0\le k \lt n$, the values $u_k$.
    332 
    333 It is now time to start working with generating functions. Let $X(t):= \sum_{k\ge 0} x_k t^k$, $U(t):=\sum_{k\ge0} u_kt^k$, $V(t):=\sum_{k\ge0} v_kt^k$. We know $U(t)$ and $V(t)$ (at least the first $n$ coefficients) and we want to compute $X(t)$. Since $x_0=1$, we know $X(0)=1$. Moreover (4) is equivalent to the ordinary differential equation $X' = V + U\cdot X$. This ODE is standard and its (unique) solution is given by
    334 
    335 $ X = \exp(\smallint U)\Big(1 + \int V\exp(-\smallint U)\Big).$
    336 
    337 Since the product of generating functions and the exponential of a generating function can be computed in $O(n\log(n))$, we are able to obtain the values of $x_k$ for all $0\le k \lt n$ and thus the values of $a_{\ast 1}(1,k)$.
    338 
    339 Now, let us see how to compute $a_{1\ast}(k, n)$. Since $a_{1\ast}(k,n) = b_{1\ast}(n-k+1)$ for all $m \lt k\le n$, let us first compute $b_{1\ast}(k)$ for all $1\le k\le n$. By repeating verbatim the reasoning above, we get that the generating function $Y(t):=\sum_{k\ge 0} y_k t^k$, where $y_{k-1}:=b_{1\ast}(k) / (k-1)!$, is given by ($V=0$ in this case) $Y=\exp(\int U)$. So, it remains only to compute $a_{1\ast}(k, n)$ for $1\le k\le m$. This can be done naïvely in $O(nm)$.
    340 
    341 The overall complexity is $O(nm + n\log(n))$.
    342 
    343 Official solution: [150306974](/contest/1654/submission/150306974 "Submission 150306974 by dario2994")