Revizia anterioară Revizia următoare
Soluţii ONIS 2015, Runda 1
- Lista de probleme
- Por Costel şi Azerah
- Por Costel şi Algoritmul
- Por Costel şi Bujor
- Por Costel şi Comisia de Cenzură
- Por Costel şi Cifrul
- Por Costel şi Invazia Extraterestră
- Por Costel şi Livada
- Por Costel şi Meciul
- Por Costel şi Perechile
- Por Costel şi Pinball
- Por Costel şi Semipalindroamele
Por Costel şi Azerah
Solutia cea mai la indemana la problema aceasta se bazeaza pe metoda programarii dinamice:
Calculam:
dp[i][0] = numarul de submultimi cu suma numerelor para cu primele i numere din sirdp[i][1] = numarul de submultimi cu suma numerelor impara cu primele i numere din sir
Cazul de baza:
dp[0][0] = 1 (submultimea vida)dp[0][1] = 0
Relatia de recurenta:
Daca numarul v[i] este par:dp[i][0] = 2 * dp[i-1][1]dp[i][1] = 2 * dp[i-1][1]
Daca numarul v[i] este impar:dp[i][0] = dp[i-1][0] + dp[i-1][1]dp[i][1] = dp[i-1][0] + dp[i-1][1]
Complexitate: 
Insa, la o inspectie mai amanuntita a dinamicii sau dupa un rationament combinatoric descoperim ca:
- Daca exista numai numere pare in sir, raspunsul este 2n
- Altfel este 2n-1
Acum, daca ignoram citirea sirului, complexitatea este 
Por Costel şi Algoritmul
Stim ca aloritmul va lua cel putin doua iteratii pentru ca se garanteaza ca exista cel putin o muchie care iese din nodul 1. Pentru ca algoritmul lui Por Costel sa se termine in doua iteratii, trebuie ca doar la prima iteratie sa se produca relaxari ale muchiilor (modificari ale vectorului d). Cand se intra in iteratia a doua trebuie ca in vectorul d sa existe deja valorile drumurilor minime pentru a nu se produce nicio modificare, variabila ok sa ramana cu valoarea 1 si sa nu se mai intre in while a treia oara.
Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul x catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din x). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul x (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia este o astfel de ordonare a N-1 muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de @M-N+1 muchii pot fi interclasate cu acestea in orice fel.
Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate O(N*M) chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind 'algoritmul lui Dijkstra': http://www.infoarena.ro/problema/dijkstra
Complexitatea: 
