•bogdan2412
|
|
« : Septembrie 29, 2005, 14:39:46 » |
|
Aici puteţi discuta despre problema Zoo.
|
|
« Ultima modificare: Noiembrie 08, 2007, 22:48:46 de către Mircea Pasoi »
|
Memorat
|
|
|
|
•dobre
|
|
« Răspunde #1 : Octombrie 09, 2005, 12:19:45 » |
|
Care este complexitatea oficiala ?
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #2 : Octombrie 09, 2005, 12:28:23 » |
|
Pai eu am facut un algoritm care imi rezolva fiecare query in O(log^2 N), deci complexitatea finala O(M log^2 N) ( ma rog, se mai adauga si un NlogN de la sortare ) si a luat 100 pct. Daca nu se incadreaza asta in timp, poti rezolva un query si in O(log N), aplicand un rafinament...
Filip b.
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #3 : Martie 26, 2007, 11:12:02 » |
|
Nu stiti de ce mi da Killed by signal 11(SIGSEGV) pe 3 teste ?? am aceeasi complexitate ca si Filip B. si memorie nlogn ?? ... arborele il construiesc recursiv
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
•Florian
|
|
« Răspunde #4 : Aprilie 11, 2007, 16:42:49 » |
|
Nu prea inteleg de ce imi trebuie sortare....iau doar 30 pcts...si pe restul TLE..insa nu stiu la ce ma ajuta sortarea...[totusi sunt constient k trebuie k sa mi se incadreze in timp]..ma poate ajuta cineva?
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #5 : Aprilie 13, 2007, 12:21:26 » |
|
pai iti trebuie un arbore de intervale in primul rand, si tre sa sortezi elementele din acele intervale.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #6 : Aprilie 13, 2007, 12:38:02 » |
|
Ee..ink nu am invatat...DEci sa inteleg k trebuie sa ma multumesc cu 30,nu?..asta e..multumesc de ajutor
|
|
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #7 : August 22, 2007, 18:57:50 » |
|
Si cum se poate face query in logn? In logn*logn mi-am dat si eu seama.
|
|
|
Memorat
|
....staind....
|
|
|
•Marius
|
|
« Răspunde #8 : August 22, 2007, 19:05:11 » |
|
Si cum se poate face query in logn? In logn*logn mi-am dat si eu seama.
Cu rafinamentului lui Willard-Lueker. Il gasesti in documentul Arbori de Intervale al doamnei Lica predat la lotul din 2006.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•peanutz
|
|
« Răspunde #9 : August 22, 2007, 19:24:58 » |
|
Multumesc.
|
|
|
Memorat
|
....staind....
|
|
|
•devilkind
|
|
« Răspunde #10 : August 26, 2007, 22:01:10 » |
|
mie mi-a intrat in timp si fara acel rafinament
|
|
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #11 : Decembrie 06, 2010, 20:08:28 » |
|
Imi poate explica si mie cineva de ce daca pun <= in loc de < la functia cmp din sursa mea de 100 de puncte iau 80? Teoretic interschimba 2 puncte cu acelasi x si nu vad care ar fi problema .
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #12 : Decembrie 06, 2010, 21:01:14 » |
|
Functia ta trebuie sa returneze True in caz ca primul element e mai mic decat celalalt. Daca ai 2 elemente egale si sunt comparate de 2 ori, iti poate da ca a < b si b < a, care o fi stricand vreun assert din sort-ul din STL, ceea ce duce la killed by signal 6.
|
|
|
Memorat
|
|
|
|
•Bit_Master
|
|
« Răspunde #13 : Februarie 16, 2011, 18:59:30 » |
|
Imi poate explica si mie cineva de ce daca pun <= in loc de < la functia cmp din sursa mea de 100 de puncte iau 80? Teoretic interschimba 2 puncte cu acelasi x si nu vad care ar fi problema . Poate le interschimba intre ele de mai multe ori pt ca oricum le-ar pune tot nu e bine. Pana la urma ele raman intr-o pozitie din cauza algoritmului care nu verifica in urma lui (ca altfel cred ca ar fi ciclat la infinit). Oricum, pierzi timp asa. Eu asa cred.
|
|
|
Memorat
|
|
|
|
•repp4radu
|
|
« Răspunde #14 : Ianuarie 11, 2013, 18:07:40 » |
|
Cred ca ar trebui marita limita de timp. Iau 90 de puncte cu TLE avand complexitatea O(M * (log M + log N)). Am incercat, de curiozitate sa trimit o sursa care acum ceva vreme lua 100, intrand lejer in timp si acum ia doar 80. Mersi anticipat! PS Parsez citirea
|
|
|
Memorat
|
|
|
|
•catazep
Strain
Karma: -2
Deconectat
Mesaje: 6
|
|
« Răspunde #15 : Ianuarie 08, 2014, 01:35:10 » |
|
nu va suparati am si eu o intrebare pt cei mai experimentati nu am cum sa ma incadrez in timp cu cv asemanator nu? #include<fstream> using namespace std; struct reper {int x,y; }; reper v[16000]; reper a,b; long unsigned N,M,i,j; unsigned t; int main() { ifstream f("zoo.in"); ofstream g("zoo.out"); f>>N; for(i=1;i<=N;i++) f>>v .x>>v.y; f>>M; for(j=1;j<=M;j++) {t=0; f>>a.x>>a.y>>b.x>>b.y; for(i=1;i<=N;i++) if(v.x>=a.x && v.y>=a.y && v.x<=b.x && v.y<=b.y) t++; g<<t<<endl;
}
}
|
|
|
Memorat
|
|
|
|
•catazep
Strain
Karma: -2
Deconectat
Mesaje: 6
|
|
« Răspunde #16 : Ianuarie 08, 2014, 01:43:17 » |
|
daca ar conta si spatiul utilizat as fi cel mai boss:)) toti au de la 2.00kb in sus si eu 0.4:)) si totus functioneaza algoritmul meu doar ca nu e prea eficient:D
|
|
|
Memorat
|
|
|
|
|