Ciclo Mínimo Creciente (Editorial)

Solución

Solo nos importa qué índices mantenemos (0 ops) y cuáles arreglamos de una vez (1 op). Una operación sobre a_i permite a_i\leftarrow(a_i+t)\bmod k con t\ge m, y dado que podemos agregar cualquier múltiplo de $k$ encima, una op puede establecer a_i a cualquier valor en [0,k-1]. Así que:

• índice mantenido: el valor se mantiene como a_i,

• índice cambiado: el valor se convierte en cualquier cosa en [0,k-1].

Restricción crucial:

• Si mantenemos algún a_i\ge k, entonces todo a su derecha también debe ser mantenido y ya ser no decreciente; de lo contrario, un valor cambiado (\le k-1) tendría que estar después de $\ge k$, lo que puede romper el orden. Así que un índice $i$ con a_i\ge k es elegible para mantener solo si el sufijo $a[i..n]$ ya es no decreciente.

• Si a_i<k, siempre es elegible para mantener (los vecinos cambiados pueden ser elegidos dentro de [0,k-1] para ajustarse).

Queremos maximizar la cantidad de índices mantenidos; el resto son cambiados. Cualquier conjunto mantenido debe ser no decreciente por valor. Por lo tanto, tomamos el LIS (variante no decreciente, es decir, versión $\le$) sobre la secuencia de posiciones elegibles:

donde $\text{suf}[i]$ cuenta los descensos en $a[i..n]$. La respuesta es:

¿Por qué?: los elementos mantenidos forman una subsecuencia no decreciente (nunca los alteramos), y cada otro lugar puede ser llenado por valores cambiados dentro de [0,k-1] para mantener el orden. Si aparece un mantenido $\ge k$, la elegibilidad impone un sufijo no decreciente limpio sin entradas cambiadas después de él.

La complejidad es \mathcal{O}(n \log n)

def solve():
    n,m,k=map(int,input().split())
    a=list(map(int,input().split()))
    suf=[0]*n
    for i in range(n-2,-1,-1):
        suf[i]=suf[i+1]+(a[i]>a[i+1])
    INF=10**18
    dp=[INF]*(n+1)
    dp[0]=-INF
    lis=0
    for i in range(n):
        if a[i]<k or suf[i]==0:
            l,r,b=1,n,0
            while l<=r:
                mid=(l+r)//2
                if dp[mid]<=a[i]:
                    b=mid;l=mid+1
                else:
                    r=mid-1
            if a[i]<dp[b+1]: dp[b+1]=a[i]
            if b+1>lis: lis=b+1
    print(n-lis)

for _ in range(int(input())):
    solve()