•domino
|
|
« : Septembrie 04, 2005, 23:47:24 » |
|
Aici puteţi discuta despre problema Prefix.
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #1 : Septembrie 16, 2005, 16:27:53 » |
|
este o linie in fisierul de intrare care arata cam asa aababcabcdabcdeabcdefabcdefgaerror si in fisierul de iesire zica ca lungimea celui mai lung prefix periodic este 2 aababc abcdabcdeabcdefabcdefgaerror eu cred ca subsirul ingrosat este un prefix periodic care are lungimea mai mare de doi unde este greseala ?
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
u-92
Vizitator
|
|
« Răspunde #2 : Septembrie 16, 2005, 17:49:53 » |
|
nu ai inteles enuntul.. prefix - adica doar litere de la inceputul cuvantului.. in exemplul dat de tine cel mai lung prefix periodic este 'aa'
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #3 : Septembrie 16, 2005, 18:58:25 » |
|
mersi pentru ajutor am inteles gresit enuntul sti am crezut ca oricare subsir periodic este calculat la cel ma mare
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
•pauldb
|
|
« Răspunde #4 : Noiembrie 24, 2005, 15:33:31 » |
|
Mie nu imi intra in timp citirea (lucrez in Pascal)... eu citesc asa:
readln(t); for k:=t downto 1 do begin
n:=0; while not eoln(input) do begin n:=n+1; read(a[n]); end; readln; end;
Exista vreo citire mai buna sau ceva?
|
|
|
Memorat
|
Am zis
|
|
|
•cristy
|
|
« Răspunde #5 : Noiembrie 24, 2005, 16:13:57 » |
|
nu ar trebui sa citesti din fisier?
|
|
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•pauldb
|
|
« Răspunde #6 : Noiembrie 24, 2005, 16:18:51 » |
|
da, citesc din fisier... (am uitat sa adaug partea aceea) si iau TLE pe testul 8. Testul 7 aproape imi iese din timp, de altfel cand trimit rezolvarea propriu-zisa iau si pe asta TLE...
|
|
|
Memorat
|
Am zis
|
|
|
andreit1
Vizitator
|
|
« Răspunde #7 : Noiembrie 24, 2005, 17:17:54 » |
|
Cea mai buna idee ar fi sa te apuci de C. Daca totusi nu ai timp de asa ceva incearca: fillchar(v,sizeof(v),' '); readln(fi,v);
unde v este vector de caractere. Asa o sa iti intre in timp( la limita, dar intra).
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #8 : Noiembrie 25, 2005, 00:23:01 » |
|
sau incearca sa folosesti seekeoln
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•pauldb
|
|
« Răspunde #9 : Noiembrie 25, 2005, 08:29:15 » |
|
multumesc frumos pentru idei...mi-a iesit... (da, si probabil ca moi apuca de C in viitorul apropiat...)
|
|
|
Memorat
|
Am zis
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #10 : Aprilie 04, 2006, 21:04:42 » |
|
aicia ii ceva kmp nu ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
•wefgef
|
|
« Răspunde #11 : Aprilie 04, 2006, 21:15:22 » |
|
se poate si cu suffix arrays daca vrei sa te complici.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
ditzone
Vizitator
|
|
« Răspunde #12 : Aprilie 04, 2006, 21:26:21 » |
|
Nu cred ca intra in timp un suffix array... si nici nu vad exact la ce iti foloseste..... KMP e numai bun
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #13 : Aprilie 04, 2006, 21:36:55 » |
|
suffix array nu stiu exact ce inseamna ... da vroiam sa folosesc functia prefix din kmp. LA asta se refere suffix array ?
|
|
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
ditzone
Vizitator
|
|
« Răspunde #14 : Aprilie 04, 2006, 21:39:07 » |
|
Nu, e o chestie ceva mai complicata.. gasesti un articol despre asta(suffix array) prin ginfo... daca poti sa faci rost de asa ceva Oricum problema asta merge fara cmplicatii prea mari cu KMP
|
|
|
Memorat
|
|
|
|
•alex_prg
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #15 : Aprilie 04, 2006, 22:56:27 » |
|
ok cred cas batut in cap. Primesc pentru doua teste "RUN ERROR - Invalid memory reference", desi am declarat toti indicii si chiar toate variabilele long. NU ma prind ... poate exista teste si cu siruri mai lungi de 1.000.000 Am dat acuma de curiozitate lmax = 10.000.000 si merge ... ciudat
|
|
« Ultima modificare: Aprilie 04, 2006, 23:07:06 de către alex_prg »
|
Memorat
|
reality is just an illusion created by the lack of alcohol
|
|
|
ditzone
Vizitator
|
|
« Răspunde #16 : Aprilie 05, 2006, 12:16:05 » |
|
M-am uitat peste teste toate au lungimea < 1.000.000
|
|
|
Memorat
|
|
|
|
•MarcvsHdr
Strain
Karma: 1
Deconectat
Mesaje: 44
|
|
« Răspunde #17 : August 14, 2007, 21:39:04 » |
|
ok cred cas batut in cap. Primesc pentru doua teste "RUN ERROR - Invalid memory reference", desi am declarat toti indicii si chiar toate variabilele long. NU ma prind ... poate exista teste si cu siruri mai lungi de 1.000.000 Am dat acuma de curiozitate lmax = 10.000.000 si merge ... ciudat Pentru cei care scriu surse in C: Nu uitati cand declarati siruri de caractere ca sirurile se termina cu '\0' (sau NULL). Asta inseamna ca daca sirul are N caractere, trebuiesc memorate N+1. Eu imi mai iau din cand in cand cate o tzeapa din asta.
|
|
|
Memorat
|
|
|
|
•dobre
|
|
« Răspunde #18 : Aprilie 28, 2008, 11:48:57 » |
|
Am implementat solutia la problema prefix. Imi da TLE pe 7 si 8. Am implementat cum s-a discutat pe topic, si ca sa aflu lungimea string-ului am facut o cautare binara. Tot 80 p iau. Exista cumva O(1) pentru lungime? Am trimis numai citirea forma banala si cea optimizata. Cea normala nu se incadreaza in timp si cea optimizata pe testul 8 imi ia 456ms. . KMP-ul nu cred ca mai trebuie optimizat, din moment ce citirea consuma cea mai mare parte. >> Poate posta cineva un cod de Pascal pentru citire? << Cred ca ar fii o idee buna sa se faca un articol legat de citirea asta, eu unu nu stiam de ea si vad ca merge doar in FPC. P.S Parerea mea este ca timpul de executie sa fie usor marit pentru problemele cu input mare. Este enervant sa faci ideea de 100 si sa iei 80 ,95 din cauza citirii. P.P.S Bafta la ONI!
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #19 : Aprilie 28, 2008, 12:57:23 » |
|
Problema se poate rezolva in O(N) (fara cautare binara).
[edit:] Limita de timp este intr-adevar enervanta pentru programatorii in Pascal, dar necesara pentru a diferentia solutii cu complexitate apropiata (presupun ca solutia ta e O(NlogN)).
|
|
|
Memorat
|
Am zis
|
|
|
•dobre
|
|
« Răspunde #20 : Aprilie 28, 2008, 22:37:22 » |
|
Solutia mea este O(T*N) am folosit KMP partea cu prefix. T-numarul de teste N-lungimea sirului Cautarea binara o foloseam doar la citire. deci am asa v:array[1..1000000] of char; ..... readln(f,v); leng:=cautare_binara(1,1000000);
undel leng- lungimea sirului, inainte parcurgeam vectorul pana daceam de chr(0) dar cu cautarea binara imi reduce mult din parcurgere. Deci totusi,tu cum ai facut citire?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #21 : Aprilie 28, 2008, 23:52:42 » |
|
Asa ca tine, doar ca nu sunt sigur daca am luat vreodata 100p in Pascal pe infoarena2.
|
|
|
Memorat
|
Am zis
|
|
|
•cip
Strain
Karma: -4
Deconectat
Mesaje: 13
|
|
« Răspunde #22 : Iunie 20, 2008, 13:40:05 » |
|
Imi da si mie cineva o idee ? am incercat tot felul de optimizari dar nu gasesc nimic sa intre in timp.. In mod normal, as face ceva de genul asta : caut lungimea L a prefixului testez cate bucati de lungime L consecutive sunt in acel string si updatez maximul daca e cazul. asta e O(T * N^2) din pacate Singura optimizare pe care o vad ar fi sa nu mai caut fiecare lungime L, ci sa incep din anumite puncte, insa tot in N^2 ajung...imi poate da cineva o idee privind cum sa folosesc KMP -ul ?
|
|
|
Memorat
|
"concureaza cu tine insuti"
|
|
|
•Alexa_ioana_14
Strain
Karma: 6
Deconectat
Mesaje: 37
|
|
« Răspunde #23 : Martie 30, 2009, 14:14:25 » |
|
Eu iau doar 3 teste cu KMP ! Restul TLE... Mai are cineva alte idei? :-/
|
|
|
Memorat
|
|
|
|
•Pepelea_Flaviu
Client obisnuit
Karma: 30
Deconectat
Mesaje: 98
|
|
« Răspunde #24 : Martie 30, 2009, 17:52:47 » |
|
Problema se face cu KMP, daca iei TLE inseamna ca nu ai implementat corect algoritmul!
|
|
|
Memorat
|
|
|
|
|