h1. Soluţii ONIS 2016, Runda 1

(toc)*{text-align:center} *Lista de probleme*
* 'A. Consecutive':onis-2016/solutii-runda-2#Consecutive
* 'B. Carte2':onis-2016/solutii-runda-2#Carte2
* 'C. Tribut':onis-2016/solutii-runda-2#Tribut
* 'D. Revolta':onis-2016/solutii-runda-2#Revolta
* 'E. Metrou4':onis-2016/solutii-runda-2#Metrou4
* 'F. Robo':onis-2016/solutii-runda-2#Robo
* 'G. Twoton':onis-2016/solutii-runda-2#Twoton
* 'H. Sate2':onis-2016/solutii-runda-2#Sate2
* 'I. Politie':onis-2016/solutii-runda-2#Politie
* 'J. Pq':onis-2016/solutii-runda-2#Pq
* 'K. Padure2':onis-2016/solutii-runda-2#Padure2
 

h1(#Consecutive). 'A. Consecutive':problema/consecutive
Vom privi din alt unghi ce inseamna ca un numar sa fie suma de mai multe numere naturale consecutive.

Complexitate timp: $O(N^5)$ (supraestimata).
Complexitate spatiu: $O(N^2)$.

h1(#Revolta). 'D. Revolta':problema/revolta
 
h1(#Metrou4). 'E. Metrou4':problema/metrou4
 
h1(#Robo). 'F. Robo':problema/robo
 

h1(#Twoton). 'G. Twoton':problema/twoton
Obesrvam ca functia adecvat denumita $wtf()$, odata apelata de la pozitia $i$, dupa un anumit numar de pasi se va intoarce la pozitia $i$ si nu va mai ajunge niciodata la $i + 1$. De aici ne vine ideea de a calcula, pentru fiecare pozitie $i, 0 <= i < N$, doua valori: $steps[i] = cati pasi face functia pana se intoarce in valoarea i$ si $ret[i] = ce valoare returneaza wtf(i)$. Evident, $steps[N - 1] = 1$, iar $ret[N - 1] = V[N - 1]$. Parcurgem descrescator pozitiile, iar pentru pozitia $i$, $0 <= i < N - 1$, vom calcula cele doua valori astfel: $steps[i]$ se initializeaza cu $1 + steps[i + 1]$ (functia cheama la inceput $wtf(i + 1)$). Apoi, ne uitam la $ret[i + 1]$. Daca acesta este mai mare sau egal cu $V[i]$, recursivitatea pe acest nivel se sfarseste, setam $ret[i] = V[i]$ si continuam. Altfel, $wtf(i + 1)$ se mai apeleaza odata, deci $steps[i] += steps[i + 1]$, iar $ret[i] = ret[i + 1]$. Raspunsul se va gasi in $steps[0]$.

Complexitate timp: $O(N)$.
Complexitate spatiu: $O(N)$.

h1(#Sate2). 'H.Sate2':problema/sate2
 

h1(#Politie). 'I. Politie':problema/politie
Observam ca politistii vor merge intai pe toate drumurile optime (dupa enunt) dintre nodurile legate direct sau indirect doar de muchii de categorie $1$, dupa aceea doar de muchii de categorie $<= 2$, de categorie $<= 3$, etc. Impartim muchiile dupa categorie. Consideram la fiecare pas $i$, $1 <= i <= D$, ca avem nodurile grupate in componente conexe astfel incat intre orice doua noduri din cadrul aceleasi componente conexe se poate ajunge mergand numai pe muchii de categorie strict mai mica decat $i$. Uitandu-ne la muchiile de categorie $i$, este posibil ca intre unele perechi de componente conexe sa fi "aparut" una sau mai multe muchii. Politistii vor dori sa faca drumuri de la orice componenta la orice alta folosind muchiile noi (atat cat se poate), avand grija sa aleaga de fiecare data un drum cu periculozitate maxima minima. Ne imaginam un graf, privind componentele deja stabilite ca pe noduri, si ca muchii intre ele doar muchiile originale de categorie $i$. Astfel, problema se reduce la a gasi un subset de muchii cu cost maxim minim astfel incat, dupa conectarea nodurilor lor aferente, intre orice doua noduri apartinand aceleeasi componente conexe din graful imaginat sa existe un drum - adica, un "Arbore partial de cost minim":http://www.infoarena.ro/problema/apm. Sortam, deci, muchiile din categoria curenta crescator dupa periculozitate si aplicam algoritmul lui Kruskal, avand grija sa introducem intr-un vector toate periculozitatile muchiilor selectate. Procedeul se repeta pana am epuizat toate muchiile. La final sortam descrescator vectorul pe care l-am mentinut si afisam primele $P$ elemente distincte.

Alternativ, mai simplu, putem pur si simplu sorta muchiile crescator dupa categorie, si in caz de egalitate crescator dupa periculozitate si, la sfarsit, sa aplicam Kruskal. Practic simulam procedeul de deasupra.
Complexitate timp: $O(MlogM + Mlog*N)$.

Complexitate spatiu: $O(N + M)$.
 
h1(#Pq). 'J. Pq':problema/pq
 
h1(#Padure2). 'K. Padure2':problema/padure2

Complexitate spatiu: $O(N + M)$.