Cycle Croissant Minimum (Corrigé)

Solution

Nous nous soucions uniquement des indices que nous gardons (0 ops) et de ceux que nous corrigeons en une seule fois (1 op). Une opération sur a_i permet a_i\leftarrow(a_i+t)\bmod k avec t\ge m, et puisque nous pouvons ajouter n'importe quel multiple de $k$ en plus, une op peut définir a_i à n'importe quelle valeur dans [0,k-1]. Donc :

• indice gardé : la valeur reste a_i,

• indice changé : la valeur devient n'importe quoi dans [0,k-1].

Contrainte cruciale :

• Si nous gardons un a_i\ge k, alors tout ce qui est à sa droite doit également être gardé et déjà être non décroissant ; sinon, une valeur changée (\le k-1) devrait se trouver après $\ge k$, ce qui peut rompre l'ordre. Donc un indice $i$ avec a_i\ge k est éligible à être gardé uniquement si le suffixe $a[i..n]$ est déjà non décroissant.

• Si a_i<k, il est toujours éligible à être gardé (des voisins changés peuvent être choisis à l'intérieur de [0,k-1] pour s'adapter).

Nous voulons maximiser le nombre d'indices gardés ; le reste est changé. Tout ensemble gardé doit être non décroissant par valeur. Ainsi, nous prenons le LIS (version non décroissante, c'est-à-dire, version $\le$) sur le flux de positions éligibles :

où $\text{suf}[i]$ compte les descentes dans $a[i..n]$. La réponse est :

Pourquoi : les éléments gardés forment une sous-séquence non décroissante (nous ne les modifions jamais), et chaque autre place peut être remplie par des valeurs changées dans [0,k-1] pour maintenir l'ordre. Si un gardé $\ge k$ apparaît, l'éligibilité impose un suffixe non décroissant propre sans entrées changées après lui.

La complexité est \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()