• Epic
• Good
• Moderate
• Bad
• Horrendous

• Epic
• Good
• Moderate
• Bad
• Horrendous

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.

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

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.

343539998

• Epic
• Good
• Moderate
• Bad
• Horrendous

For simplicity, let's denote $$$f(a[l,r])$$$ as $$$f(l,r)$$$.

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]$$$.

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.

343541349

• Epic
• Good
• Moderate
• Bad
• Horrendous

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.

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.

343541478

• Epic
• Good
• Moderate
• Bad
• Horrendous

It is not hard to see that the following property holds:

• 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$$$.

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:

• Query the subsequence $$$S \cup {i}$$$ and gain the result $$$x$$$.
• If the result is nonzero, then we know that $$$a_i=x$$$.
• Otherwise, let's assign $$$S \leftarrow S \cup {i}$$$.

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.

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.

Thus, this solution uses exactly $$$3n$$$ queries (or $$$3n-1$$$ if you would) to discover the values of all $$$2n$$$ elements.

343541838

• Epic
• Good
• Moderate
• Bad
• Horrendous

Let us define an minimal set of rectangles as a set of rectangles on the grid that satisfy the following conditions:

• 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$$$.

Then, let us call the minimal set of rectangles with maximum cardinality the exhaustive minimal set $$$\mathbb{S}$$$.

This set $$$\mathbb{S}$$$ satisfies the following conditions:

• The set $$$\mathbb{S}$$$ is unique.

• $$$|\mathbb{S}| \le {{n}\choose{2}}\cdot m$$$

• $$$\sum_\limits{(u,d,l,r) \in \mathbb{S}} {(r-l+1)} \le 2 \cdot {{n}\choose{2}} \cdot m$$$

• 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.

Elements of $$$\mathbb{S}$$$ can be enumerated in $$$\mathcal{O}(n^2m)$$$ time by the following algorithm:

• 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$$$.

• Then, $$$(u,d,i_j,i_{j+1})$$$ is an element of $$$\mathbb{S}$$$ for all $$$1 \le j \lt k$$$.

It can be shown that the algorithm finds all elements of $$$\mathbb{S}$$$.

Then, it suffices to propagate the area of each rectangle $$$(u,d,l,r) \in \mathbb{S}$$$ to all cells covered by it.

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)$$$.

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.

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.

343541956

• Epic
• Good
• Moderate
• Bad
• Horrendous

Let's solve the easy version first: all $$$a_i = -1$$$.

We can convert the condition to: for $$$0 \leq i \leq n$$$, $$$a_i = \sum_{a_j=i} j$$$.

Since $$$a_0=-1$$$, we can only consider $$$j \gt 0$$$ and get $$$a_0 = \sum_{a_j=0}j$$$ automatically.

We have a claim: for a cool polynomial and all $$$i \gt 0$$$, there are only three cases:

• Case $$$1$$$: $$$a_i = 0$$$.

• Case $$$2$$$: $$$a_i = i$$$.

• Case $$$3$$$: $$$a_i = j$$$ and $$$a_j = i$$$, where $$$i \neq j$$$.

Thus, we can write an easy DP:

$$$dp_i=2dp_{i−1}+(i−1)dp_{i−2}$$$

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.

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.

343542108

• Epic
• Good
• Moderate
• Bad
• Horrendous

For this problem there exist two versions of a core observation required for solutions:

• When you discard all elements other than suffix minimums, the optimal total cost does not change. (1.a)
• 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)

