Think of the case $$$n=3$$$. Can you remove the first or the last number in any way?

We cannot obtain a number larger than $$$\gcd(a_1,a_n)$$$ because the first and last numbers in the array can't be removed. We can remove all other elements by choosing $$$[1, i, n]$$$, so the answer is $$$\gcd(a_1, a_n)$$$.

388911115

Amazing Good Ok Bad Terrible

What is the answer for a fixed $$$x$$$?

Iterating over the values $$$x=1...m$$$, we can find the answer for each possible $$$x$$$.

For any $$$x$$$, the answer is the number of carrots of length greater than or equal to $$$x$$$, plus the number of carrots of length $$$2x$$$.

388911137

Amazing Good Ok Bad Terrible

Consider solving the problem for a fixed $$$x$$$.

Consider solving the problem for $$$k=2$$$.

What happens if $$$k$$$ is bigger than $$$18$$$?

What are the optimal $$$x$$$ values for cutting?

For target value $$$x$$$, it is optimal to use cuts in the following order: $$$x \cdot 2^{k-1}, x \cdot 2^{k-2}, \ldots, x \cdot 1$$$.

For each $$$i$$$, $$$a_i=2^k \cdot x$$$ adds $$$2^k$$$ to the answer. Otherwise, the contribution is $$$\min(\frac{a_i}{x}, 2^k-1)$$$.

The optimal $$$x$$$ is less than or equal to $$$\frac{m}{2^k}$$$ (if less than $$$1$$$, it equals $$$1$$$, and the answer is basically the sum of all carrot lengths). Moreover, no $$$i$$$ can contribute more than $$$2^k$$$ to any $$$x$$$. Using prefix sum, determine the number of values contributing $$$y$$$ to the answer for each possible $$$x$$$. This solution runs in $$$\mathcal{O}(n + m \log m)$$$.

388911156

Amazing Good Ok Bad Terrible

How to find a diameter?

Consider the simplest algorithm.

For each node, first determine whether it is closer to the first vertex than the longest distance seen so far. If not, just skip the node. This uses $$$n-1$$$ queries. Otherwise, while the query returns true, increase the queried distance by one. This can happen up to $$$n-1$$$ times. We can find one end of the diameter by running $$$2n - 2$$$ queries in total. Then repeat the process to find the other end of the diameter. This yields a total of $$$4n-4$$$ queries. But, as previously written, distance can increase at most $$$n-1$$$ times. So this yields a total of $$$3n-3$$$ queries.

388911205

Amazing Good Ok Bad Terrible

What happens when a range includes another?

A range that is included by another range is useless. What happens when we remove all such useless ranges?

We only need to solve the problem for chains of ranges. How?

In this editorial we will use BigIntegers, which are simple vectors, and addition and comparison is $$$\mathcal{O}(n)$$$. It can be proven that if one range includes another, we can remove the other. Also, it can be proven that only start and endpoints of the intervals are important, and let them be $$$pts$$$. Well-known $$$\mathcal{O}(n^3)$$$ dp exists; $$$dp_i$$$ means the maximum score if we fill all of the rows through $$$pts_i$$$; $$$dp_i=\max dp_j + 100^{100^{i-j}}$$$ if there is an interval that covers interval $$$[j, i)$$$. Because there are only $$$2$$$ columns, it can be proven that this solution works in $$$\mathcal{O}(n^2)$$$. From another perspective, you can imagine you have chains.

388911243

Amazing Good Ok Bad Terrible

Can you solve for bigger constraints, such as $$$n,m \le 2 \cdot 10^5$$$? Thanks to dinohaur for the code: 388911329

What kind of integers can exist as an $$$f(l,r)=x$$$ value?

How to check a value $$$x$$$ exists as a $$$f(l,r)$$$?

It can be seen that each value of $$$f$$$ must satisfy $$$f(l,r) \leq \text{smallest prime power bigger than n}$$$; for each $$$x$$$ that satisfies this constraint, we will try to check whether this value can be obtained or not.

A range that satisfies $$$f(l,r)=x$$$ can't contain a multiple of $$$x$$$; otherwise, the set of divisors would have $$$x$$$ in it. When considering multiples of $$$x$$$ as obstacles, we realize that it is optimal to greedily select between two consecutive obstacles. Hence, at each obstacle, we check whether every number $$$y$$$ that satisfies $$$1 \leq y \le x$$$ appears as a factor of any integer between this and the previous obstacle. This solution works in $$$\mathcal{O}(( \sum_{i=1}^n |S_i|) \cdot n$$$. Where $$$S_x$$$ represents the prime powers of $$$x$$$.

To optimize this solution, we iterate over all $$$a_i$$$ and check every factor of $$$a_i$$$, considering the index $$$i$$$ as an obstacle. In order to verify that every element smaller than $$$x$$$ is present between this and the previous obstacle, use a minimum segment tree. This solution works in $$$\mathcal{O}(( \sum_{i=1}^n |S_i|) \log n) \le \mathcal{O}(n \log^2 n)$$$.

388911266

Amazing Good Ok Bad Terrible

Consider $$$\mathcal{O}(n^2)$$$ $$$dp[v][\text{#1's count in subtree of v}]$$$ using the merging subtrees technique. The dp is convex because we are adding only two convex functions, resulting in a convex function. Then, using small to large, you can achieve $$$\mathcal{O}(n \log^2 n)$$$ complexity.

To elaborate:

For $$$\mathcal{O}(n^2)$$$, you can keep dp as pairs for simplicity: $$$(\text{score of v}, \text{minimum score})$$$.

As can be seen in the vector, scores are increasing by $$$2$$$. So you can keep dp with the vector's first element and then with the differences. When you merge two children's subtrees, you are basically doing a Minkowski sum, which is just updating the first element as $$$\text{(lhs[0].first + rhs[0].first, lhs[0].second + rhs[0].second})$$$, and merging the differences.

Then, for each point added to $$$|x|$$$, you must add $$$+2$$$ or $$$-2$$$ ($$$2$$$ due to parity) for all differences split by $$$0$$$ (be careful not to add any difference to $$$[-1, +1]$$$).

You can maintain two sets for each vertex, resulting in $$$\mathcal{O}(n \log^2 n)$$$ complexity from small to large.

388911297

First, identify all nodes in the tree with an initial value of zero, set them to one, and store them in a candidate list. Then, until the list is completely empty, select the most advantageous node at each step. For each node, we trace the path up to the root, counting how many nodes along that path have a subtree sum greater than one ($$$\text{pos}$$$) and how many have a subtree sum less than one ($$$\text{neg}$$$), thereby calculating a score based on the difference $$$\text{pos} - \text{neg}$$$.

After finding the node with the highest score among the list, select it, change its value to minus one, and decrease the subtree sums of all ancestors along the path from the chosen node to the root by two. We repeat this process until all special nodes are processed and the list is empty. And you can fasten this algorithm by HLD.

$$$\mathcal{O}(n^3)$$$ code by anpaio: 388911953 $$$\mathcal{O}(n \log^2 n)$$$ code by anpaio: 388911806

Amazing Good Ok Bad Terrible