023 Trie

[•filipb]

Aici puteti discuta despre problema Trie.

[•mika17]

pt cei ce folositi streamuri si eventual nu luati 100 aveti grija la citire ... ceva genul

Cod:

while(!fin.eof()) 
 fin>>op>>cuv 

poate cauza buguri de ex daca nu gaseste cifre/caractere compatibile sau ajunge la sf fisierului si atunci citirea nu mai are loc si raman vechile valori si algoritmul le foloseste pe acelea / calc de 2 ori pt aceleasi valori ... pt aceasta prob puteti folosi ceva gen

Cod:

if( fin.good() ) { op1() op2() etc}

acest mic detaliu a facut la mn dif dintre 30p si 100p

[edit] e o idee buna sa faci bucatile de cod vizibile folosind tagul "[ code ]"

[•Bit_Master]

De ce nu s-au reglat restrictiile problemei sa suporte cei 50MB limita, pt ca testele de evauare sa fie de toate genurile, nu neaparat omogene. Mi se pare ciudat sa favorizezi o metoda de rezolvare prin intermediul testelor.

[•pauldb]

Aceasta problema este in scop educational. Este normal sa fie evidentiata o anumita rezolvare pe care le-o propunem ca exercitiu utilizatorilor.

[•APOCALYPTO]

A mai luat cineva 100 folosind '\n' in afara de Lucian?
Eu iau 0 puncte asa si 100 daca folosesc strlen() sau '\0'.

[•amadaeus]

Te referi, probabil, la caracterul in functie de care te opresti din recursivitate, iar asta e un detaliu strict legat de implementarea algoritmului tau.
Trebuie sa te uiti mai atent peste notiunile de null-terminated string si line break si vei vedea ca iti vei putea face sursa, cu cateva modificari minore de indici, sa functioneze si cu '\n' 

[•APOCALYPTO]

Te referi, probabil, la caracterul in functie de care te opresti din recursivitate, iar asta e un detaliu strict legat de implementarea algoritmului tau.
Trebuie sa te uiti mai atent peste notiunile de null-terminated string si line break si vei vedea ca iti vei putea face sursa, cu cateva modificari minore de indici, sa functioneze si cu '\n'  

Am inteles de ce mergea la tine, fgets citeste si '\n', iar .getline() citeste '\n' dar il da afara dupa.
La ce te referi prin "indici"?

[•amadaeus]

Nu m-am uitat atent peste funcia ta de citire, imi pare rau.
Initial crezusem ca e vorba despre cum accesezi caracterele in array-ul in care le memorezi, facand un pas suplimentar pentru a trece de la '\n' la '\0'.

[•APOCALYPTO]

Nu m-am uitat atent peste funcia ta de citire, imi pare rau.
Initial crezusem ca e vorba despre cum accesezi caracterele in array-ul in care le memorezi, facand un pas suplimentar pentru a trece de la '\n' la '\0'.

Nu-i nici o problema!  

[•nicolaetitus12]

La metoda bruta stergerea nu e O(L*N) ?

[•zsee]

"Pentru toate operatiile, cuvantul w este format din maxim 20  de caractere din intervalul 'a'..'z'"
Ar trebui corectat, ca testele contin si numere...

[•gabitzish1]

M'am uitat peste cateva teste si nu am vazut cifre in interiorul cuvintelor. Care teste contin cifre?

[•zsee]

scz am gresit eu... miam dat seama care era problema...
Asa apare la mine in notepad: 0 ab0 abac3 qfksxe2 (...) De fapt notepadul era de vina, ca in alte aplicatii se vede normal...

[•S7012MY]

La problema iau 30 de puncte cu multe sigsegv si incorecturi. Banuiesc ca e din cauza citirii deoarece atunci cand nu am newline la sf fis. merge orice test. Citesc asa:

Cod:

for( ;!f.eof();f.get()) {
        f>>ce;
        f.getline(cuv,50);
        if(cuv[strlen(cuv)]!='\0')
            cuv[strlen(cuv)]='\0';
        if(!ce) t->insert(t,cuv);
        else if(ce==1) t->del(t,cuv);
        else if(ce==2) g<<t->query(t,cuv)<<'\n';
        else if(ce==3) g<<t->prefix_comun(t,cuv,0)<<'\n';
    }

sursa e asta:http://infoarena.ro/job_detail/486230?action=view-source

Ma poate ajuta cineva sa o fac sa mearga de 100?
Nu mai am nevoie. Celor carora nu le iese sa foloseasca

