106 Prefix

[•domino]

Aici puteţi discuta despre problema Prefix.

[•Dorin]

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
aababcabcdabcdeabcdefabcdefgaerror
eu cred ca subsirul ingrosat este un prefix periodic care are lungimea mai mare de doi

unde este greseala ?

[u-92]

nu ai inteles enuntul.. prefix - adica doar litere de la inceputul cuvantului.. in exemplul dat de tine cel mai lung prefix periodic este 'aa'

[•Dorin]

mersi pentru ajutor am inteles gresit enuntul
sti am crezut ca oricare subsir periodic este calculat la cel ma mare

[•pauldb]

Mie nu imi  intra in timp citirea (lucrez in Pascal)... eu citesc asa:

Cod:

 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?

[•cristy]

nu ar trebui sa citesti din fisier?

[•pauldb]

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...

[andreit1]

Cea mai buna idee ar fi sa te apuci de C. Daca totusi nu ai timp de asa ceva incearca:

Cod:

fillchar(v,sizeof(v),' ');
        readln(fi,v);

unde v este vector de caractere. Asa o sa iti intre in timp( la limita, dar intra).

[•wefgef]

sau incearca sa folosesti seekeoln

[•pauldb]

multumesc frumos pentru idei...mi-a iesit...

(da, si probabil ca moi apuca de C in viitorul apropiat...)

[•alex_prg]

aicia ii ceva kmp nu ?   

[•wefgef]

se poate si cu suffix arrays daca vrei sa te complici.

[ditzone]

Nu cred ca intra in timp un suffix array... si nici nu vad exact la ce iti foloseste..... KMP e numai bun

[•alex_prg]

suffix array nu stiu exact ce inseamna ... da vroiam sa folosesc functia prefix din kmp. LA asta se refere suffix array ?

[ditzone]

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

[•alex_prg]

  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 

[ditzone]

M-am uitat peste teste toate au lungimea < 1.000.000

[•MarcvsHdr]

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.

[•dobre]

 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!

[•pauldb]

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)).

[•dobre]

 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 

Cod:

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? 

[•pauldb]

Asa ca tine, doar ca nu sunt sigur daca am luat vreodata 100p in Pascal pe infoarena2.

[•cip]

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 ?

[•Alexa_ioana_14]

Eu iau doar 3 teste cu KMP !
Restul TLE...
Mai are cineva alte idei? :-/

[•Pepelea_Flaviu]

Problema se face cu KMP, daca iei TLE inseamna ca nu ai implementat corect algoritmul!