Inverse Minimum Partition (Easy Version)

Core Cleanup

The annoying part of the original array is that block minimums can be buried anywhere. The first move is to delete all elements that are not strict suffix minimums.

A practical way to build the reduced array is:

• keep an empty vector $v$;
• for each $a_i$, while $v$ is nonempty and $a_i \le v.back()$, pop it;
• push $a_i$.

The final $v$ is strictly increasing.

Why is this allowed? Suppose some earlier endpoint/minimum candidate is at least as large as a later element. Then the earlier one is never a better denominator than the later one, and cuts can be shifted/exchanged so it does not improve any optimal partition. Repeating this removes every dominated element. So $f(a)=f(v)$.

For example, $[3,1,4,1,5]$ reduces to $[1,5]$, whose answer is $2$.

DP After Reduction

Now $v_0 < v_1 < \cdots < v_{m-1}$.

For any block $v_i,\ldots,v_j$, the minimum is $v_i$, so

$$\operatorname{cost}(i,j)=\left\lceil \frac{v_j}{v_i}\right\rceil.$$

Let $dp[i]$ be the minimum cost to partition the suffix $v_i,\ldots,v_{m-1}$. Then

$$dp[i]=\min_{j\ge i}\left(dp[j+1]+\left\lceil\frac{v_j}{v_i}\right\rceil\right),$$

with $dp[m]=0$.

Naively this is $O(m^2)$, which is not invited to the party.

Why Only Costs 1, 2, 3 Matter

Here is the key trick: there is always an optimal partition where every block has cost at most $3$.

Take any block with cost $X\ge4$. We can split it into two blocks with total cost at most $X$.

Choose

$$y=2,\qquad x=\left\lceil\frac X2\right\rceil.$$

Then:

$$x\cdot y \ge X, \qquad x+y\le X, \qquad 1\le x,y<X.$$

Inside the block, cut near the last place where the value is still too small to make the suffix block cost at most $y$. Because $x\cdot y\ge X$, the prefix block gets cost at most $x$, and the suffix block gets cost at most $y$. Total cost is at most $x+y\le X$.

So any block costing $4$ or more can be replaced by smaller-cost blocks without making the answer worse. Keep doing that until all block costs are $1$, $2$, or $3$.

This is the whole problem, basically. Once you see this, the scary 2500 rating loses a lot of its teeth.

Transitions

For a fixed start $i$ and desired block cost $c\in\{1,2,3\}$, the farthest valid end $j$ satisfies

$$\left\lceil\frac{v_j}{v_i}\right\rceil \le c.$$

Since values are integers, this is equivalent to

$$v_j \le c\cdot v_i.$$

If we are paying cost $c$, we should extend the block as far as possible. Ending earlier cannot help, because it leaves more elements for the suffix while paying the same current cost. So the transition is:

$$dp[i] = \min_{c=1}^{3}\left(c + dp[\text{first index } p \text{ with } v_p > c\cdot v_i]\right).$$

Because $v$ is strictly increasing, that index can be found with upper_bound, giving $O(n\log n)$ total time. That is already plenty for $4\cdot10^5$.

Overflow Note

Values go up to $10^{18}$, and we multiply by $3$. That still fits in unsigned 64-bit but not signed long long. Use __int128 for the product. Tiny detail, huge WA if ignored. Classic Codeforces tax.