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
