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.
 

h2. 'KPerm':problema/kperm
h3. (problema medie, clasele 11-12)