infoarena

Aici puteţi discuta despre problema Subsir (http://infoarena.ro/problema/subsir).

am luat de mai multe ori 80 p la problema asta si pana la urma mi-am dat seama ca problema era de la citire:

while not eoln(f) do
 begin
 inc(n);
 read(f,a[n]);
 end;
readln(f);
while not eoln(f) do
  begin
  inc(m);
  read(f,b[m]);
  end;
while not (a[n] in ['a'..'z']) do dec(n);
while not (b[m] in ['a'..'z']) do dec(m);

Scuze pentru cod, dar dupa ce am adaugat ultimele 2 linii am luat 100. De ce? E o chestie de linux? Nu vad ce ar putea sa fie specific la testele 6 si 9 parca. Clarificati-ma si pe mine daca puteti.

Matricea Nr[][] cu ce o initializezi?

nr[i,j]=1 daca a[i,j]=1 si x=y[j] altfel calculezi

cum ai  facut aici ?? "daca exista pozitiile x si y astfel incat A

• = A = B[y] = B[j], se aduna Nr[j] doar daca x < i si y < j"

Sa zicem ca sirurile tale sunt a si b de lungime n si m.
Am verificat daca i si j sunt ultimele pozitii la care apare caracterul a in sirurile tale, lucru care il faci in O(1) adica ai pa[n,a]=i si pb[m,b[j]], pa[i,c] este ultima aparitie a caracterului c in primele i caractere ale lui a(la fel si pt pb). Atunci adaugi nr[i,j] la rezultat.

la exemplu ala dat in problema, restu' nu ii 0?? #-o

Pai singurul subsir de lungime maxima e "ana" deci ai 1 subsir.
Restul impartirii lui 1 la 666013 e 1 :)
adica 1 / 666013 = 0 , rest 1
cu alte cuvinte, 1 = 0 * 666013 + 1
 :mrgreen:

Daca rezultatul il obtin insumand toate valorile nr[j] calculate, asta nu inseamna ca adun toate subsirurile comune si nu numai cele de lungime maxima?

mai trebuie pusa si conditia ca c[j] = lmax, unde lmax e lungimea subsirului comun maximal.

am facut cu matricea nr[j] a numarului de subsiruri comune de lungime maxima si primesc WA la testul 9. Mi-l puteti da si mie sa vad ce am gresit?

NU vreau sa par enervant, dar cred ca am implementat bine ( avand in vedere ca am luat 90 de pcte ) dar tot nu iau testu 9. Ii ceva special la el?

Ce test pici ?

Pe testul 9 (l-am rulat la mine pe calculator) programul tau afiseaza un numar negativ (!!?).

M-am uitat pe sursa si, probabil, e de la faptul ca faci modulo doar la urma, rezultatele intermediare putand depasi long int. Aceasta problema se rezolva transformand toate operatiile din operatii "normale" in operatii "modulo" numarul dat.

Spor la treaba!

Silviu

Mersi. am luat 100. Raman dator cu o bere  :D

imi da si mie cineva un alt test va rog? cel din enunt e prea simplu...

la problema asta fac asa: adun nr[j] cand a=b[j] si lg[j]=lgmax si use[a]=0; pe use[a] il fac 1.. adica o singura data pot sa am caracterul 'a' pe ultima pozitie a unui sir maxim.. si iau doar 40
poate sa ma ajute cineva? nu-mi dau seama de eroarea din algoritm

uite un exemplu :

tot 7 imi da si mie

Vezi ca a fost o problema similara la CEOI parca in 2003, nu mai tin minte exact, ai putea folosi testele de acolo ca sa vezi daca iti merge solutia pe ele.

am modificat putin sursa si am pus conditia cu ultima aparatie, conditia pusa inainte era gresita.. si toate testele de la ceoi le iau.. sa vad acum cand revine evaluatorul ce se intampla
totusi.. iau doar 70, pic testele 7, 8 si 9 #-o

am citit solutia oficiala, dar nu am inteles o kestie, cu ce se initializeaza matricea Nr? adica, am vazut ca la un moment dat, aduni Nr[ii][jj] la Nr[j], dar daca Nr[ii][jj]=0, ce faci?

A zis gogu mai sus!  :P

scuze...am scris fara sa citesc...ce era inainte, da tot nu am inteles, x si y sunt sirurile A si B?

nr[j] = 1 daca cmls[j] = 1 si A = B[j], altfel calculezi cum zice in solutia oficiala   :wink:

Imi spuneti va rog daca pentru exemplul:


Matricea Nr arata in felul urmator:


Multumesc.

La mine arata:
dar eu am calulat doar pentru perechile (i,j) pentru care s1(i)==s2(j) deoarece doar de ele aveam nevoie. In rest am pus 0 deci este cam acelasi lucru cu a ta.

Multumesc! am luat pana la urma 100.

Ahhhhhhhhh... de ce imi da WA doar pe al 9-lea test????
Doar am calculat mereu rezultatul partial in modulo 666013

Aici am sursa comentata

Vad ca nu ai pus peste tot modulo. Cand calculezi nr[ i ][ j ] trebuie sa pui si acolo modulo pentru ca pot fi si ele foarte mari.

Si alta data nu mai posta de 2 ori consecutiv (foloseste edit / modifica)

asta era.mersi :)

pai nu iei fiecare litera si cauti si urm in sirul b?

Iau 70pct, si ma chinui de 4 ore la problema asta.  ](*,) Pe tesul acesta imi da matricea Nr la fel ca celor care au mai postat inaintea mea.


Iau WA pe testele 4,5 si 9. Problema cred ca este la calcularea solutiei. Matricea Nr cred ca o calculez bine. Am citit si pe forum si in aricolu cu solutii, dar nu prea am inteles cum sa determin solutia.

Imi puteti explica? Multumesc anticipat!

P.S: Eu determin solutia parcurgand matricea Nr, si iau cel mai mare Nr[ i ][j] pentru care cmls[ i ][j]=lungimea celui mai lung subsir comun si                a[ i ]==b[j] , si ma indoiesc ca e corect...


L.E. : Am rezolvat, era de la calcularea solutiei.