infoarena

Aici se pot pune întrebări legate de problema 2stacks de la Runda 2 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

Ce inseamna valoare ?

Deci valoare (i) inseamna pozitia pentru a i-a operatie ?

v(i) sau acea valoare care apare in text, reprezinta numarul introdus in una din stive la operatia i. Nu inteleg exact intrebarea ta.

Numar adica litera pe care o elimini sau indicele literei ?

Citeste enuntul: " se elimina din fiecare sir pozitiile din stivele corespunzatoare.".

Nu inteleg ce se cere pe aici. Ar merge bagat inca un exemplu si explicat cat de detaliat se poate.

tot nu inteleg. are vreo treaba ca sunt stive alea sau e doar un sir de operatii?

Pe scurt elimini pozitii din una din cele 2 siruri(asta e o operatie). Pozitiile eliminate trebuie sa fie in ordine crescatoare.

Voi prin: intelegeti lungimi egale????

Nu, egal atat lexicografic cat si din pct de vedere al lungimii (cu toate ca prima o cam implica pe a doua). "aa" este egal cu "aa", dar nu este egal "ab".

daca am testul :

atunci am raspunsul :


?

(adica pun in calcul cazul in care cele 2 siruri nu pot fi egale decat daca sunt nule)

Raspunsul este 2 2 pe testul acela.

Deoarece in orice set care respecta restrictiile din enunt (sa faca sirul A sa fie egal cu sirul B si sa aibe lungime maxima) trebuie sa ai 2 operatii si ai 2 seturi posibile:

* insereaza 1 in X, insereaza 1 in Y
* insereaza 1 in Y, insereaza 1 in X

v(3) e egal cu 2? Nu cu 1?

Am modificat acum. Imi cer scuze.

doua seturi se considera distincte daca exista o pozitie S1(i) din setul 1 diferita de S2(i) ?

Nu. Sa consideram ca o operatie i are 2 caracteristici: st(i) - stiva in care se introduce si v(i) - valoarea care se introduce. Doua seturi de operatii sunt distincte daca exista o operatie i pentru care st1(i) != st2(i) sau v1(i) != v2(i).

Pot elimina litere doar dintr-un sir?
Daca primul text e "algoritmiada", iar al doilea e "ddalgoritmiada" se considera valid setul: insereaza 1 in Y, insereaza 2 in Y?

DA. DA.

Nu.

Poate sa-mi aminteasca si mie cineva cum numarai cmlsc-urile, please?

A luat cineva testul de feedback? Daca da, sunt curios cum a facut (mai ales daca a bagat brut N^3).

Eu am luat testul de la feedback, dar nu am luat alte teste care mi le-am dat manual.

Am facut o dinamica in O(N^2), dp[ i ][j] - nr de moduri in care pot face stergerile astfel incat din subsirul format din primele i caractere din sirul A si din primele j din sirul B sa obtin un subsir comun de lungime maxima.
 

Asa am facut si eu.
Pe ce teste nu-ti dadea?

adaccaia
fdcac

Imi dadea ca sunt 6 posibilitati si am facut de mana si am ajuns la concluzia ca sunt mult mai multe :)

LE Scuze. Imi dadea bine. 6 dadea cu alta submisie care nu am lasat-o pana la final :)

Mie imi da ca sunt 22 de posibilitati ...

si mie