Minimum Segment Cost#13042
Sign in

Minimum Segment Cost (Editorial)

Solution

Let

b_i = a_i - c_i.

Suppose we choose a segment [l,r] of length . Then

r = l + k - 1.

The cost of this segment is

\sum_{i=1}^{n} |b_i - b_l + d_i|.

We split all positions into three cases.

If i < l, then d_i = l-i, therefore

b_i-b_l+d_i = b_i-b_l+l-i = (b_i-i)-(b_l-l).

So the contribution of these positions is

\sum_{i<l}|(b_i-i)-(b_l-l)|.

If l \le i \le r, then d_i=0, so the contribution is

\sum_{l\le i\le r}|b_i-b_l|.

If i>r, then d_i=i-r, therefore

b_i-b_l+d_i = b_i-b_l+i-r = (b_i+i)-(b_l+r).

So the contribution is

\sum_{i>r}|(b_i+i)-(b_l+r)|.

Therefore, the total cost of [l,r] is

\sum_{i<l}|(b_i-i)-(b_l-l)| + \sum_{l\le i\le r}|b_i-b_l| + \sum_{i>r}|(b_i+i)-(b_l+r)|.

The segment must satisfy

2 \le l \le r \le n-1.

Since r=l+k-1, it is enough to iterate over

2 \le l \le n-k.

There are possible segments.

For every segment, we iterate over all positions and directly calculate its cost in time.

Thus, the whole solution works in O(n^2).

Since the answer can be much larger than 2^{31}, we need to use long long.

Correctness

For every valid segment [l,r], we calculate exactly

\sum_{i=1}^{n}|b_i-b_l+d_i|

by separately considering the cases i<l, l\le i\le r, and i>r.

These three cases cover every position exactly once.

We check every valid segment of length , so the minimum value found by the algorithm is exactly the required answer.

Complexity

There are possible segments, and every segment is processed in time.

Therefore, the total complexity is

O(n^2)

time and

memory.