Smoothing a Sequence

Consider checking whether the answer can be at most $D$.

Let the positions whose original values are kept be $i_1<i_2<\cdots<i_m$. If two consecutive kept positions are $i<j$, it is necessary that

$$|A_i-A_j| \le D(j-i).$$

This condition is also sufficient. When the difference of the two endpoint values is at most $D(j-i)$, the changed positions between them can be filled with integers so that every step changes by at most $D$. Changed prefixes and suffixes can always be filled as well.

Therefore, it is enough to determine whether at least $N-K$ original values can be kept.

Subtask 4: $N\le2000$

Let $dp_i$ be the maximum number of original values we can retain when position $i$ is the last retained position. By directly checking which earlier positions $j<i$ can be retained together with $i$, we obtain

$$dp_i=1+\max_{\substack{1\le j<i\\|A_i-A_j|\le D(i-j)}}dp_j.$$

If no $j$ satisfies the condition, take the maximum to be $0$.

Compute the states in the order $i=1,2,\ldots,N$ and check whether $\max_i dp_i\ge N-K$. One feasibility check takes time. Using it in binary search gives time and space.

For each position $i$, define

$$X_i=A_i-Di,\qquad Y_i=A_i+Di.$$

For $i<j$, the condition above is equivalent to

$$X_i\ge X_j,\qquad Y_i\le Y_j.$$

Sort the points $(X_i,Y_i)$ by decreasing $X_i$, breaking ties by increasing . Let be the length of the longest nondecreasing subsequence of the values in this order. Then is exactly the maximum number of original values that can be kept.

For $D>0$, since $Y_i-X_i=2Di$, any two points satisfying the two coordinate inequalities are also ordered by their original indices. For , we have , and a nondecreasing subsequence after decreasing- sorting can contain several points together only when their values are equal, which is also valid.

Thus $D$ is feasible exactly when $L\ge N-K$. The longest nondecreasing subsequence can be computed in $O(N\log N)$ using upper_bound.

Feasibility is monotone in $D$, so binary-search $D$ from $0$ to the maximum adjacent difference of the original sequence. The total time complexity is $O(N\log N\log C)$, where $$, and the memory complexity is .

Solution written by GPT6