infoarena

Aici se pot pune întrebări legate de problema Revsecv (http://www.infoarena.ro/problema/revsecv) de la Runda 2 (http://www.infoarena.ro/algoritmiada-2016/runda-2) a concursului Algoritmiada 2016 (http://www.infoarena.ro/algoritmiada-2016).

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) ??

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

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

Rezultatul din exemplu este corect.

Se considera in rezultat si secventele de o litera ?

DA

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).

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.

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. :sad:

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.