infoarena

Aici puteti discuta despre problema Drept (http://infoarena.ro/problema/drept).

Care este complexitatea oficiala ca O(N^3 logN) cam iese din timp :D

O(N^3) optimizat e complexitatea oficiala.

Un hint pt N^3 pls.. :)

Fixezi x₁, x₂ proiectiile pe axa OX ale laturilor paralele cu OY ale dreptunghiului. Pentru ele tii sortate valorile coordonatelor y ale punctelor cu x intre x₁ si x₂. Dreptunghiurile cu k puncte se pot determina printr-o simpla iteratie.
Eu am implementat problema cu arbori echilibrati, complexitate O(N²logN + N³), dar merge prea incet. Optimizarea e cheia problemei.

Asta fac si eu, dar pentru fiecare pereche x₁ si x₂ trebuie facuta acea sortare daca am inteles bine. Dar, de aici rezulta o complexitate de O(N^2 (pt ca iau fiecare pereche) * NlogN(din sortare)) = O(N^3logN)

Ideea e sa o rezolvi fara sa sortezi in O(NlogN). Cand treci de la (x_i, x_j) la (x_i, x_j+1) trebuie sa inserezi intr-un sir sortat valorile coordonatelor y pentru care x=x_j+1. Daca ai si aceste ultime valori sortate, atunci interclasarea lor se face in O(N).

da cu ideea asta am luat si eu 100, si tocmai din acest motiv nu mi-a placut problema. Adica cand vezi N <= 1000 si scoti o solutie N^3 atat de simpla nu prea iti vine sa crezi ca o sa intre in timp, si iti storci creieri sa scoti mai bine, si pana la urma bagi o sursa ca te gandesti ca mai scoti niste puncte si te trezesti cu 100 de puncte.

Mi-a iesit pana la urma  :yahoo: Mersi fain :D