дан массив. Можно за одну операцию удалить элемент...

python
from functools import lru_cache
def minlen(s, single_deletable=False):
    s=tuple(s)
    @lru_cache(None)
    def f(t):
        m=len(t)
        best=m
        for i in range(m):
            neigh=[]
            if i>0: neigh.append(t[i-1])
            if i<m-1: neigh.append(t[i+1])
            if not neigh:
                ok = single_deletable # sum 0 even
            else:
                ok=(sum(neigh)%2==0)
            if ok:
                best=min(best, f(t[:i]+t[i+1:]))
        return best
    return f(s)
for single in [False, True]:
    print("single",single)
    for n in range(1,8):
        vals={}
        for x in range(1<<n):
            s=tuple((x>>i)&1 for i in range(n))
            vals[s]=minlen(s,single)
        print(n, sorted(set(vals.values())), {''.join(map(str,k)):v for k,v in vals.items() if v==max(vals.values())})
    print()

python
from functools import lru_cache
def terminal_lengths(s, single=False):
    s=tuple(s)
    @lru_cache(None)
    def rec(t):
        m=len(t)
        nexts=[]
        for i in range(m):
            neigh=[]
            if i>0: neigh.append(t[i-1])
            if i<m-1: neigh.append(t[i+1])
            ok = (sum(neigh)%2==0) if neigh else single
            if ok: nexts.append(t[:i]+t[i+1:])
        if not nexts:
            return {m}
        out=set()
        for u in nexts: out |= rec(u)
        return out
    return rec(s)
for n in range(1,8):
    non=[]
    for x in range(1<<n):
        s=tuple((x>>i)&1 for i in range(n))
        tl=terminal_lengths(s,False)
        if len(tl)>1:
            non.append((''.join(map(str,s)),tl))
            break
    print(n, non[:1])

python
def genA(b, maxn):
    A={""}
    if maxn>=1: A.add(str(1-b))
    changed=True
    while changed:
        changed=False
        for x in list(A):
            for y in list(A):
                s=x+str(b)+y
                if len(s)<=maxn and s not in A:
                    A.add(s); changed=True
    return A
for b in [0,1]:
    A=genA(b,5)
    print("A",b)
    for n in range(6):
        alln={format(x,f'0{n}b') for x in range(1<<n)}
        miss=sorted(alln-A)
        print(n, len(alln)-len(miss), "miss", miss[:10])

python
for b in [0,1]:
    A=genA(b,4)
    print(b, sorted([s for s in A if len(s)==4]))

python
def genP0(maxn):
    A0=genA(0,maxn)
    P={""}
    if maxn>=1: P.add("1")
    changed=True
    while changed:
        changed=False
        for x in list(P):
            for y in A0:
                s=x+"0"+y
                if len(s)<=maxn and s not in P:
                    P.add(s); changed=True
    return P
P=genP0(5)
for n in range(6):
    alln={format(x,f'0{n}b') for x in range(1<<n)}
    print(n, sorted(alln-P)[:20], "accepted", sorted([s for s in P if len(s)==n])[:20])

python
from collections import deque
INF=10**9
def minlen_fast(bits):
    n=len(bits)
    if n==0: return 0
    b=[None]+list(bits)
    # prefix no 11 for before i
    pref_no11=[True]*(n+1) # pref_no11[k] for [1..k]
    for k in range(1,n+1):
        pref_no11[k]=pref_no11[k-1] and not (k>=2 and b[k-1]==1 and b[k]==1)
    # suffix no 11 for [i..n]
    suff_no11=[True]*(n+2)
    for k in range(n,0,-1):
        suff_no11[k]=suff_no11[k+1] and not (k<n and b[k]==1 and b[k+1]==1)
    dp=[INF]*(n+1)
    # deques for parity candidates (index, dp)
    dq=[deque(), deque()]
    # Need add previous indices before processing j. For j=1 no prev.
    last11=0 # max start <= j-2?
    last00=0
    for j in range(1,n+1):
        if j>1:
            i=j-1
            # add dp[i] to parity deque
            p=b[i]
            while dq[p] and dq[p][-1][1] >= dp[i]:
                dq[p].pop()
            dq[p].append((i,dp[i]))
        # update last bad starts up to j-2 incrementally
        # At j, include pair start j-2?
        if j>=3:
            k=j-2
            if b[k]==1 and b[k+1]==1: last11=k
            if b[k]==0 and b[k+1]==0: last00=k
        # pop outdated for target b[j]
        if b[j]==0:
            L=last11
        else:
            L=last00
        p=b[j]
        while dq[p] and dq[p][0][0] < L:
            dq[p].popleft()
        # source
        if b[j]==0 and pref_no11[j-1]:
            dp[j]=1
        if b[j]==1 and j==1:
            dp[j]=1
        # adjacent any previous j-1
        if j>1:
            dp[j]=min(dp[j], dp[j-1]+1)
        # same parity long edge
        if dq[p]:
            dp[j]=min(dp[j], dq[p][0][1]+1)
    ans=INF
    for i in range(1,n+1):
        if b[i]==0 and suff_no11[i+1]:
            ans=min(ans, dp[i])
        if b[i]==1 and i==n:
            ans=min(ans, dp[i])
    return ans
for n in range(1,10):
    ok=True
    bad=None
    for x in range(1<<n):
        bits=tuple((x>>(n-1-i))&1 for i in range(n)) # normal
        a=minlen(bits,False)
        c=minlen_fast(bits)
        if a!=c:
            ok=False; bad=(bits,a,c); break
    print(n, ok, bad)