Solutia problemei Defrisare

Subtaskul 1

Cum N \le 20 putem să folosim metoda Backtracking pentru a fixa direcţia în care va cădea fiecare copac.

Subtaskul 2

Arborele are forma unui vector.
Putem să ne folosim de programarea dinamică pentru a calcula numarul optim de operaţii necesare pentru fiecare nod X dacă acesta este orientat spre stânga sau spre dreapta.

DP[Nod][0] = numarul minim de operatii necesare pentru ca toti copacii aflati in stanga nodului Nod sa pice dacă acesta cade spre stânga.
DP[Nod][1] = numarul minim de operatii necesare pentru ca toti copacii aflati in stanga nodului Nod sa pice dacă acesta cade spre dreapta.

Iniţial DP[Nod][0] = DP[Nod][1] = min(DP[X][0], \hspace{0.1cm} DP[X][1]) + 1 presupunând ca niciun copac nu are înălţimea mai mare ca L1.
Dacă H[X] > L1 înseamnă că pot să tai copacul X astfel încât să pice pe copacul curent, caz în care updatez DP[Nod][1]:   DP[Nod][1] = min(DP[Nod][1], \hspace{0.1cm} DP[X][1])

Dacă H[Nod] > L1 înseamnă că pot să tai copacul curent astfel încât să pice pe copacul X , caz în care updatez DP[Nod][0]:   DP[Nod][0] = min(DP[Nod][0], \hspace{0.1cm} DP[X][0])

Subtaskul 3

Pentru acest subtask există 3 cazuri:
1. Există două noduri X şi Y legate de radacină prin muchii de lungimi L1, respectiv L2 astfel încât H[x] > L1 şi H[radacina] > L2. Răspunsul este N - 2.

2. Există un nod X legat de radacină printr-o muchie de lungime L1 astfel încât H[radacina] > L1 sau H[X] > L1. Răspunsul este N - 1 .
3. Nu există nicio muchie a cărei lungimi este mai mică decât înălţimea unuia dintre copacii pe care îi leagă. Răspunsul este N.

Subtaskul 4

Pentru a rezolva acest subtask vom folosi o abordare similară cu cea de la subtaskul 2 .
Definim:
DP[Nod][0] = numărul minim de operaţii necesare pentru a rezolva subarborele nodului Nod dacă acesta cade spre unul dintre fii şi nu este doborât de alt fiu.
Nod poate să nu atingă niciun alt copac.

DP[Nod][1] = numărul minim de operaţii necesare pentru a rezolva subarborele nodului Nod dacă acesta cade spre unul dintre fii şi este doborât de alt fiu
DP[Nod][2] = numărul minim de operaţii necesare pentru a rezolva subarborele nodului Nod dacă acesta cade spre radacină.
Nod poate să nu fie atins de niciun alt copac.

BEST[Nod] = min(DP[Nod][0], \hspace{0.1cm} DP[Nod][1], \hspace{0.1cm} DP[Nod][2])

Rădăcina poate să fie orice nod cu grad mai mic sau egal cu 2.

Să presupunem că ne aflăm în nodul Nod cu fii X şi Y de care se leagă prin muchiile de lungime LX respectiv LY .

Iniţializăm DP[Nod][0], \hspace{0.1cm} DP[Nod][1], \hspace{0.1cm} DP[Nod][2] cu 1 + BEST[X] + BEST[Y] caz în care tai copacul curent fără să afecteze/ să fie afectat de subarborii lui X şi Y.

Dacă Nod poate să doboare copacul X atunci updatez DP[Nod][0] : DP[Nod][0] = min(DP[Nod][0], \hspace{0.1cm} DP[X][0] + BEST[Y]) . Analog pentru Y .
Dacă X poate să doboare copacul curent atunci updatez DP[Nod][2] : DP[Nod][2] = min(DP[Nod][2], \hspace{0.1cm} DP[X][2] + BEST[Y]) . Analog pentru Y .
Dacă X poate sa doboare copacul curent şi Nod poate să doboare copacul Y atunci updatez DP[Nod][1] : DP[Nod][1] = min(DP[Nod][1], \hspace{0.1cm} DP[X][2] + DP[Y][0] - 1) . Deoarece unesc două lanţuri numarul de operaţii necesare se micşorează cu 1. Analog pentru cazul Y -> Nod -> X .

Subtaskul 5

Soluţia se bazeaza pe acelaşi DP ca la subtaskul 4.
Pentru fiecare nod o să avem nevoie de o variabilă în care reţinem \sum_{fiu \in Nod} BEST[fiu] .

DP[Nod][0] şi DP[Nod][2] se calculează similar.
Pentru a calcula DP[Nod][1] încercăm să cuplăm nodul curent cu fiecare fiu X pe rând considerând că X este doborât de copacul curent.
Avem însă nevoie să ştim ce fiu e optim să considerăm că doboară copacul Nod .
Să presupunem că exista doi fii X şi Y care pot să cadă spre nodul actual. Considerăm că X este mai bun ca Y dacă DP[X][2] - BEST[X] < DP[Y][2] - BEST[Y] . Astfel avem nevoie doar de primele două cele mai bune noduri care pot fi determinate printr-o singură parcurgere a fiilor nodului actual.