Pagini recente » Monitorul de evaluare | Statistici Cinca David Andrei (cincadavid) | Profil Daria09 | Diferente pentru utilizator/deydey2 intre reviziile 24 si 25 | Diferente pentru onis-2015/solutii-runda-1 intre reviziile 105 si 106
Nu exista diferente intre titluri.
Diferente intre continut:
Complexitate <tex>O(N + M)</tex>
*Demonstratie*: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S-1.
*Demonstratie*: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S+1.
* Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol ≤ S < V.
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu doua elemente. Daca alegem o secventa de monotonie pe care alegem doua elemente, pe restul secventelor este imposibil sa alegem doua si vom alege cel mult 1, atunci sol ≤ S+1 = V
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
