Hard Arithmetic#12257

Hard Arithmetic (Çözgüdiň düşündirişi)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Target array must be an AP: $b_{i} = m \cdot i + c$ b_i=m\cdot i+c. We can only increase entries, so for a fixed slope $m$ , the smallest feasible shift is

c = i max (a_{i} - m \cdot i)

c=\max_i\,(a_i-m\cdot i)

Then the total cost (sum of increments) is

cost (m) = i = 1 \sum n (m \cdot i + c - a_{i}) = m \cdot (i = 1 \sum n i) + n \cdot i max (a_{i} - mi) - i = 1 \sum n a_{i}

\text{cost}(m)=\sum_{i=1}^n (m\cdot i+c-a_i)=m\cdot\Big(\sum_{i=1}^n i\Big)+n\cdot\max_i(a_i-m i)-\sum_{i=1}^n a_i

Let $S = \frac{n ( n + 1 )}{2}$ S=\frac{n(n+1)}{2} and $A = \sum_{i} a_{i}$ A=\sum_i a_i. Define

F (m) = i max (n a_{i} + m \cdot (S - n i))

F(m)=\max_i\big(n\,a_i+m\cdot(S-n\,i)\big)

Then $cost (m) = F (m) - A$ \text{cost}(m)=F(m)-A. This is the pointwise maximum of lines in $m \Rightarrow$ a convex, unimodal function on integers. Hence we can find its minimum with the standard discrete convex search (compare $F (M)$ ) vs $f (M + 1)$ f(M+1)).

Precompute $ba_{i} = n \cdot a_{i}$ \texttt{ba}_i=n\cdot a_i, $w_{i} = S - n \cdot i$ \texttt{w}_i=S-n\cdot i Then

F (m) = i max (ba_{i} + m \cdot w_{i}), answer = m min F (m) - A

F(m)=\max_i(\texttt{ba}_i+m\cdot \texttt{w}_i),\qquad \text{answer}=\min_m F(m)-A

Complexity $O (n lo g)$ \mathcal{O}(n\log)

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    S=n*(n+1)//2
    ba=[n*x for x in a]
    w=[S-n*(i+1) for i in range(n)]
    A=sum(a)
    def F(m):
        z=-10**30
        for i in range(n):
            v=ba[i]+m*w[i]
            if v>z:z=v
        return z
    L=-10**9
    R=10**9
    while L<R:
        M=(L+R)//2
        if F(M)<=F(M+1):R=M
        else:L=M+1
    assert(F(L)<=9*10**18)
    print(F(L)-A)

Python