Aritmética Difícil#12257

Aritmética Difícil (Editorial)

Autor del Problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

El arreglo objetivo debe ser una PA: $b_{i} = m \cdot i + c$ b_i=m\cdot i+c. Solo podemos aumentar las entradas, por lo que para una pendiente fija $m$ , el desplazamiento más pequeño factible es

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

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

Entonces el costo total (suma de incrementos) es

costo (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{costo}(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

Sea $S = \frac{n ( n + 1 )}{2}$ S=\frac{n(n+1)}{2} y $A = \sum_{i} a_{i}$ A=\sum_i a_i. Definir

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)

Entonces $costo (m) = F (m) - A$ \text{costo}(m)=F(m)-A. Este es el máximo puntual de líneas en $m \Rightarrow$ una función convexa y unimodal en enteros. Por lo tanto, podemos encontrar su mínimo con la búsqueda convexa discreta estándar (comparar $F (M)$ ) frente a $f (M + 1)$ f(M+1)).

Precalcular $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 Entonces

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

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

Complejidad $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