ditzone
Vizitator
|
|
« : Decembrie 17, 2005, 14:51:45 » |
|
Aici puteţi discuta despre problema Struti.
|
|
|
Memorat
|
|
|
|
cristi8
Vizitator
|
|
« Răspunde #1 : Decembrie 18, 2005, 12:19:23 » |
|
eu la concurs am facut-o in O(P*N*M*log(N*M)) .. folosind ceva asemanator cu QuadTree.. numai ca adaptat pentru dreptunghiuri (care mi-a luat ceva timp pentru a-l implementa si depana pentru prima data).. si am luat 20 (eu ma asteptam la vreo 80 de puncte). acum vad ca se lua 30 cu un algoritm P*N^2*N^2. ..trist, nu ?
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #2 : Decembrie 18, 2005, 12:22:17 » |
|
Trist ca merge asa de prost algoritmul ala. Doar pt. ca e mai complicat nu inseamna ca e mai eficient.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•filipb
|
|
« Răspunde #3 : Decembrie 18, 2005, 12:54:18 » |
|
eu la concurs am facut-o in O(P*N*M*log(N*M)) Un astfel de algoritm este evident mai bun decat P * N^2 * M^2., care lua 30 ( intr-adevar, am conceput testele ca un brute sa ia 30% din teste ), asa k inseamna k implementarea nu este tocmai cea facuta de tine, probabil ai facut operatii in plus care determinau constanta. Si mergea mult mai simplu parerea mea cu AIBuri 2D sau cu segment trees 2D
|
|
|
Memorat
|
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #4 : Decembrie 18, 2005, 15:30:52 » |
|
Testele ar fi trebuit sa fie mai echilibrate un pic. Cu arbori de intervale nu merge mult mai bine decat cu un brute. Asta pentru ca varianta in O(P*N*M*logN*logM) se detaseaza clar de una in O(P*N^2*M^2) decat cand N si M sunt mari, iar in cazul asta oricum ia TLE. Varianta mea de arbori de intervale, destul optimizata, a luat initial 40. (La concurs 0 ). Dupa multe, multe, multe optimizari si incercari, am reusit sa iau 100 cu solutia asta, care acum se comporta aproape ca si cum ar fi O(P*M*N). Apropo, va rog sa nu mai propuneti asa de multe probleme de deque. Sunt deja destule.
|
|
|
Memorat
|
|
|
|
ditzone
Vizitator
|
|
« Răspunde #5 : Decembrie 19, 2005, 09:38:12 » |
|
Dupa punctaje se pare ca nu sunt suficiente
|
|
|
Memorat
|
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #6 : Aprilie 09, 2006, 13:11:16 » |
|
Nu ar trebui chiar un pic ridicata limita? Ma tot chinui si nu reusesc sa iau mai mult de 80. Sau recomandati ceva optimizari.
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #7 : Aprilie 09, 2006, 13:17:49 » |
|
Eu nu am facut nici o optimizare in sursa mea. Incearca sa faci dequeul cam asa: while (prim <= ultim && st[prim].poz <= i-DX) prim++; while (ultim >= prim && st[ultim].val < M[i][j]) ultim--; st[++ultim].val = M[i][j]; st[ultim].poz = i; Eu am facut de 4 ori ceva similar in programul meu si am sub 3 secunde... Si ai grija sa procesezi si perechea inversa (DY, DX) <=> DX != DY. Daca tot nu iti merge, incearca sa citesti cu stringuri...
|
|
|
Memorat
|
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #8 : Aprilie 09, 2006, 13:39:02 » |
|
Stiu sa fac deque, iar daca luam nu luam in considerare dy,dx luam WA nu TLE. Am citit cu stringuri si au mai scazut un pic timpi, dar tot sunt maricei. Tu folosesti cate 2 deque pentru fiecare line/coloana(cum ti-ai ales) + alte 2 deque?
|
|
« Ultima modificare: Aprilie 09, 2006, 14:15:53 de către DeadStar »
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #9 : Aprilie 09, 2006, 13:58:40 » |
|
DA, fac un deque pt. linii, unul pentru coloane si dupa aceea alte doua deque-uri. Singura "optimizare" care o mai vad in sursa mea este ca nu parcurg intotdeauna toata matricea, ci merg de la (1,1) la (m-DX+1, n), de exemplu, in unul din deque-uri...atata tot... si am maxim 2.74 secunde... .
|
|
|
Memorat
|
|
|
|
•DeadStar
Client obisnuit
Karma: 2
Deconectat
Mesaje: 59
|
|
« Răspunde #10 : Aprilie 09, 2006, 20:54:05 » |
|
TEST 6 ...[2.14s]... OK! TEST 7 ...[2.10s]... OK! I-am luat in final capul la strut!
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #11 : Aprilie 09, 2006, 20:56:05 » |
|
|
|
|
Memorat
|
|
|
|
•ooctav
Strain
Karma: -1
Deconectat
Mesaje: 15
|
|
« Răspunde #12 : Martie 28, 2010, 11:50:09 » |
|
Ma puteti ajuta ? Am complexitatea N * M * P. Implementat cu STL iau 2 TLE-uri. Implementat fara iau 1 TLE si 1 WA. Trebuie sa fac ceva optimizari ?
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #13 : Martie 28, 2010, 19:25:41 » |
|
Probabil unul din TLE-uri e WA, asa ca mai bine cauta bug-ul si dupa incearca sa optimizezi .
|
|
|
Memorat
|
|
|
|
•alexandra_sandu
Strain
Karma: 0
Deconectat
Mesaje: 7
|
|
« Răspunde #14 : Mai 03, 2012, 22:30:44 » |
|
Puteti mari limita de timp va rog frumos? Am incercat sa trimit 2 surse care luau inainte 100 si acum iau 80 si 90. Sursa mea ia 70 si am complexitatea optima, nu fac niciun calcul inutil.
|
|
|
Memorat
|
|
|
|
•Schumi
Client obisnuit
Karma: 36
Deconectat
Mesaje: 74
|
|
« Răspunde #15 : Octombrie 06, 2012, 14:04:45 » |
|
Puteti sa mariti limita? Fara parsare se pot lua maxim 90 de puncte.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #16 : Octombrie 07, 2012, 12:57:43 » |
|
Am modificat limita de timp la 2 secunde.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•assa98
Strain
Karma: -19
Deconectat
Mesaje: 33
|
|
« Răspunde #17 : Martie 13, 2013, 20:58:03 » |
|
|
|
|
Memorat
|
|
|
|
•danalex97
|
|
« Răspunde #18 : Martie 15, 2013, 13:34:52 » |
|
Ai putea sa faci deque de mana in loc de cel din STL.
|
|
|
Memorat
|
|
|
|
•assa98
Strain
Karma: -19
Deconectat
Mesaje: 33
|
|
« Răspunde #19 : Martie 15, 2013, 15:22:44 » |
|
pe problema branza luam 40p cu el de mana, pe cand STL ul lua 100...
|
|
|
Memorat
|
|
|
|
•CosminRusu
|
|
« Răspunde #20 : Martie 16, 2013, 13:56:50 » |
|
Eu la problema asta luam 80 de puncte cu i si j declarate global... Dupa ce am facut asa am luat 100 . Destul de ciudat . Cam care ar fi explicatia ?
|
|
|
Memorat
|
|
|
|
•assa98
Strain
Karma: -19
Deconectat
Mesaje: 33
|
|
« Răspunde #21 : Martie 19, 2013, 10:57:26 » |
|
|
|
|
Memorat
|
|
|
|
•CosminRusu
|
|
« Răspunde #22 : Martie 19, 2013, 13:23:42 » |
|
Eu credeam ca e chiar invers .
|
|
|
Memorat
|
|
|
|
•isus
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #23 : Iunie 03, 2014, 15:52:14 » |
|
prea simpla.Cautati "tetris2";
|
|
|
Memorat
|
|
|
|
|