Arithmetic Operations
Contest: Технокубок 2022 - Финал
Difficulty rating: 2300
Tags: brute force, data structures, graphs, math

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$.

You can do the following operation any number of times (possibly zero):

- Choose any index $$$i$$$ and set $$$a_i$$$ to any integer (positive, negative or $$$0$$$).

What is the minimum number of operations needed to turn $$$a$$$ into an arithmetic progression? The array $$$a$$$ is an arithmetic progression if $$$a_{i+1}-a_i=a_i-a_{i-1}$$$ for any $$$2 \leq i \leq n-1$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$).

Output format:
Print a single integer: the minimum number of operations needed to turn $$$a$$$ into an arithmetic progression.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
In the first test, you can get the array $$$a = [11, 10, 9, 8, 7, 6, 5, 4, 3]$$$ by performing $$$6$$$ operations:

- Set $$$a_3$$$ to $$$9$$$: the array becomes $$$[3, 2, 9, 8, 6, 9, 5, 4, 1]$$$;
- Set $$$a_2$$$ to $$$10$$$: the array becomes $$$[3, 10, 9, 8, 6, 9, 5, 4, 1]$$$;
- Set $$$a_6$$$ to $$$6$$$: the array becomes $$$[3, 10, 9, 8, 6, 6, 5, 4, 1]$$$;
- Set $$$a_9$$$ to $$$3$$$: the array becomes $$$[3, 10, 9, 8, 6, 6, 5, 4, 3]$$$;
- Set $$$a_5$$$ to $$$7$$$: the array becomes $$$[3, 10, 9, 8, 7, 6, 5, 4, 3]$$$;
- Set $$$a_1$$$ to $$$11$$$: the array becomes $$$[11, 10, 9, 8, 7, 6, 5, 4, 3]$$$.

$$$a$$$ is an arithmetic progression: in fact, $$$a_{i+1}-a_i=a_i-a_{i-1}=-1$$$ for any $$$2 \leq i \leq n-1$$$.

There is no sequence of less than $$$6$$$ operations that makes $$$a$$$ an arithmetic progression.

In the second test, you can get the array $$$a = [-1, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38]$$$ by performing $$$10$$$ operations.

In the third test, you can get the array $$$a = [100000, 80000, 60000, 40000, 20000, 0, -20000, -40000, -60000, -80000]$$$ by performing $$$7$$$ operations.

Example input:
9
3 2 7 8 6 9 5 4 1

Example output:
6

Example input:
14
19 2 15 8 9 14 17 13 4 14 4 11 15 7

Example output:
10

Editorial:
instead of computing the fewest number of operations, we will compute the largest number of elements that don't have an operation on them, and we will create a piecewise algorithm with final complexity O(n√m) , where m is the upper bound on ai
.
Let d be the common difference between elements in our final sequence. First of all, I will assume that d≥0, since solving the problem for negative d is as simple as reversing the array and running the solution again. If d is fixed beforehand, we can solve the problem in O(n) by putting element i into bucket ai−d⋅i and returning n
minus the size of the biggest bucket.
For d<√m , we can use the above algorithm to handle all of these d in O(n√m) time. We can keep a hashmap from bucket index → number of elements in the bucket, or we can just keep an array since the bucket indices have a range of at most O(n√m)
which is not enough to exceed the memory limit.
For d≥√m , we observe that if we have two indices i,j such that j>i+√m, then at least one of them definitely has to have an operation performed on it, because the difference between them would have to be aj−ai≥√m⋅d>m which is not possible. In other words, if we consider the set of elements which are not edited, that set will have gaps between pairs of elements of size at most √m
.
So, we can build a graph between indices with an edge i→j with label x if i<j≤i+√m and aj−aij−i=x. This graph has at most n√m edges. Then we just have to find the longest path in the graph where all edges have the same label. You can do this with dynamic programming – let dpi,d be the length of the longest path ending at index i, where all edges have label d. For each i, we only need to check edges to j where i−√m<j<i. This means the time complexity is O(n√m). To store the values dpi,d sparsely, we can use either a hash map or a rotating buffer (where we only store dpi,d for i in a sliding window of width √m
).
Complexity: O(n√m)