(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.

(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.

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.

We give you three solutions to solve subtask 1, two of which are helpful in solving subtask 2, while the other one is not.

For the first solution of subtask 1, we show the following.

• The optimal total cost is no greater than $$$2\log_2(a_n)$$$. (2.1.a)

We will show this by an approximate algorithm that constructs a partition that might be suboptimal.

Consider the following method to partition the sequence.

Starting from the last element of the sequence, we expand the left border of the leftmost subarray greedily:

• If it is possible to use a subarray of cost $$$2$$$, then do use it.
• Otherwise, use a subarray of cost $$$1$$$.

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)$$$.

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

This solution has a time complexity of $$$\mathcal{O}(nC)=\mathcal{O}(n \log a)$$$.

For the second solution of the first subtask, we show the following.

• There is always an optimal solution which only uses subarrays with cost at most $$$3$$$. (2.2.a)

We will show this by exchange arguments.

Observe that for any $$$X \ge 4$$$ there exists a pair of integers $$$(x,y)$$$ that satisfies the following conditions:

• $$$x \cdot y \ge X$$$
• $$$x + y \le X$$$
• $$$1 \le x,y \lt X$$$

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.

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$$$.

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$$$.

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)$$$.

The third solution of the first subtask strays away from using any observation and abuses the cost function directly.

Recall that the cost function is as follows:

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})$$$.

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.

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

Before reading, please read the solutions to the first subtask (and hopefully identify the two solutions that are helpful in solving the second subtask).

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.

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.

Recall the following:

• There will be only at most $$$2\log_2(a_r)$$$ different values of $$$\operatorname{opt}(i,r)$$$. (Direct consequence of 2.1.a)
• Our DP to compute $$$\operatorname{opt}(1,r)$$$ is monotonic, i.e. $$$\operatorname{opt}(i,r) \ge \operatorname{opt}(i+1,r)$$$. (= 1.b)

Using the above, we can infer the following.

• 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.

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.

So, how would we formulate this DP? Let us define a new function:

• $$$\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$$$).

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.

So let's think of how we will compute values of $$$\operatorname{opt}'(c,r)$$$ for one $$$r$$$ in $$$\mathcal{O}(C)$$$ time.

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.

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.

We can find the following correct DP transition:

• $$$\operatorname{opt}'(c,r)=r+1$$$ (when $$$c \le 0$$$)
• $$$\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$$$)

The correctness of this DP transition is shown by 1.b and 2.2.a.

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.

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.

343542209

343542358

• Epic
• Good
• Moderate
• Bad
• Horrendous

First, we will solve the easier problem of computing just single coefficients $$$[x^k] F(n)$$$. For this, observe the following facts.

• It takes $$$\Theta((n+m) \log (n+m))$$$ time to multiply two polynomials of size $$$n$$$ and $$$m$$$ using FFT.

• However, it takes $$$\Theta(\min(n,m))$$$ time to retrieve only one coefficient from their product.

Let's consider how we can make a tradeoff between these two time complexities.

To make a meaningful tradeoff in time complexity, we can use something that resembles the Baby Step-Giant Step algorithm.

Formally, consider the following method:

• Select a constant $$$B \gt 1$$$ arbitrarily.

• 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.

• For all $$$0 \le k \le B$$$, precompute $$$F(k)$$$. This takes $$$\mathcal{O}({B}^2)$$$ time.

• 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.

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.

We only have two issues left:

• We have to compute the prefix sum of $$$[x^i]F(n)$$$ instead of just $$$[x^k]F(n)$$$.
• Our algorithm is going to be slow, especially under the modulus $$$10^9+7$$$ which makes FFT quite inconvenient.

For the first issue, observe the following:

• 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$$$.

The proof is left as a practice for the reader.

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.

For the second issue, observe the following:

• By expressing $$$(F(n+1))'$$$ in two ways, we can conclude that $$$n F(n) (F(1))' = (F(n))'F(1)$$$.

• 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)$$$.

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.

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.

343542463

• Epic
• Good
• Moderate
• Bad
• Horrendous

An important observation is that $$$f(l, p+i)$$$ is unimodal for $$$1 \le i \le l$$$.

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.

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)$$$.

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$$$.

After this, we obtain several monotonic contiguous segments. The classic priority queue method is used to obtain the top $$$m$$$ smallest values.

343542554