h3. (problema usoara, clasele 11-12)

Problema este una clasica de cautari ortogonale si se poate face usor o solutie in care se sorteaza dreptunghiurile si punctele dupa x, iar apoi se foloseste o linie de baleiere. Se proceseaza updateuri si querieruri pe un arbore de intervale in o dimensiune. Aceasta solutie are complexitate O(m log n + n log n). S-au obtinut in jur de 70 de puncte folosind asemenea abordari.
Pentru a obtine o solutie mai eficienta trebuia exploatata particularitatea problemei, adica faptul ca toate dreptunghiurile erau egale. Solutia autorului era in doi pasi, intai folosim grila de puncte de coordonate (i * W + 0.5, j * H + 0.5) unde i si j sunt numere intregi. Orice dreptunghi din enunt contine exact un punct din aceasta grila. Vom folosi o structura hash_map ce grupeaza in perechi dreptunghiurile din intrare si punctele din grila interioare lor. Acum pentru a determina daca un punct din cele m este continut in vreun dreptunghi, ne uitam care sunt cele patru puncte din grila vecine acestuia, si vom gasi maxim patru dreptunghiuri asociate acelor 4 puncte din grila. Apoi testam incluziunea punctului nostru in fiecare dintre cele patru dreptunghiuri, astfel putem raspunde la orice test de incluziune in O(1). Complexitatea toatala a algoritmului este O(n + m). Felicitam pe Berzan Constantin care a folosit aceasta abordare si a fost singurul ce a luat punctaj maxim pe aceasta problema.

Problema este una clasica de cautari ortogonale si se poate face usor o solutie in care se sorteaza dreptunghiurile si punctele dupa coordonata $x$, iar apoi se foloseste o linie de baleiere. Se proceseaza updateuri si querieruri pe un arbore de intervale in o dimensiune. Aceasta solutie are complexitate $O(M*lg N + N*lg N)$. S-au obtinut in jur de $70$ de puncte folosind asemenea abordari.
Pentru a obtine o solutie mai eficienta trebuia exploatata particularitatea problemei, adica faptul ca toate dreptunghiurile erau egale. Solutia autorului continea doi pasi:
* Intai folosim grila de puncte de coordonate $(i*W+0.5, j*H+0.5)$ unde $i$ si $j$ sunt numere intregi. Orice dreptunghi din enunt contine exact un punct din aceasta grila. Vom folosi o tabela de dispersie (hash) ce grupeaza in perechi dreptunghiurile din intrare si punctele din grila interioare lor.
* Pentru a determina daca un punct din cele $M$ este continut in vreun dreptunghi, ne uitam care sunt cele patru puncte din grila vecine acestuia, si vom gasi maxim patru dreptunghiuri asociate acelor 4 puncte din grila. Apoi testam incluziunea punctului nostru in fiecare dintre cele patru dreptunghiuri, astfel putem raspunde la orice test de incluziune in $O(1)$.
Complexitatea toatala a algoritmului este $O(N + M)$. Felicitam pe Berzan Constantin care a folosit aceasta abordare si a fost singurul ce a luat punctaj maxim pe aceasta problema.

h2. 'KPerm':problema/kperm