Solutie problema Iepuri

Solutie problema Iepuri -

Solutia se bazeaza pe metoda programarii dinamice si are complexitatea O(N*K).

Observam ca putem deduce numarul de posibilitati de a imparti un anumit numar j de morcovi la un iepure i si oricati morcovi la iepurii subordonati direct sau indirect daca cunoastem numarul de posibilitati de a imparti j+1, j+2, , j+K morcovi la fiecare fiu al sau si oricati morcovi iepurilor ce apartin subarborilor desemnati de fiecare fiu. Astfel, structura de date folosita pentru implementarea recurentei devine evidenta:

T[i][j] = numarul de posibilitati de a imparti morcovi la iepurii ce apartin subarborelui cu radacina in iepurele i stiind ca iepurele i ia j morcovi

Astfel definita structura de date, luam numarul de posibilitati de a imparti morcovi la iepurii din subarborele desemnat de primul fiu pentru fiecare din cazurile: primul fiu ia j+1, j+2, , j+K morcovi. La sfarsit, adunam toate aceste valori iar rezultatul il inmultim cu valorile pentru al doilea fiu, al treilea fiu etc. calculate in mod similar.

T[i][j] = 1, daca iepurele i corespunde unui nod terminal

T[i][j] = (T[f₁][j+1]+T[f₁][j+2]++T[f₁][j+K]) *

(T[f₂][j+1]+T[f₂][j+2]++T[f₂][j+K]) * * (T[f_p j+1]+T[f_p][j+2]++T[f_p][j+K]),

unde f₁, f₂, f_p sunt numerele de ordine a celor p iepuri fii ai iepurelui i

Rezultatul problemei va fi dat de T[R 1]+T[R][2]++T[R][K] unde R reprezinta numarul de ordine al lui Rila-Iepurila, adica al iepurelui care nu are nici un sef (radacina arborelui) .

Iepuri - solutie alternativa - Stelian Ciurea

1. reprezentam arborele sub forma listelor de adiacenta implementate dinamic; la citire construim si vectorul de predecesori (legaturi de tip tata - aceasta ne permite sa determinam radacina arborelui si deasemenea sa parcurgem arborele in adancime fara sa utilizam un vector pentru nodurile vizitate)

2. determinam radacina

3. facem o parcurgere in adancime a arborelui plecand din radacina: aceasta functie de parcurgere are 2 parametri: nd = nodul curent si i care reprezinta numarul minim de morcovi pe care ii poate manca iepurele din nd.

In aceasta functie, pentru o valoare j a numarului de morcovi, daca notam cu nrp1 numarul de posibilitati pe care le avem in fiul_1 al lui nd cu cel putin j+1 morcovi, cu nrp2 numarul de posibilitati pe care le avem in fiul_2 cu cel putin j+1 morcovi etc, numarul de posibilitati pe care le avem pentru nd este nrp1*nrp2* .

Numarul total de posibilitati la nivelul lui nd se obtine ca o insumare a valorilor pe care le obtinem pentru toate valorile pe care le ia j (de la i la k).

Aceasta solutie obtine 60 de puncte; pentru 40% dintre teste nu se incadreaza in limita de rulare de o secunda.