[secventa nu subsir]

vreau sa remarc o greseala referitor la linkul catre wikipedia. Ala se refera la longest common substring nu subsequence.
De fapt la problema asta este vorba de secventa nu subsir !!!!!!!!!!!!!!!!!!

OK.
Merci pentru informatii.

care este complexitatea lui min(a[ h ][ x ],a[ h ][ x+sh ])?
este O(1)?

dar complexitatea lui a[ y-x ][ x ]?
este tot O(1)?

nu ia mai mult timp prima varianta pt. ca se compara doua valori, pe cand in a doua doar se returneaza o valoare?

Daca e asa, atunci pt. un milion de interogari sa zicem,  nu e metoda mea mai eficienta, desi ocupa mai multa memorie si timp la crearea matricei?

Da, cel mult O(N^2). Insa avantajul se va concretiza la query, deoarece nu mai trebuie sa aflam vreun minim ci doar returnam a[ y-x ][ x ].

eu am inteles rmq-ul asta dar am o intrebare:

de ce folosim puteri ale lui 2 si nu ceva mult mai simplu precum o progresie aritmetica?
in felul asta matricea ar fi mai mare ce-i drept insa query-ul ar fi mai rapid pentru ca nu ar mai fi nevoie sa calculam minimul dintre doua valori (deoarece nu vom mai folosi log)

cum m-am gandit eu:

a[ i ][ j ]=min(a[i-1][j],a[i-1][j+i-1]);
a[ i ][ j ]=min(a[0][j],...,a[0][j+i]);
deci a[ i ][ j ] este minimul pe sirul care incepe la j si are lungimea de i+1

prin urmare minimul din intervalul [x,y] ar fi pur si simplu a[ y-x ][ x ] (fara sa trebuiasca sa mai folosim vreo functie de minim)

deci, eu zic ca metoda asta a mea e mai eficienta fata de cea de pe site, atunci cand se  
folosesc foarte multe interogari.

Gresesc undeva?

Extraordinar!
L-am inteles. 
Ptiu... ce algoritm. Ma doare capul si acuma.
Cine a inventat algoritmul asta cred ca n-avea ce face!

Daca nu-mi dadeai explicatiile astea doua nu puteam sa-mi dau seama cum functioneaza .

Merci mult! Toate cele bune

formula pentru rmq[ i ][j] am luat-o de aici: http://www.descarca-x.info/showthread.php?tid=568

dar repet: nu se verifica pentru i=3

Am I missing something?

Va rog raspundeti-mi!!!

care este relatia de recurenta pe linii?

cumva asta:

Cod:

rmq[i][j]=min(rmq[0][j],...,rmq[0][j+pow(2,i)-1])

?

daca asa e, atunci de ce mie imi da

rmq[3][j]=min(rmq[0][j],...mrmq[0][j+6]);

si nu j+7 la sfarsit ?

Gata, am inteles.
Piuhh, greu de tot query-ul ala de inteles. Mi-a ars multi neuroni.

Eu nu pot sa inteleg cum se reprezinta valorile din exemplu 4 3 5 6 1, ca un arbore de intervale.
 
Poate cineva sa-mi zica cum sunt asezate aceste valori in vectorul care memoreaza arborele?

Eu stiu si cum functioneaza un heap, dar aici nu-mi pot da seama.
Va multumesc!

Aha...deci ar trebui sa analizez mai lejer complexitatea unui algoritm.
Cat despre cele doua linkuri de pa wikipedia pot sa spun doar ca ma depasesc.
Merci oricum!

de exemplu pentru sirul 3 4 1 6 5 cu k=3 se parcurg urmatorii pasii:
se compara:

4 cu 3
1 cu 4
1 cu 3
6 cu 1
5 cu 6
5 cu 1

deci sunt 6 comparari.
Nu rezulta de aici ca complexitatea este 6 (adica N+1) si nu 5 (adica N) pentru exemplul dat?

Eu nu pot sa inteleg de ce solutia cu deque are complexitate O(N).
Eu m-am gandit la ce complexitate are algoritmul postat aici cu deque si imi iese o complexitate mai mare decat N, insa in nici un caz N.
Pentru ca se parcurge vectorul A o data cu for si apoi se mai parcurge partial si Deque cu un while in la fiecare iteratie in for.
Deci eu zic ca complexitatea trebuie sa fie mai mare decat N.

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

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

Asa m-am gandit si eu. Ciudat e ca merge si nu pot intelege de ce.
Nu pot sa inteleg care ar putea fi demonstratia matematica pentru algoritmul asta, asa cum exista una pentru algoritmul care rezolva acceasi problema, insa utilizand un graf auxiliar (http://www.youtube.com/watch?v=NlQqmEXuiC8).

Merci!
Eu m-am gandit la un algoritm propriu inspirat de chestia asta cu vectorii L si R.
Incerc sa cuplez un nod din stanga cu unul din dreapta.
Daca nodul din dreapta nu e cuplat atunci fac cuplajul.
Altfel caut un alt nod din dreapta cu care nodul din stanga se poate cupla.
Daca toate nodurile din dreapta nodului din stanga sunt cuplate atunci decuplez un nod din dreapta, il cuplez cu nodul din stanga, iar nodul din stanga care a fost decuplat de nodul din dreapta caut sa-l cuplez cu un altul din dreapta necuplat.

Faza e ca algoritmul la care m-am gandit eu merge foarte bine pe foaie, intru-cat l-am testat multe grafuri bipartite?
Cumva algoritmul tau face acelasi lucru?

Apropo: algoritmul lui Stroe nu merge pentru un graf anume. E gresit.

Algoritmul lui Marius Stroe nu urmeaza pseudocodul Hopcroft-Karp de pe wikipedia. E cu totul altceva!

Poate cineva sa comenteze codul (http://infoarena.ro/job_detail/225128?action=view-source) pentru ca nu pot sa-l inteleg. Eu stiu cum sa fac problema asta dar intr-un mod mult mai dificil de implementat, de aceea va rog daca poate cineva sa ma ajute sa inteleg codul lui Marius Stroe!

Am trimis si eu un program spre evaluare (algoritmul lui Gabow) si am erorile astea pe care nu le-am avut pe pc-ul meu:

Eroare de compilare:
user.cpp:160:2: warning: no newline at end of file
user.cpp:30: error: '>>' should be '> >' within a nested template argument list
user.cpp:31: error: '>>' should be '> >' within a nested template argument list
user.cpp:71: error: '>>' should be '> >' within a nested template argument list
    

Care-i faza?

"Pentru determinarea lantului, vom adaugata fictiv o muchie intre aceste doua noduri, dupa care vom aplica algoritmul de determinare a unui ciclu Eulerian. Eventual, acest ciclu determinat va fi 'rupt' in locul in care apare muchia adaugata si tiparit in ordinea corecta."

Eu am implementat algoritmul recursiv si totul merge perfect. Nu mai trebuie sa adaugi nicio muchie fictiva. Trebuie doar sa apelezi euler(nod de grad impar). Si merge. NU inteleg de ce ati scris chestia asta cu muchia. Va rog raspundeti-mi ca sa nu mor prost.

[email protected]