O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste $100$, pt $N=13$) si, pentru fiecare astfel de partitie (care are, sa presupunem $K$ elemente), calcularea urmatoarelor valori: $ok[i][j][S] = 1$ sau $0$ , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii $S$ ( $S$ e un numar pe $K$ biti), folosind nodurile din subarborele lui $i$ si ramanand $j$ noduri, inclusiv nodul $i$, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui $i$); o valoare $j=0$ indica ca au fost folosite toate nodurile din subarborele lui $i$, inclusiv $i$, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul $ok[fiu][j'][S']$, cu $j' < j$ si $S'$ inclus in $S$). Daca $ok[ 1 ][ 0 ][2^K^-1]$ are valoarea $1$, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

h2. 'CT':problema/ct

h2(#nr1). 'CT':problema/ct

Se fixeaza radacina arborelui intr-un nod (sa zicem nodul $1$). Pentru fiecare din cele $K$ perechi de orase se calculeaza $LCA$-ul (lowest common ancestor = cel mai apropiat stramos comun). Se poate folosi orice metoda eficienta de determinarea a $LCA$-ului: de exemplu, pentru fiecare nod $i$ se pot memora $O(logN)$ valori, $stramos[i][j]$, reprezentand stramosul aflat cu $2^j^$ nivele mai sus in arbore (cu $j$ incepand de la $0$), iar cu aceste valori, $LCA$-ul a oricare $2$ noduri se poate determina in timp $O(logN)$. Se sorteaza apoi $LCA$-urile tuturor perechilor, in functie de nivelul din arbore ({$LCA$}-urile de pe un nivel mai jos aflandu-se inaintea celor de pe un nivel mai ridicat). In continuare, vom parcurge $LCA$-urile in ordinea sortata. Pentru a rezolva problema, avem acum $2$ posibilitati:

Uitandu-ne pe valorile obtinute pentru fiecare $i$ de la $1$ la $N$, observam o regula care reduce complexitatea rezolvarii problemei la $O(1)$. Pentru $K$ par, daca $N mod (K + 2) = 1$, castigatorul jocului va fi Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator). Pentru $K$ impar, daca $N mod (2 * K + 2) = 1$, atunci castigatorul este Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator).

h2(#nr1). '1expr':problema/1expr

h2. '1expr':problema/1expr

Problema se rezolva folosind programare dinamica. Pentru fiecare $K$ de la 1 la $3^8^$ se calculeaza lungimea minima a unei $1-expresii$ care are ca rezultat pe $K$, iar ultima operatie efectuata in cadrul acestei $1-expresii$ este $+$, $*$, $^$ sau $!$ (deci se calculeaza $4$ valori). Este important sa se calculeze toate aceste $4$ valori si nu doar o singura lungime minima a unei $1-expresii$ care il are ca rezultat pe $K$, deoarece este posibil ca acea $1-expresie$ sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca pusa intre paranteze.