8. Anihilácia vzorové riešenie

4
aabccccbacc
bccccbacc
hahaahh
xzzxyzzyzzyx

ano
nie
nie
ano

Reťazec písmen \(S\) dokážeme celý zmazať práve vtedy, keď platí aspoň jedna z týchto podmienok:

• \(S\) je prázdny reťazec
• \(S\) má dĺžku aspoň 2, začína a končí tým istým písmenom, a keď zmažeme všetky výskyty tohto písmena zo začiatku a z konca, dostaneme reťazec, ktorý sa dá zmazať celý. (Čiže napr. “aaaaaUaaa”, kde \(U\) sa dá zmazať, alebo “bbbbbb”).
• \(S\) sa dá rozseknúť na neprázdne reťazce \(U\) a \(V\), aj \(U\) aj \(V\) sa dajú celé zmazať.
• \(S\) sa dá rozseknúť na 5 častí \(x,U,x,V,x\), kde \(x\) je ľubovoľné písmeno a \(U\) aj \(V\) sú neprázdne reťazce, ktoré sa dajú celé zmazať.

Dôkaz:

Ľahko overíme, že ak reťazec spĺňa niektorú podmienku, dá za zmazať celý. Stačí nám ukázať, že ak sa reťazec dá zmazať, musí spĺňať aspoň jednu podmienku, čo skúsime ukázať sporom. Majme reťazec, ktorý sa dá zmazať celý ale nespĺňa žiadnu zo štyroch podmienok.

Keď by sme tento reťazec mazali, ako posledné nám musel ostať úsek aspoň dvoch rovnakých písmen, označme si toto písmeno \(x\). Pôvodný reťazec má tvar \(T_0x_1T_1x_2...x_kT_k\), kde \(x_i\) je niekoľko znakov \(x\) a \(T_i\) je reťazec, ktorý sa dá celý zmazať (lebo na konci nám ostali len znaky \(x\).).

Ak \(T_0\) resp. \(T_k\) sú neprázdne, tak daný reťazec sa dá rozseknúť na \(T_0\) a zvyšok, resp. \(T_k\) a zvyšok a teda reťazec spĺňa tretiu podmienku (spor). Ďalej teda predpokladajme, že \(T_0\) aj \(T_k\) sú prázdne.

Ak k je 1, máme reťazec tvaru \(x_1\), ktorý spĺňa druhú podmienku (spor).

Ak k je 2, máme reťazec tvaru \(x_1T_1x_2T_2x_3\). Ak ktorýkoľvek z \(x_1\), \(x_2\), \(x_3\) má aspoň dva znaky, tak reťazec spĺňa tretiu podmienku, inak spĺňa štvrtú (spor).

Ak k je viac ako 2, reťazec spĺňa tretiu podmienku (spor).

\(\square\)

Ľahko napíšeme rekurzívnu funkciu, ktorá overí všetky tieto podmienky v čase \(O(n)\), kde \(n\) je dĺžka reťazca, plus čas strávený v rekurzívnych volaniach. Pridáme memoizáciu, aby sme pre každý podúsek vstupného reťazca počítali odpoveď (či sa dá celý zmazať) len raz. Takto dosiahneme časovú zložitosť \(O(n^3)\).

Pamäťová zložitosť je \(O(n^2)\).

import sys
sys.setrecursionlimit(1000000)

# memoizacia
def sol(S, a, b):
    if memo[a][b] == -1: memo[a][b] = _sol(S,a,b)
    return memo[a][b]

# da sa odstranit S[a:b]?
def _sol(S, a, b):
    # prazdny retazec je dobry
    if b-a == 0:
        return True

    # a..aUa..a je dobre, ak U je dobre
    if b-a > 1 and S[a] == S[b-1]:
        aa, bb = a, b
        while aa < b and S[aa] == S[a]:
            aa += 1
        while bb > aa and S[bb-1] == S[b-1]:
            bb -= 1
        if sol(S, aa, bb):
            return True

    for i in range(a+1, b-1):
        # UV je dobre, ak U aj V su dobre
        if sol(S, a, i) and sol(S, i, b):
            return True
    
        # aUaVa je dobre, ak U aj V su dobre
        if S[a] == S[i] and S[i] == S[b-1] and sol(S, a+1, i) and sol(S, i+1, b-1):
            return True

    return False

t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    memo = [[-1 for i in range(n+1)] for j in range(n+1)]
    print(('nie', 'ano')[sol(s,0,n)])