Cod:

if(fin.good){
switch (op) etc
}

(daca fol streamuri de c++)

[•livium]

Stie cineva ce face *s - 'a' ?
Ca eu nu inteleg.

[•pauldb]

Inseamna a cata litera din alfabet e caracterul catre care indica pointer-ul s.

[•livium]

Merci!
Mi-am dat si eu seama de asta la scurt timp dupa ce am pus intrebarea.

[•maritim]

Salut !

Ma puteti ajuta si pe mine va rog, sa inteleg care este problema implementarii mele? Iau numai 10 puncte, cu toate ca am luat cateva teste, le-am comparat si toate rezultatele imi dau ok .

Multumesc!

L.E. : Multumesc frumos PlayLikeNeverB4 ca ai incercat sa ma ajuti! Se pare ca nu initializam o valoare din Trie cu 1, cea care pastra numarul de prefixe din fiecare elemnt!

[•razyelx]

rog pe cineva care are putin timp sa se uite peste sursa mea. in mare parte am segmentation fault si incorect. merge pe exemplu.
 

[•algotroll]

Va rog frumos daca poate cineva sa isi dea seama ce nu e in regula cu implementarea mea, ma streseaza de mai mult de o ora.
Mai precis, pentru

Cod:

struct nod
{
    nod* nlist[26];
    int ap;
    nod()
    {
        memset(nlist,0,sizeof(nlist));
        ap=0;
    }
};
void insert(nod* pN, string &a)
{
    for (int i=0;i<a.size();i++)
    {
        if (pN->nlist[alf(a[i])]==0)
        {
            nod* pTmp = new nod;
            pN->nlist[alf(a[i])]=pTmp;
            pN=pTmp;
        }
        else pN=pN->nlist[alf(a[i])];
    }
    pN->ap++;
}
int pre_com(nod* pN, string &a)//prefix comun
{
    for (int i=0;;i++)
    {
        if (pN->nlist[alf(a[i])]==0) return i; //asta e singura verificare pt incheierea
        pN=pN->nlist[alf(a[i])]; // buclei; frunza are nlist nula
    }
}

cu alf(x)==x-'a'
efectuarea

Cod:

nod trie; insert(&trie,"aa");  pre_com(&trie,"aa"); 

da segmentation fault. pe gdb nu apare problema.

[•Prostu]

Nu imi este clar de ce iti da KBS 11 in cazul pe care l-ai trecut tu acolo, dar din restul codului observ ca nu folosesti variabila ap in mod consistent. In unele cazuri consideri ca este numarul de aparitii al cuvintelor iar in alte cazuri consideri ca este numarul de cuvinte dintr-un subarbore. Cred ca vrei sa folosesti 2 variabile separate pentru asta. Asta explica de ce iei incorect, dar sunt sanse mari ca KBS-ul sa fie din aceiasi cauza.

[•algotroll]

Nu imi este clar de ce iti da KBS 11 in cazul pe care l-ai trecut tu acolo, dar din restul codului observ ca nu folosesti variabila ap in mod consistent. In unele cazuri consideri ca este numarul de aparitii al cuvintelor iar in alte cazuri consideri ca este numarul de cuvinte dintr-un subarbore. Cred ca vrei sa folosesti 2 variabile separate pentru asta. Asta explica de ce iei incorect, dar sunt sanse mari ca KBS-ul sa fie din aceiasi cauza.

Da, ai dreptate, trebuia sa numar cate aparitii au ascendentii fiecarui nod. Nu mi-am dat seama ca fara stergerea se face prea dificil. mersi!

[•Alexxino7]

what the hell is this? http://infoarena.ro/job_detail/795049
Nu prea le am cu pointerii dar sursa ruleaza fara probleme pe calculatorul meu.
Dupa ce am scos asserturile am luat iar killed by signal 11 http://infoarena.ro/job_detail/795053, deci banuiesc ca se declanseaza vreunul din ele. Dar la mine pe calc nu se declanseaza nici unul.
Later Edit: Nu mai este nevoie i-am dat de cap pana la urma.

[•tudy23]

Am rezolvat problema si primesc doar 5 puncte. Am verificat fisierul meu .out cu fisierele de test si da bine pe cel putin 4(atat am verificat, atat manual cat si folosind un program). E cineva binevoitor sa se uite peste sursa?Poate fac vre-o afisare gresit. Multumesc!

[•PlayLikeNeverB4]

Vezi ca ai niste warning-uri la compilare. Posibil ca de acolo sa vina diferenta.