h1. Solutii - Summer Challenge Trei

(Creat de ==user(user="ditzonec" type="tiny")== la data de _2006-08-27_ categoria _Competitii_, autor(i) _Echipa Info-arena_)

(Categoria _Competitii_, autor(i) _Echipa Infoarena_)

h2. ABC

h2. Gold

Solutia triviala este {$O(N^3^)$}: se aleg doua puncte si se verifica suma cantitatilor din ambele parti ale dreptei printr-o parcurgere noua a punctelor. O astfel de solutie obtine $30-40$ de puncte. Pornind de la aceasta idee se poate rafina ajungand la o complexitate de {$O(N^2^logN)$}. Pentru fiecare punct $P$ sortam celelalte $N-1$ puncte dupa unghiul polar ( unghiul format de punctul curent cu axa Ox, daca consideram originea in punctul {$P$}) in {$O(NlogN)$}. Notam cu {$S{~i~}$} suma cantitatilor din primele $i$ mine in ordinea ordonarii dupa unghi. Vom fixa o dreapta de baleiere care sa treaca prin punctul $P$ si prin primul punct in ordinea sortarii. Daca am calculat la un anumit pas toate punctele aflate de o parte a dreptei de baleiere, in momentul in care rotim dreapta de baleiere pana ajunge in dreptul urmatorului punct (in ordinea sortarii) toate aceste puncte raman de aceeasi parte mai putin cel aflat pe dreapta si eventual se vor adauga unele noi. De aceea vom incepe cautarea ultimului punct aflat in sensul $+$ al dreptei
de baleiere de la punctul calculat la pasul anterior( toti indicii vor fi calculati modulo {$N$}). Fiecare punct va fi parcurs de cel mult doua ori, deci complexitatea acestui pas este {$O(N)$}. Astfel vom putea calcula in $O(1)$ sumele de o parte si de alta a dreptei folosindu-ne de vectorul {$S$}.

Solutia triviala este {$O(N^3^)$}: se aleg doua puncte si se verifica suma cantitatilor din ambele parti ale dreptei printr-o parcurgere noua a punctelor. O astfel de solutie obtine $30-40$ de puncte. Pornind de la aceasta idee se poate rafina ajungand la o complexitate de {$O(N^2^logN)$}. Pentru fiecare punct $P$ sortam celelalte $N-1$ puncte dupa unghiul polar ( unghiul format de punctul curent cu axa Ox, daca consideram originea in punctul {$P$}) in {$O(NlogN)$}. Notam cu {$S{~i~}$} suma cantitatilor din primele $i$ mine in ordinea ordonarii dupa unghi. Vom fixa o dreapta de baleiere care sa treaca prin punctul $P$ si prin primul punct in ordinea sortarii. Daca am calculat la un anumit pas toate punctele aflate de o parte a dreptei de baleiere, in momentul in care rotim dreapta de baleiere pana ajunge in dreptul urmatorului punct (in ordinea sortarii) toate aceste puncte raman de aceeasi parte mai putin cel aflat pe dreapta si eventual se vor adauga unele noi. De aceea vom incepe cautarea ultimului punct aflat in sensul $+$ al dreptei de baleiere de la punctul calculat la pasul anterior( toti indicii vor fi calculati modulo {$N$}). Fiecare punct va fi parcurs de cel mult doua ori, deci complexitatea acestui pas este {$O(N)$}. Astfel vom putea calcula in $O(1)$ sumele de o parte si de alta a dreptei folosindu-ne de vectorul {$S$}.