Marmote

Se observa ca o vizuina are forma unui romb cu centrul in punctul Xi, Yi. O prima solutie de complexitate O(N*M + K*L2) 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(L2) 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 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).