Thank you everyone for participating!
Here is the Blog Link and the Contest Link
A. Squarefree Pairs
Idea and prepared by: Akshayy-Singh- $$$S(n,m)$$$ is the answer: add up $$$\gcd(i,j)$$$ over all pairs $$$1\le i\le n$$$, $$$1\le j\le m$$$ whose gcd is squarefree.
- $$$\mu(d)$$$ (Möbius function): $$$\mu(1)=1$$$. If some prime squared divides $$$d$$$, then $$$\mu(d)=0$$$. Otherwise $$$\mu(d)=+1$$$ if $$$d$$$ has an even number of prime factors and $$$-1$$$ if it has an odd number. For example $$$\mu(6)=+1$$$, $$$\mu(7)=-1$$$, $$$\mu(12)=0$$$.
- $$$\varphi(e)$$$ (Euler's totient): how many numbers from $$$1$$$ to $$$e$$$ have no common factor with $$$e$$$ other than $$$1$$$. For example $$$\varphi(6)=2$$$, because only $$$1$$$ and $$$5$$$ qualify.
- "Divide" always means integer division, rounded down.
For pairs with gcd equal to $$$1$$$, a well-known trick is to add up $$$\mu(d)$$$ over all $$$d$$$ that divide the gcd. Here the condition is "the gcd is squarefree" instead of "the gcd is 1". Is there a similar sum of $$$\mu$$$ values that equals $$$1$$$ when a number is squarefree and $$$0$$$ otherwise?
Try adding up $$$\mu(d)$$$ over every $$$d$$$ whose square divides $$$x$$$. Write $$$x$$$ as a product of prime powers, for example $$$360 = 2^3 \cdot 3^2 \cdot 5^1$$$. Only squarefree $$$d$$$ matter, because the other $$$d$$$ have $$$\mu(d)=0$$$. Which primes can such a $$$d$$$ use? Think about how many times each prime divides $$$x$$$.
Use the identity with $$$x=\gcd(i,j)$$$ and swap the order of adding, so that $$$d$$$ is the outer loop. The condition "$$$d^2$$$ divides the gcd" means "$$$d^2$$$ divides $$$i$$$ and $$$d^2$$$ divides $$$j$$$". Now write $$$i = d^2\cdot a$$$ and $$$j = d^2\cdot b$$$. What happens to $$$\gcd(i,j)$$$?
After this step you need the plain sum of $$$\gcd(a,b)$$$ over a rectangle $$$1\le a\le A$$$, $$$1\le b\le B$$$, for many different $$$(A,B)$$$. Every number $$$k$$$ equals the sum of $$$\varphi(e)$$$ over all divisors $$$e$$$ of $$$k$$$. For example, $$$6$$$ has divisors $$$1,2,3,6$$$ and $$$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6)=1+1+2+2=6$$$. Apply this to $$$k=\gcd(a,b)$$$ and swap the order of adding: for each $$$e$$$, how many pairs $$$(a,b)$$$ have both numbers divisible by $$$e$$$?
You should now have a sum over $$$k$$$ of $$$\varphi(k)\cdot(A / k)\cdot(B / k)$$$. The two quotients $$$A/k$$$ and $$$B/k$$$ stay the same for long stretches of $$$k$$$. What do you need to precompute to add up $$$\varphi$$$ over a whole stretch in one step? And how many times do you need to sieve?
Step 1: handle the squarefree condition. For every positive integer $$$x$$$:
Why this is true. Write $$$x$$$ as a product of prime powers, for example $$$360 = 2^3\cdot 3^2\cdot 5^1$$$. Call a prime heavy if it divides $$$x$$$ at least twice. In $$$360$$$ the heavy primes are $$$2$$$ and $$$3$$$. Let $$$h$$$ be the number of heavy primes.
Only squarefree $$$d$$$ can contribute, because the other $$$d$$$ have $$$\mu(d)=0$$$. A squarefree $$$d$$$ has $$$d^2$$$ dividing $$$x$$$ exactly when every prime of $$$d$$$ is heavy. So the allowed $$$d$$$ are all products of some of the heavy primes (including the empty product, which is $$$1$$$). For $$$360$$$ these are $$$1, 2, 3, 6$$$ with $$$\mu$$$ values $$$+1,-1,-1,+1$$$.
- If $$$h=0$$$, the only allowed $$$d$$$ is $$$1$$$, and the sum is $$$\mu(1)=1$$$. This is the case where $$$x$$$ is squarefree.
- If $$$h\ge 1$$$, pick one heavy prime $$$p$$$. Pair each allowed $$$d$$$ that doesn't contain $$$p$$$ with the one obtained by multiplying by $$$p$$$. The two have opposite $$$\mu$$$ values, so every pair cancels and the sum is $$$0$$$.
So the sum is $$$1$$$ when $$$x$$$ is squarefree and $$$0$$$ otherwise.
Step 2: swap the order of adding. Replace the condition on $$$\gcd(i,j)$$$ using Step 1. We get
Pairs where $$$d^2$$$ divides both numbers look like $$$i=d^2 a$$$ and $$$j=d^2 b$$$, with $$$1\le a\le A$$$ and $$$1\le b\le B$$$, where $$$A = n / d^2$$$ and $$$B = m / d^2$$$ (rounded down). For these pairs $$$\gcd(i,j)=d^2\cdot\gcd(a,b)$$$. Therefore
where $$$T(A,B)$$$ is the sum of $$$\gcd(a,b)$$$ over all $$$1\le a\le A$$$ and $$$1\le b\le B$$$. We only need $$$d$$$ with $$$d^2\le\min(n,m)$$$, because otherwise there are no such pairs. We can also skip every $$$d$$$ with $$$\mu(d)=0$$$.
Step 3: compute $$$T(A,B)$$$. Every positive integer $$$k$$$ equals the sum of $$$\varphi(e)$$$ over all divisors $$$e$$$ of $$$k$$$. Why: take the $$$k$$$ fractions $$$\frac1k,\frac2k,\dots,\frac kk$$$ and reduce each to lowest terms. Every reduced denominator $$$e$$$ divides $$$k$$$, and exactly $$$\varphi(e)$$$ of the fractions end up with denominator $$$e$$$. Counting all fractions gives $$$k$$$.
Apply this to $$$k=\gcd(a,b)$$$. A divisor $$$e$$$ of $$$\gcd(a,b)$$$ is a number dividing both $$$a$$$ and $$$b$$$, so we can add up by $$$e$$$ first. For a fixed $$$e$$$, there are $$$A/e$$$ choices of $$$a$$$ and $$$B/e$$$ choices of $$$b$$$ (rounded down). That gives
Step 4: make it fast. The values $$$A/k$$$ and $$$B/k$$$ stay constant over long stretches of consecutive $$$k$$$. For example, with $$$A=B=10$$$ the stretches are $$${1},{2},{3},{4,5},{6,\dots,10}$$$, so only $$$5$$$ groups instead of $$$10$$$ terms.
If the current stretch starts at $$$k$$$, it ends at
Every term in the stretch has the same two quotients, so the stretch contributes $$$(\varphi(k)+\varphi(k+1)+\dots+\varphi(k'))\cdot(A/k)\cdot(B/k)$$$.
To get the sum of $$$\varphi$$$ over a stretch in one step, precompute prefix sums: $$$P[x]=\varphi(1)+\dots+\varphi(x)$$$. Then the stretch sum is $$$P[k'] - P[k-1]$$$. Keep $$$P$$$ reduced modulo $$$10^9+7$$$ so the products stay inside long long.
Step 5: the whole algorithm. 1. Read all test cases and find the largest $$$n$$$ or $$$m$$$ in the input; call it $$$N$$$. 2. Run one sieve up to $$$N$$$ that computes $$$\mu$$$ and $$$\varphi$$$ for every number, and build the prefix sums $$$P$$$. 3. For each test case, go through $$$d=1,2,\dots$$$ while $$$d^2\le\min(n,m)$$$. Skip $$$d$$$ if $$$\mu(d)=0$$$. Otherwise compute $$$T(n/d^2,\;m/d^2)$$$ with the stretch method, then add $$$d^2\cdot T$$$ to the answer if $$$\mu(d)=1$$$ or subtract it if $$$\mu(d)=-1$$$, always modulo $$$10^9+7$$$.
B. Can We?
Idea and prepared by: lolzxii$$$a_i + a_j$$$ is odd only when $$$a_i$$$ and $$$a_j$$$ is of different parities.
What happens if the array consists entirely of even numbers, or entirely of odd numbers? Can you perform any operations at all?
If both parities exist, does the ability to swap opposite parities allow you to reach any permutation of the array?
We can divide the problem into two simple cases based on the presence of even and odd numbers in the array:
1. Case 1: All elements have the same parity (either all even or all odd):
No operation can ever be performed, so just check if the original array is already sorted.
2. When both the parities are present in the array:
Array can always be sorted in this case.
C. Bounds-Duel
Idea and prepared by: NorLuiThe statement says a player with no legal moves loses. Can that ever actually happen?
The winner depends only on whether the final $$$N$$$ is divisible by $$$D$$$. While the number is being built, what do you really need to remember about the current prefix?
Think backwards from the end. Once all $$$k$$$ digits are written, the player who would move next is exactly the one who did not write the last digit. When do they win?
First, nobody ever gets stuck. Since $$$L \le R$$$, the empty prefix can be extended to some valid $$$N$$$, and after every legal move the prefix is still extendable by definition. So whatever the current prefix is, there is some valid $$$N$$$ that starts with it, and the next digit of that $$$N$$$ is a legal move. That means the "no legal moves" rule never applies and the game always lasts exactly $$$k$$$ moves.
Now, what do we need to know about a prefix?
- Its value modulo $$$D$$$, because only $$$N \bmod D$$$ matters at the end.
- Whether it is still equal to the prefix of $$$L$$$, and whether it is still equal to the prefix of $$$R$$$. This is the usual digit DP "tight" flag, here one for each bound.
If the prefix is tight with $$$L$$$, the next digit has to be at least $$$L$$$'s digit at that position. If it's tight with $$$R$$$, the next digit can be at most $$$R$$$'s digit. Otherwise the digit is free. The legal digits are exactly the ones in this range.
Also notice that the game is the same for both players: the rules don't care who is Alice and who is Bob. So instead of tracking players, let's define
where $$$r$$$ is the prefix modulo $$$D$$$, and $$$tl$$$, $$$th$$$ are the two tight flags.
Base case ($$$pos = k$$$): the "player to move" here is the one who didn't write the last digit. They win exactly when $$$N$$$ is not divisible by $$$D$$$, so $$$win[k][r][\cdot][\cdot] = (r \neq 0)$$$.
Transition: this is a normal game DP. A position is winning if you can move to a position that is losing for your opponent:
where $$$lo = tl \,?\, L_{pos} : 0$$$, $$$hi = th \,?\, R_{pos} : 9$$$, $$$tl' = tl \land (d = L_{pos})$$$ and $$$th' = th \land (d = R_{pos})$$$.
Alice moves first from the empty prefix, so the answer is "Alice" if $$$win[0][0][1][1]$$$ is true and "Bob" otherwise.
We only need the layer $$$pos+1$$$ to compute layer $$$pos$$$, so we keep two arrays of size $$$4D$$$. The total work is $$$O(k \cdot 4 \cdot D \cdot 10)$$$ per test. Since $$$\sum D \le 2 \cdot 10^5$$$, that's at most about $$$1.4 \cdot 10^8$$$ very simple operations overall.
D. Path Fracture
Idea and prepared by: lolzxiiSuppose a tree is fractured into $$$L$$$ connected components with sizes $$$s_1, s_2, \dots, s_L$$$ such that $$$\sum_{i=1}^L s_i = n$$$. How many ways are there to add $$$L-1$$$ edges between these components to form a single connected tree?
The total sum of $$$k$$$ over all queries is bounded by $$$2 \cdot 10^5$$$. We cannot afford to traverse the whole tree for each query. Which standard data structure allows us to process a subset of nodes and their connecting paths in $$$O(k \log k)$$$ time?
How can we compute the product of component sizes along long paths without traversing them node by node?
By a generalized version of Cayley’s Formula, the number of ways to connect $$$L$$$ components of sizes $$$s_1, s_2, \dots, s_L$$$ into a single tree is:
We want to find the number of ways $$$T$$$ to connect $$$L$$$ components of sizes $$$s_1, s_2, \dots, s_L$$$ (with $$$\sum s_i = n$$$) into a single tree using $$$L-1$$$ edges.
Consider the set $$$\mathcal{M}$$$ of all rooted, directed component trees with a designated global root $$$r \in V$$$. We count $$$\vert{}\mathcal{M}\vert{}$$$ in two ways:
Way 1: Top-Down
1. Choose a global root $$$r$$$ ($$$n$$$ choices).
2. Choose a component tree structure ($$$T$$$ choices).
3. Orient all $$$L-1$$$ edges away from the component containing $$$r$$$.
4. Each directed edge pointing into component $$$C_j$$$ must pick a specific target vertex in $$$C_j$$$ ($$$s_j$$$ choices).
Summing over all choices of the root component:
Way 2: Bottom-Up
1. Choose a global root $$$r$$$ ($$$n$$$ choices).
2. Add $$$L-1$$$ directed edges sequentially to merge components. At step $$$k$$$, we connect any vertex in the graph ($$$n$$$ choices) to the root of a component not in its current tree ($$$L-k$$$ choices).
Multiply across all $$$L-1$$$ steps:
Equating the two:
Since the $$$L-1$$$ edges can be added in $$$(L-1)!$$$ orderings, dividing out the edge-addition sequences yields:
Thus, the problem boils down to efficiently calculating the sizes of all $$$L$$$ disjoint components created when the minimal connected subgraph of $$$S$$$ is removed.
To avoid traversing the whole tree for each query, we can construct a virtual tree on the subset of vertices S.
Deleting the $$$L-1$$$ edges of the minimal subgraph leaves behind $$$L$$$ components:
1. Vertices along the compressed edges between Virtual Tree nodes.
2. The remaining original subtrees attached to each Virtual Tree node.
Component Size of an Intermediate Node
Consider a node $$$v$$$ lying strictly inside the path between a Virtual Tree node and its parent. If we cut the edge above $$$v$$$ and below $$$v$$$, its component size is the subtree size of its parent minus its own subtree size:
Multiplying Along Paths via Binary Lifting
We maintain $$$cld[u][j]$$$ as the product of component sizes for $$$2^j$$$ nodes along the path starting from $$$u$$$ going upward.
- Base Case: $$$cld[u][0] = sz[\text{up}[u][0]] - sz[u] \pmod{998244353}$$$
- Transition: $$$cld[u][j] = (cld[u][j-1] \cdot cld[\text{up}[u][j-1]][j-1]) \pmod{998244353}$$$
For a Virtual Tree edge between parent $$$u$$$ and child $$$c$$$, the number of intermediate edges to cut is $$$d = \text{depth}[c] - \text{depth}[u] - 1$$$.
We jump up $$$c$$$ by $$$d$$$ steps in $$$O(\log n)$$$ using binary lifting.
E. no-free-ride
Idea and prepared by: NorLuiSort the edges by weight, heaviest first. For a fixed cycle, which edge gives the "max outside" term? Try to describe it only by how many of the heaviest edges the cycle contains.
Suppose the cycle has to contain the $$$t$$$ heaviest edges. Out of all such paths, which one is the best?
When do the $$$t$$$ heaviest edges all fit on one simple path? If they stop fitting for some $$$t$$$, can they fit again for a bigger $$$t$$$?
Let the weights in decreasing order be $$$w_1 \gt w_2 \gt \dots \gt w_{n-1}$$$, and let $$$e_i$$$ be the edge with weight $$$w_i$$$. For convenience, let $$$w_n = 0$$$.
Take any valid path $$$P$$$ and let $$$t$$$ be the largest number such that $$$e_1, e_2, \dots, e_t$$$ all lie on $$$P$$$. Then $$$e_{t+1}$$$ is outside and every heavier edge is inside, so the maximum outside is exactly $$$w_{t+1}$$$:
Now fix $$$t$$$. We need a path containing $$$e_1, \dots, e_t$$$ with the largest possible minimum. Adding edges to a path can only lower its minimum, so the best choice is the shortest path containing all of $$$e_1, \dots, e_t$$$. That is just the smallest subtree containing these edges, and it has to be a path.
What about the requirement that $$$e_{t+1}$$$ stays outside? We can simply ignore it. If our path also contains $$$e_{t+1}$$$, its real value is only larger than $$$\min(P) - w_{t+1}$$$, and it gets counted properly for a bigger $$$t$$$. So we never overestimate, and the optimum is reached at its own $$$t$$$.
So the answer is the maximum over $$$t$$$ of (minimum on the shortest path covering the top $$$t$$$ edges) $$$- \, w_{t+1}$$$. The only remaining detail is the "at least two edges" rule, which matters for small $$$t$$$:
- $$$t = 0$$$: the cycle doesn't need $$$e_1$$$. Any path with at least two edges contains a 2-edge subpath whose minimum is not smaller, so only 2-edge paths matter. At each vertex the best one uses its two heaviest edges, giving (second heaviest edge at the vertex) $$$- \, w_1$$$.
- $$$t = 1$$$: the path is $$$e_1$$$ plus one edge touching it. Take the heaviest edge adjacent to $$$e_1$$$; the value is its weight $$$- \, w_2$$$.
- $$$t \ge 2$$$: the shortest path covering the top $$$t$$$ edges already has at least two edges, so it is a valid choice.
Which $$$t$$$ are possible?
Any two edges of a tree lie on one simple path, so $$$t = 2$$$ always works. If the top $$$t$$$ edges don't fit on one path, the subtree for $$$t+1$$$ only gets bigger, so they won't fit then either. Hence the good values form a prefix $$$2, 3, \dots, p$$$, and we can binary search for $$$p$$$.
To check a fixed $$$k$$$: root the tree, mark both endpoints of each of the top $$$k$$$ edges, and count marked vertices in every subtree. The edge from $$$x$$$ to its parent belongs to the smallest subtree covering the marked vertices exactly when the subtree of $$$x$$$ contains some, but not all, of them. That subtree is a path iff every vertex has degree at most $$$2$$$ in it. Each check is $$$O(n)$$$.
Computing the minimums.
For every $$$t \le p$$$, the shortest path covering the top $$$t$$$ edges lies inside the path for $$$p$$$. So we build the path for $$$p$$$ once, walk along it and write down the position of each edge. The path for $$$t$$$ is the segment between the leftmost and rightmost positions among $$$e_1, \dots, e_t$$$. As $$$t$$$ grows this segment only extends, so we keep its two ends and the current minimum and move the ends one step at a time, which is $$$O(n)$$$ in total.
Overall complexity: $$$O(n \log n)$$$.
Instead of binary searching, we can add the edges one by one, heaviest first, and keep the two endpoints $$$u, v$$$ of the current path, a lot like maintaining a diameter.
When edge $$$(x, y)$$$ is added, the new path, if it exists, must go between the farthest pair among $$$u, v, x, y$$$. So take that pair $$$a, b$$$ and check that every one of the four points $$$c$$$ lies on the path between them, i.e. $$$dist(a, c) + dist(c, b) = dist(a, b)$$$. If the check fails, we stop, since no bigger $$$t$$$ can work.
Distances come from LCA, and the minimum edge on the path $$$u - v$$$ comes from binary lifting with the minimum weight stored on every jump. The cases $$$t = 0$$$ and $$$t = 1$$$ are handled exactly as above. This is also $$$O(n \log n)$$$.
F. Cyclic Interference
Idea and prepared by: iZenithInstead of looking at the sum over all slots $$$i$$$ at once, expand the total instability formula. What happens if you expand $$$(R_{t,i})^2$$$? The square of a sum turns the problem into finding the contribution of ordered pairs of rings.
For a specific pair of rings $$$j$$$ and $$$k$$$, the distance between their visible slots at time $$$t$$$ depends strictly on their relative velocity difference: $$$\delta = (V_j - V_k) \bmod n$$$. At time $$$t$$$, their values are shifted by exactly $$$(\delta \cdot t) \bmod n$$$ slots relative to each other.
Consider what happens when we sum over all time steps $$$t \in [1, n-1]$$$. Because $$$n$$$ is strictly a prime number, what set of gaps does a pair of rings with a non-zero velocity difference ($$$\delta \neq 0$$$) visit across the $$$n-1$$$ seconds?
There are two distinct ways to approach this problem.
Approach 1: The Closed-Form Shortcut $$$\mathcal{O}(n + m)$$$
Let's expand the instability formula:
Summing this over all slots $$$i$$$ represents the cyclic cross-correlation of array $$$A$$$ for pairs of rings.
Let $$$C[d]$$$ be the total correlation score when two rings are exactly $$$d$$$ slots apart:
A pair of rings with a velocity difference $$$\delta = (V_j - V_k) \bmod n$$$ will be separated by a gap of $$$(\delta \cdot t) \bmod n$$$ at time $$$t$$$. We want to find their total contribution across all time steps $$$t = 1 \dots n-1$$$. Because $$$n$$$ is prime, we have two cases: 1. $$$\delta = 0$$$ (Equal Velocities): The gap is always $$$0$$$. Across $$$n-1$$$ seconds, this pair contributes $$$(n-1) \times C[0] = (n-1) \sum A_i^2$$$. 2. $$$\delta \neq 0$$$ (Different Velocities): Because $$$n$$$ is prime, multiplying a non-zero $$$\delta$$$ by $$$t = 1, 2, \dots, n-1$$$ forms a bijection. The pair visits every non-zero gap exactly once. Thus, their contribution is exactly $$$\sum_{d=1}^{n-1} C[d]$$$.
We don't need to compute individual $$$C[d]$$$ values. We know that the sum of all possible shifts is just the square of the array sum: $$$\sum_{d=0}^{n-1} C[d] = \left(\sum A_i\right)^2$$$. Therefore, the sum of non-zero shifts is simply $$$\left(\sum A_i\right)^2 - \sum A_i^2$$$.
Let $$$E$$$ be the number of ordered pairs of rings with equal velocities (which is simply $$$\sum \text{cnt}_v^2$$$, where $$$\text{cnt}_v$$$ is the frequency of velocity $$$v$$$). The remaining $$$m^2 - E$$$ pairs have different velocities.
The final answer is:
This can be computed in a single pass in $$$\mathcal{O}(n+m)$$$ time!
Approach 2: Number Theoretic Transform $$$\mathcal{O}(n \log n)$$$
We can also compute the answer formally without the shortcut (which would be required if the problem asked for the cost at each individual second $$$t$$$).
Let $$$D[d]$$$ be the number of pairs of rings with a relative velocity difference of exactly $$$d$$$. Let $$$C[d]$$$ be the total correlation score of array $$$A$$$ for a gap of $$$d$$$. The total cost at any specific time $$$t$$$ is the sum of the contributions of all pairs based on their current gap:
We can break this down into three major steps:
Step 1: Finding Arrays C and D using Auto-correlation Instead of calculating $$$C$$$ and $$$D$$$ in $$$\mathcal{O}(n^2)$$$, we can use NTT. By reversing array $$$A$$$ into $$$A_{\text{rev}}$$$ and multiplying $$$A$$$ by $$$A_{\text{rev}}$$$ as polynomials, the coefficient of $$$x^{n-1+s}$$$ in the result corresponds to the dot product of $$$A$$$ shifted by $$$s$$$. We do the exact same reverse-and-multiply NTT convolution on the velocity frequency array to build $$$D$$$.
Step 2: Handling Zero Differences If $$$d=0$$$, the rings have the same velocity. Their relative gap is always $$$0$$$, regardless of $$$t$$$. This means every time step $$$t$$$ receives a constant "Base" cost of $$$D[0] \cdot C[0]$$$. We can set this aside and add it back at the end.
Step 3: The Primitive Root Mapping For $$$d \gt 0$$$, our cost formula is a multiplicative convolution: we need to sum $$$D[d] \cdot C[(d \cdot t) \bmod n]$$$. However, standard NTT only optimizes additive convolutions (where indices are $$$u + v$$$).
Since $$$n$$$ is strictly prime, it has a primitive root $$$g$$$. This allows us to map every non-zero integer modulo $$$n$$$ to a unique power of $$$g$$$. We can express the relative velocity difference as $$$d = g^u \bmod n$$$, and the time step as $$$t = g^v \bmod n$$$. The multiplication inside the array index now becomes a simple exponent addition:
We create two new arrays of size $$$n-1$$$: * $$$\text{Arr1}[u] = D[g^u \bmod n]$$$ * $$$\text{Arr2}[v] = C[g^v \bmod n]$$$
Now, the summation for a specific time $$$t = g^v$$$ is exactly the additive convolution of $$$\text{Arr1}$$$ and $$$\text{Arr2}$$$. To compute this for all $$$t$$$ simultaneously, we reverse $$$\text{Arr1}$$$ and double $$$\text{Arr2}$$$ (to simulate the circular nature of the exponents modulo $$$n-1$$$), and multiply them using a third and final NTT.
Finally, we map the results back from powers of $$$g$$$ to standard time steps, add our $$$D[0] \cdot C[0]$$$ base cost to each second, and take the sum of all $$$\text{Cost}(t)$$$ to get the final answer.
G. Among US?
Idea and prepared by: lolzxiiIf all $$$k+3$$$ points were correct, interpolating all the $$$k+3$$$ points would define a degree-$$$k$$$ polynomial.
However, because there is one lie among the $$$k+3$$$ points, a polynomial interpolated through all of them behaves like a degree-$$$k+2$$$ polynomial.
Can you think about what happens if you remove the single erroneous point?
In the messy $$$k+2$$$ degree polynomial $$$C_{k+2}$$$ and $$$C_{k+1}$$$ is non-zero due to one error point. If we adjust the error with some $$$\delta$$$, then both of these coefficients must be simultaneously zero for the introduced $$$\delta$$$.
If we have $$$k+3$$$ points and drop any single point $$$j$$$, the remaining $$$k+2$$$ points uniquely define a polynomial of degree $$$k+1$$$.
If we drop a correct point, the fake/erroneous point is still left in the mix, meaning the resulting degree-$$$k+1$$$ polynomial will have a non-zero leading coefficient.
If we drop the actual error index ($$$\text{id}$$$), the remaining $$$k+2$$$ points are completely clean and lie on the original degree-$$$k$$$ polynomial. Therefore, its degree-$$$k+1$$$ coefficient must be strictly $$$0$$$.
Given a set of $$$n$$$ points $$$(x_0, y_0), (x_1, y_1), \dots, (x_{n-1}, y_{n-1})$$$, the unique polynomial passing through them can be written using Lagrange basis polynomials:
where each basis polynomial $$$L_i(x)$$$ is defined as:
Therefore, the leading coefficient $$$C_{n-1}$$$ of the entire polynomial is simply the sum of each $$$y_i$$$ divided by the denominator of its basis polynomial:
In our problem, we query $$$k+3$$$ points at consecutive integers $$$x_i = i$$$ from $$$0$$$ to $$$k+2$$$.
Plugging $$$x_i = i$$$ into the denominator product:
Let's define this precomputed weight as $$$d_i = \frac{(-1)^{k+2-i}}{i!(k+2-i)!}$$$. Thus, our leading coefficient sum (let's call it $$$f$$$) is:
The coefficient of $$$x^{k+1}$$$ is $$$S_1(i)$$$, where $$$S_1(i)$$$ is the sum of all $$$x$$$-coordinates from $$$0$$$ to $$$k+2$$$ except $$$i$$$.
Since the sum of all coordinates from $$$0$$$ to $$$k+2$$$ is $$$\text{sum} = \sum_{j=0}^{k+2} j$$$, the sum of the remaining coordinates is simply:
Therefore, the second top coefficient sum (let's call it $$$s$$$) is:
If all points were correct, both $$$f$$$ and this second top coefficient would be $$$0$$$ (since the true polynomial has degree $$$\le k$$$).
Because there is a single error $$$\Delta$$$ sitting at index $$$id$$$, it scales both coefficients:
$$$f = \Delta \cdot d_{id}$$$:
$$$s = f \cdot (id - \text{sum})$$$
Once we drop the bad index $$$id$$$, we're left with our $$$k+1$$$ clean points. From here, it's just standard Lagrange interpolation to recover the original coefficients. To keep it fast ($$$O(K^2)$$$), we build the product polynomial $$$\prod (x - x_i)$$$ and use synthetic division to strip out the denominators and sum up each point's contribution.
H. Bob and the Infinite Fruit Baskets
Idea and prepared by: pranav_2005The calories from basket $$$i$$$ on day $$$d$$$ is given by a linear equation: $$$y_i(d) = C_i - S_i \cdot d$$$. We want to pick the basket that maximizes this value for each day $$$d$$$, as long as the value remains positive.
Since $$$k \le 10^9$$$, you cannot iterate day by day. However, because each basket's calories decrease linearly at a constant rate, the "best" basket changes at most $$$N$$$ times. The optimal choices across all days form the upper envelope of $$$N$$$ lines.
If you know a certain basket (or line) is optimal on day $$$d$$$, you can use Binary Search to find the last day mid where this basket remains the absolute best choice.
We want to compute $$$\sum_{d=0}^{k-1} \max\left(0, \max_{1 \le i \le N} (C_i - d \cdot S_i)\right)$$$.
Because $$$k$$$ is massive but $$$N$$$ is small ($$$N \le 1000$$$), we can use a jump strategy to process continuous segments of days at once. For the current day $$$i$$$, we find the maximum possible calories we can get, let's call this $$$val$$$, and the rate at which this specific basket degrades, $$$dec$$$.
Instead of evaluating day $$$i+1, i+2, \dots$$$ one by one, we can binary search the furthest day $$$mid$$$ ($$$i \le mid \lt k$$$) such that our current basket remains the absolute optimal choice. For a fixed day $$$x$$$, we can check if our chosen line still yields the maximum value among all $$$N$$$ baskets.
Since the degradation is linear, the sum of calories gained from this basket between day $$$i$$$ and day $$$mid$$$ is exactly the sum of an Arithmetic Progression (A.P.):
We add this sum to our total answer and jump our current day $$$i$$$ directly to $$$mid$$$. We terminate early if the maximum available calories on the current day drops to $$$\le 0$$$ or if we reach $$$k$$$ days.
Time Complexity: $$$\mathcal{O}(N^2 \times \log(k))$$$ per testcase, which comfortably passes within the time limit.
I. Funny Game
Idea and prepared by: pranav_2005Notice that selecting a submask $$$x \gt 0$$$ such that $$$a_i$$$ & $$$x = x$$$ means picking a non-empty subset of the ON bits in $$$a_i$$$. Each set bit acts entirely independently. This structure strongly resembles the classic game of Nim, where each set bit is equivalent to a single stone in pile $$$i$$$.
Because the goal is to maximize the final score, the game is decided by the Most Significant Bit (MSB) that has an odd total count across all elements. If a player secures an odd number of this MSB in their score, they guarantee a win, because this bit's value is strictly greater than the sum of all lower bits combined.
Let $$$j$$$ be the highest bit with an odd count cnt. If $$$cnt \equiv 1 \pmod 4$$$, Alice can easily secure it. If $$$cnt \equiv 3 \pmod 4$$$, taking the bit leaves an even amount for the opponent, so neither player wants to touch the $$$j$$$-bits unless forced! How can you determine who gets forced?
First, we analyze each bit position $$$j$$$ from $$$30$$$ down to $$$0$$$. Let $$$cnt$$$ be the number of elements in the array $$$a$$$ that have the $$$j$$$-th bit set.
If $$$cnt$$$ is even for all bits, the game will always end in a DRAW because neither player can gain a strict majority for any bit, resulting in identical final scores.
Find the largest bit $$$j$$$ where $$$cnt$$$ is odd. The player who secures this bit in their final score will win. We have two cases based on $$$cnt$$$:
$$$cnt \equiv 1 \pmod 4$$$: Alice can simply choose an element with the $$$j$$$-th bit set, pick $$$x = 2^j$$$ (taking only this bit), and secure the advantage. Bob is now facing an even number of $$$j$$$-bits. Whatever Bob does with the remaining $$$j$$$-bits, Alice can mirror. Thus, Alice wins.
$$$cnt \equiv 3 \pmod 4$$$: If Alice takes a $$$j$$$-bit, she leaves $$$cnt \equiv 2 \pmod 4$$$, which allows Bob to mirror her and eventually secure the $$$j$$$-bit advantage. Therefore, neither player wants to touch the $$$j$$$-bits. They will instead stall by playing a standard game of Nim on all the other bits. The "pile size" for each element is simply its
popcount(number of set bits), excluding the $$$j$$$-th bit.
We compute the Nim-sum (XOR sum) of these remaining popcounts: $$$xo = \bigoplus_{i=1}^{n} \left( \text{popcount}(a_i) - [j\text{-th bit is set in } a_i] \right)$$$
- If $$$xo = 0$$$, it is a losing position in Nim. Bob can mirror Alice's stalling moves, eventually forcing Alice to take a $$$j$$$-bit. Bob wins.
- If $$$xo \neq 0$$$, Alice can play the winning Nim strategy, forcing Bob to exhaust his stalling moves and take the $$$j$$$-bit first. Alice wins.
Time Complexity: $$$\mathcal{O}(N \cdot \log(\max A))$$$ per testcase.
J. One More Bounce
Idea and prepared by: iZenithTry writing down the exact height after the first few bounces in terms of $$$h$$$. The fraction decreases by $$$\frac{2}{i+2}$$$, meaning the remaining height is multiplied by $$$\left(1 - \frac{2}{i+2}\right) = \frac{i}{i+2}$$$. Do you notice a telescoping pattern?
The height after the $$$i$$$-th bounce mathematically simplifies to $$$h \cdot \frac{2}{(i+1)(i+2)}$$$. We need this value to be $$$\ge k$$$. Since $$$h$$$ can be up to $$$10^{18}$$$, a linear loop will result in Time Limit Exceeded. How can you efficiently find the largest $$$i$$$?
Let $$$H_i$$$ be the maximum height after the $$$i$$$-th bounce. We are given $$$H_0 = h$$$. The problem states that after the $$$i$$$-th bounce, the height decreases by $$$\frac{2}{i+2}$$$ of the previous height. This means the new height is:
If we expand this out from the beginning, we get a massive telescoping product:
Notice how almost every term in the numerator cancels out with a term in the denominator. The only surviving terms are $$$1 \cdot 2$$$ in the numerator, and $$$(i+1)(i+2)$$$ in the denominator. This beautifully simplifies to:
We want to find the maximum number of bounces $$$i$$$ such that $$$H_i \ge k$$$:
Since $$$h \le 10^{18}$$$, the value of $$$\frac{2h}{k}$$$ can be up to $$$2 \cdot 10^{18}$$$. The maximum possible value for $$$i$$$ is roughly $$$\sqrt{2 \cdot 10^{18}} \approx 1.4 \times 10^9$$$. A linear search (checking $$$i = 1, 2, 3 \dots$$$) will give a Time Limit Exceeded error. However, since the function $$$(i+1)(i+2)$$$ is strictly increasing, we can use Binary Search to find the maximum $$$i$$$.
We set our search space to $$$low = 0$$$ and $$$high = 2 \cdot 10^9$$$. For each $$$mid$$$, we check if $$$(mid+1)(mid+2) \le \frac{2h}{k}$$$. If it is, we record $$$ans = mid$$$ and search higher. Otherwise, we search lower.
Time Complexity: $$$\mathcal{O}(\log(\sqrt{h}))$$$ per testcase, which comfortably passes within the time limit.
K. Find me
Idea and prepared by: mnshgCan you trace the robot's moves backward from a given cell $$$(x, y)$$$ back to $$$(1,1)$$$?
Notice that if $$$x \gt y$$$, the last move must have been a right move ($$$x \leftarrow x - y$$$), and if $$$y \gt x$$$, the last move must have been an up move ($$$y \leftarrow y - x$$$).
Since simulating one step at a time is too slow for coordinates up to $$$10^{18}$$$, how can you compress consecutive identical moves (e.g., $$$x / y$$$ consecutive right moves) using modulo arithmetic, similar to the Euclidean algorithm?
After tracing the compressed paths for both target cells back to $$$(1,1)$$$ and reversing them, how can you find the last common cell by simulating forward from $$$(1,1)$$$ while both paths match?
To find the last common cell visited by the two paths from $$$(1,1)$$$ to $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, we can trace both paths backward to the origin. From any cell $$$(x, y)$$$, we can determine the previous move by comparing $$$x$$$ and $$$y$$$. If $$$x \gt y$$$, the robot must have performed $$$x / y$$$ consecutive right moves, meaning we can jump back using $$$x \bmod y$$$ while recording the direction and number of steps. Conversely, if $$$y \gt x$$$, the robot performed $$$y / x$$$ consecutive up moves, allowing us to update $$$y \bmod x$$$. This process mirrors the Euclidean algorithm, guaranteeing that the path length and trace time are bounded efficiently by $$$\mathcal{O}(\log(\max(x, y)))$$$.
After generating the compressed paths for both target cells, we reverse them so they begin from $$$(1,1)$$$. We then simulate forward from the origin simultaneously, comparing the direction and number of steps in both compressed paths. As long as both paths take the same direction, we advance our current position by $$$\min(\text{steps}_1, \text{steps}_2)$$$. If the directions eventually differ or the step counts diverge, the paths split, and our current position becomes the last common cell.
L. Conveyor Smoothing: Toll Road
Idea and prepared by: NorLuiThis problem is built on slope trick: storing a convex piecewise linear function by the points where its slope changes. If you haven't used it before, read one or two of these first:
- [Tutorial] Slope Trick by zscoder, the original tutorial (it also solves APIO 2016 Fireworks)
- Slope trick blog by Kuroni
- [Tutorial] Intuition on Slope Trick by maomao90, which focuses on how to come up with these solutions
- USACO Guide: Slope Trick, with a curated problem list
Good warm-up problems: 713C - Sonya and Problem Wihtout a Legend and 865D - Buy Low Sell High.
Forget about efficiency for a moment. Let $$$f_i(x)$$$ be the minimum cost for the first $$$i$$$ points if $$$b_i = x$$$. Write down how $$$f_{i+1}$$$ is computed from $$$f_i$$$.
Draw $$$f_i(x)$$$ for a few small cases. What shape is it? Try to prove it always keeps that shape.
The transition allows any change $$$b_{i+1} - b_i \in [-V, U]$$$, with a cost that depends on the sign. Can you replace it by two simpler steps, one that only goes down and one that only goes up?
Look at the "only down" step: $$$g(y) = \min_{0 \le s \le V} \big( f(y + s) + D \cdot s \big)$$$. Paying $$$D$$$ per unit of descent is worth it only when $$$f$$$ is falling faster than $$$D$$$ per unit. Where does that happen, in terms of the breakpoints of $$$f$$$?
The DP
Let $$$f_i(x)$$$ be the minimum cost for the first $$$i$$$ points with $$$b_i = x$$$. Then $$$f_1(x) = |a_1 - x|$$$ and
The answer is $$$\min_x f_n(x)$$$. Heights can be huge, so we can't store $$$f_i$$$ as an array. Instead we look at its shape.
Every $$$f_i$$$ turns out to be convex and piecewise linear, with integer slopes and integer breakpoints (proof below). That's exactly what slope trick handles.
Representation
We keep two multisets of breakpoints and the minimum value:
- $$$L$$$: breakpoints left of the minimum. Sorted as $$$l_1 \ge l_2 \ge \dots$$$, the slope of $$$f$$$ between $$$l_{j+1}$$$ and $$$l_j$$$ is $$$-j$$$.
- $$$R$$$: breakpoints right of the minimum. Sorted as $$$r_1 \le r_2 \le \dots$$$, the slope between $$$r_j$$$ and $$$r_{j+1}$$$ is $$$+j$$$.
- $$$ans = \min f$$$, which is reached on $$$[l_1, r_1]$$$.
A point that appears $$$k$$$ times means the slope changes by $$$k$$$ there.
Operation 1: adding $$$|x - a|$$$
This is the classic step from the prerequisite blogs:
- If $$$a \lt l_1$$$: the minimum grows by $$$l_1 - a$$$. Move $$$l_1$$$ from $$$L$$$ to $$$R$$$ and insert $$$a$$$ into $$$L$$$ twice.
- If $$$a \gt r_1$$$: symmetric.
- Otherwise insert $$$a$$$ into both $$$L$$$ and $$$R$$$; the minimum doesn't change.
Operation 2: the toll transition
This is the new part, and it's done in three steps.
Step 1: split it. Think of a move from $$$x$$$ to $$$y$$$ as "first go down by $$$s \in [0, V]$$$ paying $$$D \cdot s$$$, then go up by $$$s' \in [0, U]$$$ paying $$$C \cdot s'$$$". Going down and then up again never helps, since you pay both tolls on the overlap. Every allowed move is one of these with $$$s = 0$$$ or $$$s' = 0$$$. So the transition is the same as doing two simpler steps one after another:
Step 2: the Down step. From height $$$y$$$ we may come down from any start $$$x \in [y, y + V]$$$, paying $$$D$$$ per unit. Moving the start one unit to the right changes $$$f$$$ by its slope and the toll by $$$+D$$$. So moving right pays off exactly while $$$f$$$ falls faster than $$$D$$$ per unit, i.e. while its slope is below $$$-D$$$.
Left of $$$l_D$$$ the slope of $$$f$$$ is at most $$$-D$$$, and right of $$$l_D$$$ it's bigger than $$$-D$$$. So the best start is $$$l_D$$$, clipped to the window $$$[y, y + V]$$$:
- $$$y \ge l_D$$$: start at $$$y$$$ itself, so $$$g(y) = f(y)$$$. Nothing changes here.
- $$$l_D - V \le y \le l_D$$$: start at $$$l_D$$$, so $$$g(y) = f(l_D) + D (l_D - y)$$$, a straight line with slope $$$-D$$$.
- $$$y \le l_D - V$$$: start at $$$y + V$$$, so $$$g(y) = f(y + V) + D V$$$. This is $$$f$$$ moved left by $$$V$$$.
In terms of breakpoints: $$$l_1, \dots, l_D$$$ and all of $$$R$$$ stay where they are, and $$$l_{D+1}, l_{D+2}, \dots$$$ all move left by $$$V$$$. If $$$|L| \le D$$$, then $$$f$$$ is never steeper than $$$D$$$, descending never pays off, and nothing moves.
Intuitively, the deep points of $$$L$$$ describe where $$$f$$$ is very steep. Where it's steeper than the toll, we'd rather pay the toll and drive down, which stretches that steep part out by $$$V$$$.
Step 3: the Up step. It's symmetric: $$$r_1, \dots, r_C$$$ and all of $$$L$$$ stay, and $$$r_{C+1}, r_{C+2}, \dots$$$ move right by $$$U$$$.
Down never touches $$$R$$$ and Up never touches $$$L$$$, so the whole transition is just:
Keep the $$$D$$$ largest points of $$$L$$$ and the $$$C$$$ smallest points of $$$R$$$ in place. Move every other point of $$$L$$$ left by $$$V$$$ and every other point of $$$R$$$ right by $$$U$$$.
The minimum value doesn't change either, because $$$h \ge 0$$$ and $$$h(0) = 0$$$. So $$$ans$$$ is untouched.
Data structure
Split each side into two parts:
- $$$L_{in}$$$: the $$$\min(D, |L|)$$$ largest points of $$$L$$$, kept in a
multisetat their real positions. - $$$L_{out}$$$: the rest of $$$L$$$, kept in a max-heap with a lazy offset $$$lo$$$ (we store $$$value - lo$$$).
- $$$R_{in}$$$ / $$$R_{out}$$$: the same with the $$$C$$$ smallest points and an offset $$$ro$$$.
Now the transition is just lo -= V and ro += U. Every point of $$$L_{out}$$$ is at most every point of $$$L_{in}$$$, and it only moves further left, so the split stays valid.
After each insert or erase we rebalance: - If $$$|L_{in}| \gt D$$$, move the smallest point of $$$L_{in}$$$ to $$$L_{out}$$$.
- If $$$|L_{in}| \lt D$$$ and $$$L_{out}$$$ is non-empty, move the top of $$$L_{out}$$$ back into $$$L_{in}$$$.
Each push or pop causes $$$O(1)$$$ such moves. The largest point of $$$L$$$ is the maximum of $$$L_{in}$$$ if it's non-empty, otherwise the top of $$$L_{out}$$$.
Two edge cases are worth mentioning. When $$$D$$$ is huge (up to $$$10^9$$$), $$$L_{out}$$$ is always empty and nothing on the left ever moves. When $$$D = 0$$$, all of $$$L$$$ moves every step, because descending is free and you can always slide down towards the minimum.
Complexity
$$$O(n \log n)$$$. Breakpoints can drift by up to $$$n \cdot \max(U, V) \approx 5 \cdot 10^{14}$$$. The answer is at most $$$\sum a_i$$$, since $$$b_i = 0$$$ for all $$$i$$$ is always valid. So long long is enough.
$$$n = 3$$$, $$$U = V = 5$$$, $$$C = 1$$$, $$$D = 3$$$, $$$a = [2, 8, 1]$$$.
- $$$i = 1$$$: $$$L = \lbrace 2 \rbrace$$$, $$$R = \lbrace 2 \rbrace$$$, $$$ans = 0$$$, i.e. $$$f_1(x) = |x - 2|$$$.
- Transition: $$$|L| = 1 \le D$$$ and $$$|R| = 1 \le C$$$, so nothing moves.
- $$$i = 2$$$, $$$a = 8 \gt r_1 = 2$$$: $$$ans = 6$$$, $$$2$$$ moves from $$$R$$$ to $$$L$$$, and $$$8$$$ goes into $$$R$$$ twice. Now $$$L = \lbrace 2, 2 \rbrace$$$, $$$R = \lbrace 8, 8 \rbrace$$$, so $$$f_2$$$ is flat at $$$6$$$ on $$$[2, 8]$$$. For example, $$$b = [2, 2]$$$ pays $$$6$$$ for changing elevation, and $$$b = [2, 8]$$$ pays $$$6$$$ in climb toll.
- Transition: $$$R$$$ keeps its $$$C = 1$$$ smallest point $$$8$$$, and the other $$$8$$$ moves right by $$$U = 5$$$, so $$$R = \lbrace 8, 13 \rbrace$$$. In words: from $$$b_2 = 8$$$ you can keep going up to $$$13$$$ paying only the toll of $$$1$$$ per unit, so the slope there is $$$1$$$ instead of $$$2$$$. $$$L = \lbrace 2, 2 \rbrace$$$ has at most $$$D = 3$$$ points and stays.
- $$$i = 3$$$, $$$a = 1 \lt l_1 = 2$$$: $$$ans = 6 + 1 = 7$$$. This matches the expected output.
Lemma 1 (splitting). Doing Down and then Up gives
For any such $$$x, z$$$ we have $$$y - x = (y - z) - (x - z) \in [-V, U]$$$, so the move $$$x \to y$$$ is allowed. Its cost is at least $$$h(y - x)$$$: if $$$y \ge x$$$ then $$$y - z \ge y - x$$$, so $$$C(y - z) \ge C(y - x)$$$; if $$$y \lt x$$$ then $$$x - z \ge x - y$$$, so $$$D(x - z) \ge D(x - y)$$$. In the other direction, every allowed move $$$x \to y$$$ is achieved with exactly cost $$$h(y - x)$$$ by taking $$$z = \min(x, y)$$$. So the two steps together are exactly the original transition.
Lemma 2 (Down step). Let $$$f$$$ be convex piecewise linear with breakpoint multisets $$$L, R$$$, and $$$|L| \ge D$$$. Then $$$g(y) = \min_{0 \le s \le V} f(y + s) + D s$$$ has the left breakpoints $$$\lbrace l_1, \dots, l_D \rbrace \cup \lbrace l_{D+1} - V, \; l_{D+2} - V, \dots \rbrace$$$, the same $$$R$$$, and $$$\min g = \min f$$$. If $$$|L| \lt D$$$, then $$$g = f$$$.
Proof. Put $$$x = y + s$$$ and $$$\varphi(x) = f(x) + D x$$$. Then
The slopes of $$$\varphi$$$ are the slopes of $$$f$$$ plus $$$D$$$.
- If $$$|L| \lt D$$$, every slope of $$$f$$$ is greater than $$$-D$$$, so $$$\varphi$$$ is increasing. The best choice is $$$x = y$$$, which gives $$$g = f$$$.
- Otherwise, the slope of $$$f$$$ is $$$\le -D$$$ left of $$$l_D$$$ and $$$\ge -(D - 1)$$$ right of it. So $$$\varphi$$$ is non-increasing up to $$$l_D$$$ and increasing after it, and $$$l_D$$$ minimizes $$$\varphi$$$. Because $$$\varphi$$$ is convex, its minimum over the window $$$[y, y + V]$$$ is at the point of the window closest to $$$l_D$$$. That gives exactly the three cases from the solution.
Reading off the slopes: $$$g$$$ has $$$f$$$'s slopes (all $$$\le -D$$$) shifted left by $$$V$$$, then a segment of slope $$$-D$$$, then $$$f$$$'s slopes right of $$$l_D$$$ (all $$$ \gt -D$$$). The slopes are still non-decreasing, so $$$g$$$ is convex. Its breakpoints are the ones claimed, with the same multiplicities: the change from $$$-D$$$ to $$$-(D-1)$$$ is still at $$$l_D$$$, and each $$$l_j$$$ with $$$j \gt D$$$ sits at $$$l_j - V$$$.
Finally, $$$g(y) = f(x) + D s \ge \min f$$$ for every $$$y$$$. And $$$g = f$$$ on $$$[l_D, \infty)$$$, which contains $$$[l_1, r_1]$$$ where $$$f$$$ reaches its minimum. So $$$\min g = \min f$$$, which finishes the proof of Lemma 2.
The Up step is the same lemma mirrored ($$$x \mapsto -x$$$, swapping $$$L \leftrightarrow R$$$, $$$D \to C$$$, $$$V \to U$$$).
Putting it together. $$$f_1 = |x - a_1|$$$ is convex. Lemmas 1 and 2 show the transition keeps convexity and the minimum, and adding $$$|x - a|$$$ keeps convexity too. So by induction every $$$f_i$$$ is convex and the algorithm keeps its breakpoints exactly.
All breakpoints start at integers and only move by integers, so they stay integers. That means the minimum over the window in Lemma 2 is always attained at an integer, and the piecewise linear $$$f_i$$$ agrees with the DP over integer heights. So the answer is $$$ans$$$ after processing all $$$n$$$ points.
M. K Teams
Idea and prepared by: lolzxiiWhat is the minimum possible number of coders needed to occupy $$$K$$$ tables if every table must have at least $$$2$$$ members?
What is the maximum possible number of coders that can fit into $$$K$$$ tables if each table can hold at most $$$3$$$ members?
If $$$N$$$ falls within this valid range, can you start by giving every table a base size of $$$2$$$ and then distribute the remaining coders?
If we have $$$K$$$ tables, we can accommodate minimum $$$2 \cdot K$$$ people and maximum $$$3 \cdot K$$$ people. If $$$N$$$ falls out of this range, there is no possible way to allocate tables.
If $$$N$$$ falls in this range, we can assign 2 people to each table, and the left over people can team up with the tables having 2 people.
N. Dominance-Free Arrays
Idea and prepared by: lolzxiiHow many total non-negative integer arrays of length $$$N$$$ sum up to $$$S$$$ without any restriction?
How can we count arrays where at least one element is greater than or equal to $$$X = \lfloor S/2 \rfloor + 1$$$?
Instead of directly counting arrays that satisfy the condition, it is much easier to count the total number of solutions to $$$\sum A_i = S$$$ and subtract the invalid solutions (where at least one element strictly exceeds $$$\lfloor \frac{S}{2} \rfloor$$$).
By stars and bars, the number of non-negative integer solutions to $$$\sum_{i=1}^{N} A_i = S$$$ is given by:
Let $$$X = \lfloor \frac{S}{2} \rfloor + 1$$$. An element violates the condition if $$$A_i \ge X$$$.
Notice that it is impossible for two or more elements to be $$$\ge X$$$.
By symmetry, any of the $$$N$$$ positions can be the violating element.
If we fix the $$$i$$$-th element to be $$$\ge X$$$ (say it takes value $$$X + y$$$ where $$$y \ge 0$$$), the remaining $$$N-1$$$ elements must sum to $$$S - (X + y) = (S - X) - y$$$.
Summing over all possible values of $$$y$$$ and all $$$N$$$ positions, the number of ways to choose an invalid array where a specific element is $$$\ge X$$$ is equivalent to choosing distributions for the remaining elements, which simplifies to $$$N \times \binom{N + S - X - 1}{N - 1}$$$.







