|
Titlul: 239 Points Scris de: Cosmin Negruseri din Aprilie 11, 2006, 15:10:46 Aici puteţi discuta despre problema Points (http://infoarena.ro/problema/points).
Titlul: Re: 239 Points Scris de: Gogu Marian din Aprilie 11, 2006, 18:02:12 Cam ce complexitate ati scos aici?
Eu am facut in O(N+2^(D*3)), cu D=numarul de dimensiuni dar cineva mi-a zis ca s-ar putea face in O(N log N) si eu nu-mi dau seama cum. Titlul: Raspuns: 239 Points Scris de: Idolu' Femeilor din Aprilie 13, 2006, 01:31:18 Ce e special la ultimele la 6 teste de tot nu pot sa le trec??? Complexitatea mea e tot O(N + 2 ^ (D * 3)).
Titlul: Raspuns: 239 Points Scris de: u-92 din Aprilie 13, 2006, 10:44:00 poate nu folosesti long long :P
Titlul: Raspuns: 239 Points Scris de: Idolu' Femeilor din Aprilie 13, 2006, 18:00:47 Folosesc! :( Nush ce poate avea
Titlul: Raspuns: 239 Points Scris de: andreit1 din Aprilie 13, 2006, 18:18:31 Pune long long si la numerele pe care le inmultesti( daca faci undeva inmultiri) nu doar la rezultat. Calculele pot sari peste... Si eu tot 70 am luat din cauza asta initial...
Titlul: Raspuns: 239 Points Scris de: Idolu' Femeilor din Aprilie 13, 2006, 18:51:10 ms, de la asta era. pusesem niste long long-uri da nu pusesem peste tot.
Titlul: Raspuns: 239 Points Scris de: Tandrau Alexandru din Mai 06, 2006, 15:52:50 Eu am scos O(n)
Titlul: Raspuns: 239 Points Scris de: Cosmin Negruseri din Mai 07, 2006, 18:19:31 Asa au scos toti ...
Titlul: Raspuns: 239 Points Scris de: Bondane Cosmin din Iunie 23, 2006, 16:53:56 Cum ati facut de ati scos O(n)? ](*,) dak poate cineva sa imi explice plz plz
Titlul: Raspuns: 239 Points Scris de: Filip Cristian Buruiana din Iunie 23, 2006, 17:36:03 Aria unui triunghi de varfuri A(x1, y1), B(x2, y2), C(x3, y3) este:
|(x3-x1) * (y2-y1) - (x2-x1) * (y3-y1)| / 2 . De aici devine evident, pentru ca expresia din modul trebuie sa fie numar par ca aria sa fie numar natural. Si asta se poate face simplu in O(N) daca preprocesezi informatii de genul: M[r1][r2] = numarul de puncte (x,y) din cele N care au x % 2 = r1 si y % 2 = r2, r1, r2 din {0,1}. Si vezi cum trebuie sa aduni ( ai grija si sa nu numeri acelasi triunghi de mai multe ori, pt. ca de exemplu ABC este acelasi lucru cu ACB, BCA, etc )... Spor ;) |