|
Titlul: 095 Color Scris de: Mircea Pasoi din Septembrie 01, 2005, 17:58:12 Aici puteţi discuta despre problema Color (http://infoarena.ro/problema/color).
Titlul: 095 Color Scris de: Danila Iulian din Februarie 20, 2006, 23:24:30 Merge rezolvarea cu cautare binara?
Sau ar trebui sa-mi dau seama de cate triunghiuri negre sunt dupa ce aflu numarul celor rosii? Titlul: 095 Color Scris de: Andrei Grigorean din Februarie 21, 2006, 16:23:18 sau ar trebui sa iti dai seama cat e suma celor negre+cele rosii ;).
Titlul: Răspuns: 095 Color Scris de: Dumitran Adrian Marius din Martie 12, 2007, 23:55:23 limita de timp?
am O(n) depasit:) mariti limita la 0,5 sa poata citi lumea linistita Titlul: Răspuns: 095 Color Scris de: Mihai Leonte din Martie 29, 2007, 22:27:39 Ceva e tare tare naspa la problema asta. Am o solutie care tot ia 50 p astfel:
- primele 4 teste, TLE. - testul 5, TLE/WA (depinde de optimizari) - ultimele 5 teste, corecte Algoritmul meu se compune din: 1. citire - O(m) <- nu se poate scapa de asta 2. un DF <- ca sa determin cate cicluri rosii sunt. 3. niste calcule care duc la solutie. O(2*n) (am pus si constanta). Am incercat mai multe variante. Simulez listele de adiacenta cu vectori (adica sunt alocate static) ca sa evit sa bag pointeri (nu se prea cunoaste diferenta, 0,01 secunde la testul 5). DF-ul n-ar trebui sa ia mai mult de O(n), avand in vedere ca sunt n noduri. Eu mai fac niste operatii si pentru cazul in care nodul in care incerc sa merg e deja vizitat (totusi, doar 3 adunari !!)... :'( Ce pot sa ii mai fac? Tot iau TLE. Evident, solutia este liniara. In cazul asta, constanta conteaza mult. :? Titlul: Răspuns: 095 Color Scris de: Tabara Mihai din Martie 29, 2007, 22:30:28 Eu am parsat citirea...desi nu a fost nevoie decat pentru ultimul test :-k
:-k Titlul: Răspuns: 095 Color Scris de: Mihai Leonte din Martie 29, 2007, 22:48:34 Ok. Tocmai am realizat ceva. Calculam tot felul de tampenii aiurea, ca se reduceau in formula finala. Acum dupa simplificare algoritmul meu e:
1. citirea O(m) 2. calculul O(n) Din moment ce n<=4000, nu prea conteaza ala. Iau 80p. :| - TLE pe primele doua teste. Cum ai parsat citirea? Numerele sunt cate doua pe linie. Nu stiu daca e foarte mare diferenta sa citesti M linii sau sa citesti 2*M numere. Deci, problema asta chiar are limita de timp pus aiurea. Imi pare rau ca m-am chinuit doua ore sa ii reduc timpul de executie cu 12 milisecunde, in conditiile in care se ia TLE cu citire :|:|. Titlul: Răspuns: 095 Color Scris de: Tabara Mihai din Martie 30, 2007, 07:18:54 Nu stiu ce sa zic... :-k Eu luam 90 fara parsare.
( Am parsat cu fread ). Tie cred ca O(m) din citire iti face probleme mai degraba decat O(n) din rezolvare. Incearca sa parsezi citirea si vezi ce iese. :wink: , desi sincer sa fiu e destul de ciudata faza, atata timp cat iti intra ultimul test in timp si nu iti intra primele doua :-s Oricum, incearca si parsare ca nu ai nimic de pierdut :thumbup: :peacefingers: Titlul: Răspuns: 095 Color Scris de: Bogdan-Cristian Tataroiu din Martie 30, 2007, 08:29:07 Ultimul test e mic, primele 2 sunt alea mari... Nu prea aveai cum sa iei TLE pe ultimu si sa-ti intre primele 2 :P
Nu intra problema fara sa parsezi citirea :P Titlul: Răspuns: 095 Color Scris de: Tabara Mihai din Martie 30, 2007, 10:36:34 Ultimul test e mic, primele 2 sunt alea mari... Nu prea aveai cum sa iei TLE pe ultimu si sa-ti intre primele 2 :P Nu intra problema fara sa parsezi citirea :P Mda.. :oops:..ai avut dreptate. :thumbup: M-am uitat acuma si eu in monitor la sursa aceea de 90, fara parsare a mea. Cod: Test Timp executie Memorie folosita Mesaj Punctaj :fool: |