codeforces-scrape

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

2160.md (28299B)


      1 Source: https://codeforces.com/blog/entry/147322
      2 
      3 Thanks for the participation! We hope you enjoyed the contest.
      4 
      5 **Rate the contest!**
      6 
      7 * Epic
      8 * Good
      9 * Moderate
     10 * Bad
     11 * Horrendous
     12 
     13 The solution codes will be added shortly after the system tests are finished. They have been added.
     14 
     15 [2160A - MEX Partition](/contest/2160/problem/A "Codeforces Round 1058 (Div. 2)")
     16 
     17 Problem Credit: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
     18 
     19 **Rate the problem!**
     20 
     21 * Epic
     22 * Good
     23 * Moderate
     24 * Bad
     25 * Horrendous
     26 
     27 **Solution**
     28 
     29 First, let $m=\operatorname{mex}(A)$. We can ignore all elements that are greater than $m$. This is because since $m$ is the mex, $m$ does not appear in $A$, and consequently it also cannot appear in any of the partitions. Thus, which of the partitions each element goes to does not matter.
     30 
     31 Now, let's consider the number $0$. Suppose there is at least one $0$ in $A$. Then, at least one multiset in the partition must contain $0$ (because each element in $A$ must be in one multiset in the partition). This also implies that all multisets must contain $0$, as otherwise the $\operatorname{mex}$ of all multisets cannot be the same (it is $0$ for some, but greater than $0$ for others).
     32 
     33 Once we reach the conclusion that $0$ must be present in all partitions, we can make the same conclusion for $1,2,\ldots,m-1$. That is, $m$ is the only possible score.
     34 
     35 **Code (chromate00)**
     36 
     37 [343539998](/contest/2160/submission/343539998 "Submission 343539998 by chromate00")
     38 
     39 [2160B - Distinct Elements](/contest/2160/problem/B "Codeforces Round 1058 (Div. 2)")
     40 
     41 Problem Credit: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
     42 
     43 **Rate the problem!**
     44 
     45 * Epic
     46 * Good
     47 * Moderate
     48 * Bad
     49 * Horrendous
     50 
     51 **Solution**
     52 
     53 For simplicity, let's denote $f(a[l,r])$ as $f(l,r)$.
     54 
     55 First, notice that $f(l,r)\leq f(l,r+1)$. This is trivially true because each unique element that appears in the range $(l,r)$ must appear in $(l,r+1)$ also. Now, $f(l,r+1)$ is either equal to $f(l,r)$ if $a_{r+1}$ already appeared, or $f(l,r)+1$ if $a_{r+1}$ does not appear in $[l,r]$.
     56 
     57 Now, expanding $b_i-b_{i-1}$ yields $f(i,i) + (f(i-1,i)-f(i-1,i-1))+(f(i-2,i)-f(i-2,i-1))+\ldots+(f(1,i)-f(1,i-1))$. From the above, we know that $f(l,i) \neq f(l,i-1)$ only when $a_i$ does not appear in $[l,i-1]$. Let $x$ be the largest integer such that $f(x,i-1)=f(x,i)$. Note that this implies that $a_x=a_i$. For all $y \gt x$, we have $f(y, i) - f(y,i-1) = 1$. Thus, we have $b_i-b_{i-1}=i-(i-x) = x$, because all terms of the expansion above are $1$ except for the ones corresponding to indices $x$ to $i-1$. Since we know that $a_x = a_i$, and $x = b_i - b_{i-1}$, we should set $a_i$ to be the same as $a_{b_i-b_{i-1}}$. There is one more case where $x$ is undefined, because $f(y,i) \neq f(y,i-1)$ for all $y \geq 1$. This implies $a_i$ did not appear before in the array. We can just set $a_i$ to any unused number arbitrarily.
     58 
     59 **Code (chromate00)**
     60 
     61 [343541349](/contest/2160/submission/343541349 "Submission 343541349 by chromate00")
     62 
     63 [2160C - Reverse XOR](/contest/2160/problem/C "Codeforces Round 1058 (Div. 2)")
     64 
     65 Problem Credit: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
     66 
     67 **Rate the problem!**
     68 
     69 * Epic
     70 * Good
     71 * Moderate
     72 * Bad
     73 * Horrendous
     74 
     75 **Solution**
     76 
     77 Let's view $x$, $f(x)$, and $x \oplus f(x)$ each as $y$-bit numbers (where $y$ is the smallest integer with $2^y \gt x$). We can see that $x \oplus f(x)$ is necessarily a palindrome. This is because the last bit of $x \oplus f(x)$ is the XOR of the last bit of $x$ and the first bit of $f(x)$. But since $f(x)$ is just $x$ reversed, this simplifies to the last bit of $x$ XOR'ed with the first bit of $x$. Now, look at the first bit. It is the XOR of first bit of $x$ and the first bit of $f(x)$. By similar reasoning, this also simplifies to the first bit of $x$ and the last bit of $x$. We can use the same argument to argue that the second and second to last, third and third to last bit, etc. are all the same. This is what a palindrome is.
     78 
     79 One caveat is that although $x$ is not allowed to have leading zeroes (by our definition of $y$), both $f(x)$ and $x \oplus f(x)$ is. Thus, if we let $z$ be the smallest integer with $2^z \gt n$, then $y$ is not necessarily equal to $z$. Fortunately, using our palindrome condition, we can find the number of leading zeroes $n$ must have (it is the same as the number of trailing zeroes in the binary representation of $n$). This is how we can find $y$. There is one more trick — suppose $z$ is odd and there exists a middle. If the middle digit is $1$, then we cannot find an integer $x$ with $x \oplus f(x)=n$. This is because the middle digit is the result of XOR between a bit and itself in $x$ (since it is in the middle), and both $1 \oplus 1$ and $0 \oplus 0$ results in $0$. Note all other digits are allowed to be either $1$ or $0$. If the result is $0$, we can place a $1$ in both the corresponding left bit and corresponding right bit. If the result is $1$, we can arbitrarily place a $1$ in the left bit and a $0$ in the right bit, and this is possible if the left bit and right bit are not the same.
     80 
     81 **Code (chromate00)**
     82 
     83 [343541478](/contest/2160/submission/343541478 "Submission 343541478 by chromate00")
     84 
     85 [2159A - MAD Interactive Problem](/contest/2159/problem/A "Codeforces Round 1058 (Div. 1)")
     86 
     87 Problem Credit: [wuhudsm](/profile/wuhudsm "Master wuhudsm")
     88 
     89 **Rate the problem!**
     90 
     91 * Epic
     92 * Good
     93 * Moderate
     94 * Bad
     95 * Horrendous
     96 
     97 **Solution**
     98 
     99 It is not hard to see that the following property holds:
    100 
    101 * For some subsequence $T$ and index $i$ such that $i \notin T$, let the query results be $0$ for $T$ and $x \neq 0$ for $T \cup {i}$. Then, we gain the information that $a_i=x$.
    102 
    103 To use this property to our advantage, let's maintain a subsequence $S$ whose query result is known to be $0$. Consider the following subroutine:
    104 
    105 * Query the subsequence $S \cup {i}$ and gain the result $x$.
    106 * If the result is nonzero, then we know that $a_i=x$.
    107 * Otherwise, let's assign $S \leftarrow S \cup {i}$.
    108 
    109 If we perform this subroutine for $i=1,2,\ldots,2n$, we gain the information about all $a_i$ such that its value appeared **for the second time**. We now need to find the other $n$ elements' values.
    110 
    111 Notice that currently the subsequence $S$ contains each of $1,2,\ldots,n$ **exactly once**, and **so does** $[1,2n] \setminus S$. Therefore, we assign $S \leftarrow ([1,2n] \setminus S)$ and perform the subroutine over all undiscovered indices again. Each run of the subroutine will give you a nonzero result, and give you the values of the $n$ undiscovered elements in $n$ additional queries.
    112 
    113 Thus, this solution uses exactly $3n$ queries (or $3n-1$ if you would) to discover the values of all $2n$ elements.
    114 
    115 **Code (_istil)**
    116 
    117 [343541838](/contest/2159/submission/343541838 "Submission 343541838 by chromate00")
    118 
    119 [2159B - Rectangles](/contest/2159/problem/B "Codeforces Round 1058 (Div. 1)")
    120 
    121 Problem Credit: [chromate00](/profile/chromate00 "Expert chromate00")
    122 
    123 UPD: I sincerely apologize about the weak pretests of the problem. I have greatly underestimated the runtime and memory usage of the worst solutions, while still wanting to be generous about slower solutions. This has led to weak tests during contest. Deeply sorry about the bad contest experiences affected by this.
    124 
    125 **Rate the problem!**
    126 
    127 * Epic
    128 * Good
    129 * Moderate
    130 * Bad
    131 * Horrendous
    132 
    133 **Solution**
    134 
    135 Let us define an **minimal** set of rectangles as a set of rectangles on the grid that satisfy the following conditions:
    136 
    137 * For all rectangles $(u,d,l,r)$ in the set, there is no other rectangle $(u,d,l',r')$ on the grid such that $l \le l' \le r' \le r$ and $r'-l' \lt r-l$.
    138 
    139 Then, let us call the minimal set of rectangles with maximum cardinality the **exhaustive minimal set** $\mathbb{S}$.
    140 
    141 This set $\mathbb{S}$ satisfies the following conditions:
    142 
    143 * The set $\mathbb{S}$ is unique.
    144 * $|\mathbb{S}| \le {{n}\choose{2}}\cdot m$
    145 * $\sum_\limits{(u,d,l,r) \in \mathbb{S}} {(r-l+1)} \le 2 \cdot {{n}\choose{2}} \cdot m$
    146 * For each covered cell $(x,y)$ on the rectangle, there is at least one rectangle in $\mathbb{S}$ that covers $(x,y)$ with minimum area.
    147 
    148 Elements of $\mathbb{S}$ can be enumerated in $\mathcal{O}(n^2m)$ time by the following algorithm:
    149 
    150 * For all pairs $u,d$ of rows, enumerate columns $i_1,i_2,\ldots,i_k$ such that $G_{u,i_j}=G_{d,i_j}$ for all $j$.
    151 * Then, $(u,d,i_j,i_{j+1})$ is an element of $\mathbb{S}$ for all $1 \le j \lt k$.
    152 
    153 It can be shown that the algorithm finds all elements of $\mathbb{S}$.
    154 
    155 Then, it suffices to propagate the area of each rectangle $(u,d,l,r) \in \mathbb{S}$ to all cells covered by it.
    156 
    157 This can be done in multiple ways, but the simplest out of all such ways is keeping a range DP for each column and propagating the values based on $\text{dp}[u][d] \le \text{dp}[u][d+1]$ and $\text{dp}[u][d] \le \text{dp}[u-1][d]$. Then, the value of $\text{dp}[i][i]$ on column $j$ becomes the answer for cell $(i,j)$.
    158 
    159 Finally, the conditions satisfied by $\mathbb{S}$ are also satisfied when the grid is transposed, so if $n \gt m$ you can simply compute the same way on the transposed grid. This gives us a solution with $\mathcal{O}(nm \min(n,m))=\mathcal{O}(nm\sqrt{nm})$ complexity.
    160 
    161 Enumerating all elements of $\mathbb{S}$ and saving it in memory might take $\mathcal{O}(nm \min(n,m))$ memory, but it may still pass if sufficiently optimized. There is a way to modify the solution to use only $\mathcal{O}(\min(n,m)(n+m))$ memory, which is left as a practice for the reader.
    162 
    163 **Code (chromate00, O(min(n,m)(n+m)) memory)**
    164 
    165 [343541956](/contest/2159/submission/343541956 "Submission 343541956 by chromate00")
    166 
    167 [2159C - Twin Polynomials](/contest/2159/problem/C "Codeforces Round 1058 (Div. 1)")
    168 
    169 Problem Credit: [wuhudsm](/profile/wuhudsm "Master wuhudsm")
    170 
    171 **Rate the problem!**
    172 
    173 * Epic
    174 * Good
    175 * Moderate
    176 * Bad
    177 * Horrendous
    178 
    179 **Solution**
    180 
    181 Let's solve the easy version first: all $a_i = -1$.
    182 
    183 We can convert the condition to: for $0 \leq i \leq n$, $a_i = \sum_{a_j=i} j$.
    184 
    185 Since $a_0=-1$, we can only consider $j \gt 0$ and get $a_0 = \sum_{a_j=0}j$ automatically.
    186 
    187 We have a claim: for a cool polynomial and all $i \gt 0$, there are only three cases:
    188 
    189 * Case $1$: $a_i = 0$.
    190 * Case $2$: $a_i = i$.
    191 * Case $3$: $a_i = j$ and $a_j = i$, where $i \neq j$.
    192 
    193 **Proof**
    194 
    195 Use the method of proof by contradiction. Assuming a cool polynomial does not meet the above conditions.
    196 
    197 Let $m$ be the minimum positive index not meeting the above three conditions.
    198 
    199 * If there is no index $j \gt m$ satisfying $a_{j} = m$, we get $a_m=0$ or $a_m=m$, which meets condition $1$ or $2$.
    200 * If there is only one index $j \gt m$ satisfying $a_{j} = m$, we get $a_m=j$, which meets condition $3$.
    201 * If there two indices $j,k \gt m$ such that $a_{j} = m$, $a_{k} = m$. We can get some indices $x_1,x_2,...$ satisying $\sum x_i=m$ and $a_{x_i}=j$, and some indices $y_1,y_2,...$ satisying $\sum y_i=m$ and $a_{y_i}=k$. This contradicts the fact that $m$ is the minimum positive index not meeting the above three conditions. In other words, you can not find such indices $x_1,x_2,...$ and $y_1,y_2,\ldots$
    202 * For more indices, the proof is the same as above.
    203 
    204 Thus, we can write an easy DP:
    205 
    206 $dp_i=2dp_{i−1}+(i−1)dp_{i−2}$
    207 
    208 Now, let’s return to the original problem. For all $a_i \neq -1$, we need to check whether they form "valid coefficients"(if the coefficients can represent at least one cool polynomial). After that, the problem reduces to the easy version.
    209 
    210 There are several ways to check validity. Cases $1$ and $2$ are trivial. For Case $3$, we can use DSU to merge $i$ and $j$, and then check the size of each connected component.
    211 
    212 **Code (wuhudsm)**
    213 
    214 [343542108](/contest/2159/submission/343542108 "Submission 343542108 by chromate00")
    215 
    216 [2159D1 - Inverse Minimum Partition (Easy Version)](/contest/2159/problem/D1 "Codeforces Round 1058 (Div. 1)"), [2159D2 - Inverse Minimum Partition (Hard Version)](/contest/2159/problem/D2 "Codeforces Round 1058 (Div. 1)")
    217 
    218 Problem Credit: [chromate00](/profile/chromate00 "Expert chromate00"), [wuhudsm](/profile/wuhudsm "Master wuhudsm"); Special Thanks: [satyam343](/profile/satyam343 "Candidate Master satyam343")
    219 
    220 **Rate the problem!**
    221 
    222 * Epic
    223 * Good
    224 * Moderate
    225 * Bad
    226 * Horrendous
    227 
    228 This problem's editorial will be divided into parts. You may need to read all of them to understand the full picture.
    229 
    230 **Part 1**
    231 
    232 For this problem there exist two versions of a core observation required for solutions:
    233 
    234 * When you discard all elements other than suffix minimums, the optimal total cost does not change. (1.a)
    235 * Denoting optimal total cost for sequence $b_l,b_{l+1},\ldots,b_r$ as $\operatorname{opt}(l,r)$, it can be shown that $\operatorname{opt}(l-1,r) \ge \operatorname{opt}(l,r)$ for all $1 \lt l \le r \le n$. (1.b)
    236 
    237 (1.a) can be shown by exchange arguments. Assume a partition consists mainly of two subarrays (and some irrelevant others), $[\dots,[x_1,\dots,x_p],\dots,[y_1,\dots,y_q,\dots,y_r],\dots]$. Then, if $x_p \ge y_q$, you can find a partition $[\dots,[x_1,\dots,y_q],[y_{q+1},\dots,y_r],\dots]$ which is at least good as the original one. Likewise, if $x_p \ge y_r$, you can find a partition $[\dots,[x_1,\dots,y_r],\dots]$ which is at least as good as the original one. Repeating this exchange process on any "optimal" partition, you will now have another "optimal" partition whose endpoints all belong to suffix minimums. And because then the denominator of $\mathtt{cost}$ will always lie on a suffix minimum, you can discard all of the rest without changing the total cost.
    238 
    239 (1.b) can be shown much easier. Consider the $\mathcal{O}(n^2)$ algorithm to compute $\operatorname{opt}$. We know that $\operatorname{opt}(l,r)=\min\limits_{i=l}^{r}{(\operatorname{opt}(i+1,r)+c[l,i])}$ where $c[l,r]\ge 0$ for all $1 \le l \le r \le n$. Also, observe $c[l,r] \ge c[l+1,r]$ for all $l \lt r$. As all terms that constitute the minimum possible value of $\operatorname{opt}(l,r)$ are no less than that of $\operatorname{opt}(l+1,r)$, $\operatorname{opt}(l,r) \ge \operatorname{opt}(l+1,r)$ indeed does hold.
    240 
    241 Both observations hold similar implications, and all subsequent observations for subtask 1 can be shown for both observations. While (1.a) is much convenient for implementing the solution for subtask 1, we will prove all subsequent observations using (1.b) because it will be reused in subtask 2 also.
    242 
    243 We give you **three** solutions to solve subtask 1, **two** of which are helpful in solving subtask 2, while **the other one** is not.
    244 
    245 **Part 2.1**
    246 
    247 For the first solution of subtask 1, we show the following.
    248 
    249 * The optimal total cost is no greater than $2\log_2(a_n)$. (2.1.a)
    250 
    251 We will show this by an **approximate algorithm** that constructs a partition that might be suboptimal.
    252 
    253 Consider the following method to partition the sequence.
    254 
    255 Starting from the last element of the sequence, we expand the left border of the leftmost subarray greedily:
    256 
    257 * If it is possible to use a subarray of cost $2$, then do use it.
    258 * Otherwise, use a subarray of cost $1$.
    259 
    260 In either event, the rightmost element of the leftmost subarray must be strictly less than the one on the previous leftmost subarray. By contradiction, this event cannot happen more than $\log_2(a_n)$ times. As we only used subarrays of cost no greater than $2$, this algorithm always constructs a partition with total cost no greater than $2 \log_2(a_n)$.
    261 
    262 As now we know that the optimal total cost is no greater than $C = 128 \ge 2 \log_2(a_n)$, we can optimize the $\mathcal{O}(n^2)$ DP into a solution that resembles two-pointers, but we will use $C$ pointers on one side for each possible cost. This is possible due to the monotonicity that we proved either as a corollary of (1.a) or by (1.b).
    263 
    264 This solution has a time complexity of $\mathcal{O}(nC)=\mathcal{O}(n \log a)$.
    265 
    266 **Part 2.2**
    267 
    268 For the second solution of the first subtask, we show the following.
    269 
    270 * There is always an optimal solution which **only uses subarrays with cost at most $3$.** (2.2.a)
    271 
    272 We will show this by exchange arguments.
    273 
    274 Observe that for any $X \ge 4$ there exists a pair of integers $(x,y)$ that satisfies the following conditions:
    275 
    276 * $x \cdot y \ge X$
    277 * $x + y \le X$
    278 * $1 \le x,y \lt X$
    279 
    280 The proof for the above is simple; $x=\left \lceil {\frac{X}{2}}\right \rceil$ and $y=2$ satisfies the conditions for all $X \ge 4$. Then, it is possible to divide a subarray $A$ into two subarrays $P$, $Q$ such that $\mathtt{cost}(P) \le x$ and $\mathtt{cost}(Q) \le y$. Formally, assume a subarray $A=[A_1,A_2,\ldots,A_k]$ where $\mathtt{cost}(A)=X$. Let $A_i$ be the unique element for which $y \cdot A_i \lt A_k$ and $y \cdot A_j \ge A_k$ for all $i \lt j \le k$. Here, $A_i$ may be $A_1$. This element $A_i$ always exists, and we can divide $A$ into $P=[A_1,A_2,\ldots,A_i]$ and $Q=[A_{i+1},A_{i+2},\ldots,A_k]$. Then, it is easy to show that $\mathtt{cost}(P) \le x$ and $\mathtt{cost}(Q) \le y$. This defines an "exchange scheme" which will never worsen the total cost while decreasing the maximum subarray cost used.
    281 
    282 Repeating this process on an optimal partition, the new partition has a total cost not worse than the original, and will only use subarrays with cost at most $3$.
    283 
    284 We can show that this bound is tight by construction. Namely, the sequence $[3,4,8,9]$ has total cost $3$, and splitting it into any $2$ or more subarrays will have total cost at least $4$.
    285 
    286 Applying this to the solution outlined in 2.1, you get a solution with time complexity $\mathcal{O}(n)$. Alternatively, you can use data structures such as segment tree for a solution with time complexity $\mathcal{O}(n \log n)$.
    287 
    288 **Part 2.3**
    289 
    290 The third solution of the first subtask strays away from using any observation and abuses the cost function directly.
    291 
    292 Recall that the cost function is as follows:
    293 
    294 $\mathtt{cost}(b)=\left \lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}} \right \rceil$
    295 
    296 Considering $\min(a_{j+1},\ldots,a_{i})$ as a constant, $\mathtt{cost}([a_{j+1},\ldots,a_i])+\operatorname{opt}(1,j)$ can be regarded a linear function of $a_i$ rounded up. Therefore, we can consider using Convex Hull Trick to optimize our $\mathcal{O}(n^2)$ DP. The only caveat is how to use Convex Hull Trick with changing values of $\min(a_{j+1},\ldots,a_{i})$.
    297 
    298 This can be resolved by maintaining values of $\min(a_{j+1},\ldots,a_{i})$ using a monotone stack. We can simply keep the minimum value of $\operatorname{opt}(1,j)$ for same values of $\min(a_{j+1},\ldots,a_{i})$. The updates that might happen on the CHT structure are maintainable if you can roll back the CHT structure (like we did the monotone stack); and a Li-Chao Tree can be rolled back quite easily as its inner behaviour is not different from a segment tree.
    299 
    300 This leads us to a solution with time complexity $\mathcal{O}(n \log {1/\epsilon})$. Certain solutions with too big constants can get MLE under the given constraints, but there exist solutions with small enough constants that use `double` instead of whatever other type you might want to use. Why such solutions are still correct is left as a practice for the reader (seriously, you should be able to take a guess if you understood the other "more elegant" solutions).
    301 
    302 **Part 3 (for Hard subtask)**
    303 
    304 Before reading, please read the solutions to the first subtask (and hopefully identify the two solutions that are helpful in solving the second subtask).
    305 
    306 Directly applying the most optimal DP solution to the first subtask, we have a solution with $\mathcal{O}(n^2)$ time complexity. However, it seems hard to improve further as even our optimal DP has $\mathcal{O}(n)$ states and it looks like that can't be helped with.
    307 
    308 However, we somehow already have enough resources to improve it even further; there is a way to know all values $\operatorname{opt}(1,r),\operatorname{opt}(2,r),\ldots,\operatorname{opt}(r,r)$ without using $\mathcal{O}(n)$ states.
    309 
    310 Recall the following:
    311 
    312 * There will be only at most $2\log_2(a_r)$ different values of $\operatorname{opt}(i,r)$. (Direct consequence of 2.1.a)
    313 * Our DP to compute $\operatorname{opt}(1,r)$ is monotonic, i.e. $\operatorname{opt}(i,r) \ge \operatorname{opt}(i+1,r)$. (= 1.b)
    314 
    315 Using the above, we can infer the following.
    316 
    317 * We can model another DP by swapping the places of cost and index, and this new DP will only have at most $C=128 \ge 2\log_2(a_r)$ states.
    318 
    319 This "swapping cost and index" might sound like it's so unexpected, but surely you may have seen such a DP formulation if you have solved many DP problems. Namely, this technique is used in Knapsack problems when the cost is small and the capacity is huge.
    320 
    321 So, how would we formulate this DP? Let us define a new function:
    322 
    323 * $\operatorname{opt}'(c,r)$: minimum value of $l$ such that $\operatorname{opt}(l,r) \le c$ ($0 \le c \le C$, $1 \le r \le n$).
    324 
    325 Then, we can see by 1.b that $\operatorname{opt}'(c+1,r) \le \operatorname{opt}'(c,r)$ for all $0 \le c$. Also, after we know $\operatorname{opt}'(c,r)$ and $\operatorname{opt}'(c+1,r)$, we can compute the range of $l$ such that $\operatorname{opt}(l,r) = c$, and it lets us find the sum of $\operatorname{opt}(l,r)$ over all $1 \le i \le r$ in $\mathcal{O}(C)$ time.
    326 
    327 So let's think of how we will compute values of $\operatorname{opt}'(c,r)$ for one $r$ in $\mathcal{O}(C)$ time.
    328 
    329 Let us first precompute the **minimum** $l$ such that $\mathtt{cost}([a_l,a_{l+1},\ldots,a_i]) \le c$ for all $i$ and $c$. By 2.2.a, it suffices to compute this for only $1 \le c \le 3$. We will denote this as $L(i,c)$. These values can be easily preprocessed using walk on segment tree in $\mathcal{O}(n \log n)$ time. This will come in handy for our new DP formulation.
    330 
    331 In the formulation of our original $\mathcal{O}(n)$ DP for the first subtask, we required a pointer for each cost $1 \le c \le 3$ on one side. On the new formulation, however, we will need some transition directly for indices. This is where the values $L(i,c)$ comes in handy.
    332 
    333 We can find the following correct DP transition:
    334 
    335 * $\operatorname{opt}'(c,r)=r+1$ (when $c \le 0$)
    336 * $\operatorname{opt}'(c,r)= \min_\limits{1 \le k \le 3} \left ({\min_\limits{\max(\operatorname{opt}'(c-k,r)-1,0) \le i \le r}{L(i,k)}}\right )$ (when $c \gt 0$)
    337 
    338 The correctness of this DP transition is shown by 1.b and 2.2.a.
    339 
    340 Because we have already preprocessed the values of $L(i,1)$, $L(i,2)$, $L(i,3)$ in $\mathcal{O}(n \log n)$ time, we can now construct a RMQ data structure for these values in $\mathcal{O}(n \log n)$ time for $\mathcal{O}(1)$ query time. This allows us to process all values of $\operatorname{opt}'(c,r)$ for one $r$ in $\mathcal{O}(C)$ time according to the transition described above.
    341 
    342 Computing this for each $r$ independently, we have now computed the sum of $\operatorname{opt}(l,r)$ over all $1 \le l \le r \le n$ in $\mathcal{O}(n \log n + n \log a)$ time. The problem is solved.
    343 
    344 **Code (chromate00, Easy Part 2.1)**
    345 
    346 [343542209](/contest/2159/submission/343542209 "Submission 343542209 by chromate00")
    347 
    348 **Code (chromate00, Hard)**
    349 
    350 [343542358](/contest/2159/submission/343542358 "Submission 343542358 by chromate00")
    351 
    352 [2159E - Super-Short-Polynomial-San](/contest/2159/problem/E "Codeforces Round 1058 (Div. 1)")
    353 
    354 Problem Credit: [chromate00](/profile/chromate00 "Expert chromate00"); Special Thanks: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED"), [zeemanz](/profile/zeemanz "Grandmaster zeemanz")
    355 
    356 **Rate the problem!**
    357 
    358 * Epic
    359 * Good
    360 * Moderate
    361 * Bad
    362 * Horrendous
    363 
    364 **Solution**
    365 
    366 First, we will solve the easier problem of computing just single coefficients $[x^k] F(n)$. For this, observe the following facts.
    367 
    368 * It takes $\Theta((n+m) \log (n+m))$ time to multiply two polynomials of size $n$ and $m$ using FFT.
    369 * However, it takes $\Theta(\min(n,m))$ time to retrieve only one coefficient from their product.
    370 
    371 Let's consider how we can make a tradeoff between these two time complexities.
    372 
    373 To make a meaningful tradeoff in time complexity, we can use something that resembles the *Baby Step-Giant Step* algorithm.
    374 
    375 Formally, consider the following method:
    376 
    377 * Select a constant $B \gt 1$ arbitrarily.
    378 * For all $kB \le N$, precompute the polynomial $\mathcal{F}(k)=F(kB)$. This takes $\mathcal{O}(N \log N \cdot \frac{N}{B}) = \mathcal{O}(\frac{N^2}{B} \log N)$ time.
    379 * For all $0 \le k \le B$, precompute $F(k)$. This takes $\mathcal{O}({B}^2)$ time.
    380 * For each query, find the respective coefficient of $F(n)=\mathcal{F}({\left \lfloor{n/B}\right \rfloor}) F(n \bmod B)$. This takes $\mathcal{O}(\min(N,B))=\mathcal{O}(B)$ time.
    381 
    382 Then, we achieve an algorithm that runs in $\mathcal{O}(\frac{N^2}{B}\log N + B^2 + QB)$ time. By adjusting $B$ to $B \approx \sqrt{N \log N}$, we can achieve an algorithm that runs in $\mathcal{O}((N+Q)\sqrt{N \log N})$ time.
    383 
    384 We only have two issues left:
    385 
    386 * We have to compute the prefix sum of $[x^i]F(n)$ instead of just $[x^k]F(n)$.
    387 * Our algorithm is going to be slow, especially under the modulus $10^9+7$ which makes FFT quite inconvenient.
    388 
    389 For the first issue, observe the following:
    390 
    391 * Define a polynomial $G(n)$ of infinite degree such that $[x^k]G(n)=\sum_\limits{i=0}^{k}[x^i]F(n)$. Then, $G(n+m) = G(n) F(m)$ holds for all $n,m \ge 0$.
    392 
    393 The proof is left as a practice for the reader.
    394 
    395 Then, we can transform $\mathcal{F}(k)=F(kB)$ to $\mathcal{G}(k)=G(kB)$ easily in $\mathcal{O}(N)$ time for each, and then the algorithm can compute the respective coefficient of $G(n)=\mathcal{G}({\left \lfloor{n/B}\right \rfloor})F(n \bmod B)$ in $\mathcal{O}(\min(\infty,B))=\mathcal{O}(B)$ time likewise. It is not required to save infinitely many coefficients of $G(n)$; the coefficients $[x^k]G(n)$ are constant for $k \gt 2n$. Thus we have resolved the first issue.
    396 
    397 For the second issue, observe the following:
    398 
    399 * By expressing $(F(n+1))'$ in two ways, we can conclude that $n F(n) (F(1))' = (F(n))'F(1)$.
    400 * Then, comparing the coefficients of both sides, we can derive the coefficients of $F(n)$ in $\mathcal{O}(nk)$ time where $k=\operatorname{deg}(F(1))=\mathcal{O}(1)$.
    401 
    402 This gives us an alternative way to precompute polynomials $\mathcal{F}(k)=F(kB)$, and using this, the algorithm will run in $\mathcal{O}(\frac{N^2}{B} + B^2 + QB)$ time. By adjusting $B$ to $B \approx \sqrt{N}$, we achieve an algorithm that runs in $\mathcal{O}((N+Q)\sqrt{N})$ and does not use FFT. This fits nicely in the given time limit of $7$ seconds.
    403 
    404 Depending on implementation, some smaller values of $B$ might lead to a MLE verdict. However, if this happens, your submission should fail on the first test case as the precomputation itself uses the most amount of memory. It is fine to adjust the value of $B$ larger as there is quite some margin in the time limit. Slower programming languages might also get a TLE verdict, but the implementation for the intended solution should be simple enough to be translated to C++ in a few minutes.
    405 
    406 **Code (chromate00)**
    407 
    408 [343542463](/contest/2159/submission/343542463 "Submission 343542463 by chromate00")
    409 
    410 [2159F - Grand Finale: Snakes](/contest/2159/problem/F "Codeforces Round 1058 (Div. 1)")
    411 
    412 Problem Credit: [wuhudsm](/profile/wuhudsm "Master wuhudsm")
    413 
    414 **Rate the problem!**
    415 
    416 * Epic
    417 * Good
    418 * Moderate
    419 * Bad
    420 * Horrendous
    421 
    422 **Solution**
    423 
    424 An important observation is that $f(l, p+i)$ is unimodal for $1 \le i \le l$.
    425 
    426 **Proof**: If $f(l, x) \lt f(l, x+1)$, then the snake head at time $T = x+1$ is the maximum value, and this value will not leave the snake's body until at least $l$ seconds later.
    427 
    428 Thus, for a snake of length $l$, we can divide it into $\lfloor \frac{n}{l} \rfloor$ segments and perform ternary search on each segment. The total number of segments is $O(n \log n)$, and the total number of queries is $O(n \log^2 n)$.
    429 
    430 We also need to handle the case where $f(l, M_1) = f(l, M_2)$. Suppose $i \gt 1$ and $a_{i,j} = f(l, M_1) = f(l, M_2)$, the snake reaches $a_{i,j}$ at time $T = i + j - 1$. We determine whether $M_1$ is in the increasing or decreasing half by querying $f(l, i + j - 2)$. A similar approach is used for $i = 1$.
    431 
    432 After this, we obtain several monotonic contiguous segments. The classic priority queue method is used to obtain the top $m$ smallest values.
    433 
    434 **Code (wuhudsm)**
    435 
    436 [343542554](/contest/2159/submission/343542554 "Submission 343542554 by chromate00")