Minimum Increasing Cycle (Editorial)

Solution

We only care about which indices we keep (0 ops) and which we fix in one shot (1 op). One operation on a_i allows a_i\leftarrow(a_i+t)\bmod k with t\ge m, and since we can add any multiple of $k$ on top, one op can set a_i to any value in [0,k-1]. So:

• kept index: value stays a_i,

• changed index: value becomes anything in [0,k-1].

Crucial constraint:

• If we keep some a_i\ge k, then everything to its right must also be kept and already be nondecreasing; otherwise a changed value (\le k-1) would have to sit after $\ge k$ which can break order. So an index $i$ with a_i\ge k is keep-eligible only if the suffix $a[i..n]$ is already nondecreasing.

• If a_i<k, it's always keep-eligible (changed neighbors can be chosen inside [0,k-1] to fit).

We want to maximize the count of kept indices; the rest are changed. Any kept set must be nondecreasing by value. Hence we take the LIS (nondecreasing variant, i.e., $\le$-version) over the stream of eligible positions:

where $\text{suf}[i]$ counts descents in $a[i..n]$. The answer is:

Why: kept elements form a nondecreasing subsequence (we never alter them), and every other place can be filled by changed values within [0,k-1] to maintain order. If a kept $\ge k$ appears, eligibility enforces a clean nondecreasing suffix with no changed entries after it.

Complexity is \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()