153 Siruri

[•domino]

Aici puteţi discuta despre problema Siruri.

[•filipb]

Am redus problema prin niste operatii evidente la aflarea celei mai lungi subsecvente comune ale celor doua siruri.
Si totusi... se poate cobori sub O(M * N)?  

[andreit1]

Asta e ideea. Se poate aduce la O(N*logN). Exista 2 metode: una cat de cat elementara si alta cu Sufix Array.

[•greco]

Cea pe care ai facut-o tu nu stiu daca e cat de cat elementara... ma rog, cealalta e cu suffix array.

[cristi8]

...hmm... si cum se reduce la aflarea celei mai lungi subsecvente comune ?

[•filipb]

pai daca ai a+b = a[i+1]+b[i+1], atunci a - a[i+1] = b[i+1] - b, si de unde notand X = a + a[i+1] si Y = b[i+1]-b => evident... nu?  

[cristi8]

ok, am inteles. am redus problema la cea mai lunga secventa comuna, m-am documentat despre suffix arrays, am implementat, si iau 45 pct, pe restul imi iese din timp.

cel mai probabil am inteles suffix arrays gresit.
eu fac asa:
sa zicem ca vreau sa gasesc c m l scv com dintre sirurile x si y.

tin un vector sa cu o permutare a numerelor 1..n, care reprezinta pozitiile de start a sufixelor sirului x, ordonate lexicografix. (aici fac qsort cu functie de comparare de complexitate O(n) pe cazul cel mai defavorabil)

pe urma iau fiecare sufix al lui y, si  caut cel mai lung prefix comun cu un sufix al lui x.
vectorul sa (de pozitii de start a sufixelor) fiind sortat, folosesc cautare binara.

e o implementare destul de "urata" pentru prima data cand am scris-o.
am inteles gresit suffix arrays ? mai pot optimiza mai mult ?

[•domino]

Pai construirea suffix array-ului la tine are complexitatea O(N^2*lg N) worst-case daca am inteles bine, e normal sa ia TLE.
Cauta pe net ca exista algoritm O(N*lg N), exista chiar si un articol in GInfo Noiembrie 2005 foarte bun despre ast.a

[•filipb]

[•webspider]

Hey, stie cineva daca e vre-un edge case mai ciudat pe testul 13 ca e singurul la care-mi pica cu "prea lunga".
Any input appreciated.

Mersi!

[•StarGold2]

Se pare ca la aceasta problema se poate lua 100 folosind o solutie cu hashuri gresita (pentru a evita hashurile negative am folosit valoarea absoluta a diferentelor dintre elementele consecutive): pe testul

Cod:

3
1 2 3
3
1 2 3

imi da 3 cand ar trebui sa imi dea 1. Rog pe cineva daca poate sa modifice testele a.i sa dispara mica eroare