2159.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")