Solutii

Cosmin Negruseri
13 august 2011

In caz ca sunt lurkeri pe blog scriu ideile de rezolvare pentru problemele postului anterior:

1. (Amazon) Se da un sir A de n elemente intregi. Sa se determine doi intregi din sir a, b astfel ca a + b = X. Complexitate O(n).

Parcurgem sirul element cu element si pastram in tabela de dispersie HT elementele deja parcurse. La pasul curent cand ne uitam la elementul A[i] cautam daca in HT exista elementul de valoare S - A[i].

2. (Google, Facebook) Se da un sir A de n elemente intregi. Se cere sa se determine o subsecventa a sirului care are suma elementelor egala cu X. Complexitate O(n).

Din nou parcurgem sirul dar in loc sa adaugam fiecare element, vom adauga Sum[i], suma cumulata a elementelor de la 1 la i Sum[i] = sum(A[1..i]) in structura noastra de date. Acum la fiecare element curent cautam daca exista vreun j astfel ca Sum[j] == Sum[i] - S.

3. (Microsoft, algoritmiada) Se da un arbore T de n noduri ce are costuri intregi pe muchii. Sa se determine un drum ce merge in jos in arbore care are suma costurilor muchiilor egala cu X. Complexitate O(n).

Foarte similar cu ideea din problema anterioara. Cand coboram pe o muchie adaugam in arbore valoarea drumului de la radacina pana la nodul curent, iar cand urcam o stergem.

4. (CLRS) Se da un arbore T de n noduri. Sa se determine un nod pentru care stegerea din graf genereaza componente conexe cu dimensiuni mai mici de n/2 noduri. Complexitate O(n).

Consideram un arbore cu radacina. Pornim de la frunze in sus si pt nod avem un subarbore asociat lui ce merge in jos. Dupa ce stim numarul nodurilor din fiecare subarbore determinat de fii, putem calcula numarul de noduri din subarborele determinat de nodul curent. Avand informatia asta putem calcula care nod are proprietatea din enunt. Acel nod este numit centrul arborelui.

5. Dandu-se un arbore ce are costuri intregi pentru muchii, sa se gaseasca un drum cu numar minim de muchii care are suma costurilor S. Complexitate mai buna de O(n^2).

Aplicam o solutie pe ideea divide et impera. La fiecare pas alegem centrul arborelui curent si cautam daca exista un drum ce trece prin el care sa aiba costul S. Putem face asta usor calculand costul drumurilor de la nod la restul nodurilor si folosind o tabela de dispersie. Apoi aplicam acelasi algoritm recursiv pe toti subarborii care apar dupa stergerea centrului din graf. Solutia asta va avea complexitate O(n log n).

Cam atat, nu erau prea grele nu-i asa?