h1(#marmote). 'Marmote':problema/marmote
Se observa ca o vizuina are forma unui romb cu centrul in punctul $X{~i~}$, $Y{~i~}$. O prima solutie de complexitate $O(N*M + K*L^2^)$ este urmatoarea: vom mentine o matrice $Fol[i][j]$ in care vom marca pozitiile care apartin vreunei vizuine. In momentul in care soseste o noua marmota vom verifica in $O(L^2^)$ daca toate pozitiile vizuinei sale nu sunt folosite de alta marmota, iar in caz afirmativ vom marca pozitiile noii vizuini in matrice.

Observatia necesara pentru a reduce complexitatea este ca daca avem doua vizuini care se intersecteaza, atunci pentru fiecare din cele doua vizuini cel putin unul din cele patru varfuri este o pozitie comuna. Astfel, putem sa verificam in $O(1)$ daca o anumita marmote poate sa isi construiasca vizuina uitandu-ne doar la cele patru varfuri. Pentru a obtine o solutie corecta trebuie sa avem grija la vizuinele care se afla pe marginile campului. Va trebui sa extindem matricea $Fol$ astfel incat sa cuprinda in totalitate viuzinile. Comeplexitatea acestei solutii este $O(N*M + K)$.

Observatia necesara pentru a reduce complexitatea este ca daca avem doua vizuini care se intersecteaza, atunci pentru fiecare din cele doua vizuini cel putin unul din cele patru varfuri este o pozitie comuna. Astfel, putem sa verificam in $O(1)$ daca o anumita marmota poate sa isi construiasca vizuina uitandu-ne doar la cele patru varfuri. Pentru a obtine o solutie corecta trebuie sa avem grija la vizuinele care se afla pe marginile campului. Va trebui sa extindem matricea $Fol$ astfel incat sa cuprinda in totalitate vizuinile. Complexitatea acestei solutii este $O(N*M + K)$.