|
Titlul: 153 Siruri Scris de: Mircea Pasoi din Decembrie 12, 2005, 00:20:26 Aici puteţi discuta despre problema Siruri (http://infoarena.ro/problema/siruri).
Titlul: 153 Siruri Scris de: Filip Cristian Buruiana din Decembrie 14, 2005, 18:13:45 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)? :? Titlul: 153 Siruri Scris de: andreit1 din Decembrie 14, 2005, 18:31:49 Asta e ideea. Se poate aduce la O(N*logN). Exista 2 metode: una cat de cat elementara si alta cu Sufix Array.
Titlul: 153 Siruri Scris de: Tiberiu-Lucian Florea din Decembrie 14, 2005, 18:55:21 Cea pe care ai facut-o tu nu stiu daca e cat de cat elementara... ma rog, cealalta e cu suffix array.
Titlul: 153 Siruri Scris de: cristi8 din Ianuarie 22, 2006, 20:54:40 ...hmm... si cum se reduce la aflarea celei mai lungi subsecvente comune ?
Titlul: 153 Siruri Scris de: Filip Cristian Buruiana din Ianuarie 22, 2006, 21:42:01 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? :?:
Titlul: 153 Siruri Scris de: cristi8 din Ianuarie 23, 2006, 18:54:17 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 ? Titlul: 153 Siruri Scris de: Mircea Pasoi din Ianuarie 23, 2006, 19:36:49 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 Titlul: 153 Siruri Scris de: Filip Cristian Buruiana din Ianuarie 23, 2006, 20:34:23 Cauta "Udi Manber & Gene Myers - “Suffix arrays- A new method for on-line string searches.”" - asta e bibliografia pentru un articol de la lot care mi se pare marfa si usor de inteles despre Suffix Trees.
Titlul: Răspuns: 153 Siruri Scris de: Dumitru Bogdan din Decembrie 16, 2010, 02:03:45 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! Titlul: Răspuns: 153 Siruri Scris de: Emanuel Nrx din Martie 23, 2016, 23:49:34 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 imi da 3 cand ar trebui sa imi dea 1. Rog pe cineva daca poate sa modifice testele a.i sa dispara mica eroare :ok: |