Revsecv

[•klamathix]

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

[•dutzul]

ce se intelege prin disjuncte? disjuncte ca si string ? sau ca si pozitii?

gen ababa

pozitile 1-3 si 3-5 sunt ok (adica coincid) ??

[•klamathix]

Disjuncte ca pozitii, se vede din relatiile dintre indici enuntate inainte de explicatia informala.

[•cosminlinca]

Rezultatul corect la exemplul dat nu este cumva 15,in loc de 16?

[•andreiiii]

Rezultatul din exemplu este corect.

[•xtreme77]

Se considera in rezultat si secventele de o litera ?

[•andreiiii]

DA

[•RazvanR104]

Ma poate ajuta cineva cu o idee de rezolvare? M-am gandit la suffix arrays, dar nu vad nici asa cum as putea scoate mai putin de O(N^2).

[•klamathix]

Mergi pe ideea cu Suffix Arrays. Gândește-te în primul rând cum rezolvi problema dacă nu se pune restricția ca subsecvențele să fie disjuncte ca indici.

[•RazvanR104]

Ma gandesc asa: combin sirul normal cu sirul reversed despartite de un caracter si construiesc suffix array-ul. Parcurg in ordine descrescatoare sufixele (de exemplu) si ma intereseaza suma tuturor LCP-urilor dintre sirul curent si cele de sub el, pe care o adun la solutie. La schimbarea indexului, va trebui sa modific LCP-urile de dedesubt, si am nevoie de inca o structura de date care sa-mi spuna cate valori mai mari decat o anumita valoare am si sa le transforme pe toate intr-o anumita valoare. M-am gandit aici la un arbore de intervale cu lazy update.
Indexul va fi intotdeauna pe un sufix al sirului reversed, iar suma LCP-urilor o voi lua doar din cele care apartin sirului normal.

S-ar putea sa ma complic tare, dar asta e ideea la care am ajuns.

Totusi, nu-mi dau seama inca cum voi elimina solutiile care nu sunt disjuncte.

[•PlayLikeNeverB4]

Eu nu stiu solutia, dar partea aia mi se pare cea mai simpla. Solutiile care nu sunt disjuncte apar la palindroame. Pentru fiecare centru de palindrom poti gasi o formula.