TLCS rapid

[•cmiN]

Stie cineva un algoritm mai rapid decat dinamica clasica pentru cel mai lung subsir comun ?
Am gasit documentatie pe net, ceva cu bit string sau sortare si cautare binara, dar nu au un amarat de pseudocod sau orice sa inteleg exact cum calculeaza anumite chestii. Sa fie sub O(n*m+n+m) e tot ce ma intereseaza.
-> http://www.spoj.pl/problems/TLCS/

[•blasterz]

Exista o solutie in O(n * nr_aparitii * log (n * nr_aparitii))
Unde n este lungimea unui sir iar nr_aparitii este numarul maxim de aparitii a unui caracter/numar.
Adica daca ai n = 30 000 si stii ca fiecare numar apare de cel mult 100 de ori, atunci algoritmul iti va intra probabil intr-o secunda.

Ideea e cam asa:
Pentru fiecare numar distinct din al doilea sir, mentii cate o lista cu toate aparitile din primul sir, sortate descrescator.
Acum inlocuiesti in sirul intiial, toate aparitiile, cu toata lista respectivului. Dupa asta, daca faci cel mai lung subsir crescator, vei obtine solutia dorita.

exemplu:

sir1: 3 2 4 5 2 3
sir2: 2 5 3 2 3

Avem listele:

2: 5, 2 (2 se gaseste in primul sir pe pozitiile 5 si 2)
3: 6, 1
5: 4

Acum inlocuim fiecare aparitie cu lista lui (in al 2lea sir)

5 2 4 6 1 5 2 6 1

Un subsir crescator de lungime maxima este: 2 4 5 6

Daca luam din primul sir de pe pozitile 2 4 5 6 obtinem: 2 5 2 3

[•cmiN]

Merci mult.
Am incercat http://pastebin.com/jGjLkMiD dar n-am idee la implementarea cu arbori, iar la generare ma gandeam la un sort+binsearch dar pierd cand caut indicii in lis(). Oricum cam tot acelasi timp e, faza naspa e ca de data asta nu-mi intra deloc in timp, ori conditionez la primul rezultat ori iau TLE pe orice timp il bag in main in if.

[•blasterz]

Am incercat si eu TLCS... si sincer am pus doar sa afiseze NU tot timpul... si imi da TLE...deci e ceva dubios ...

Later Edit: Am luat 995 puncte (din 1000) cu metoda clasica in O(n * m) optimizata... totusi nu reusesc sa obtin mai mult.

[•cmiN]

Am vazut ... gege esti boss ... ce optimizari ?
Incercasem si eu ceva sa scot un timp la jumatate + triming dar WA :\.

LE: Asta imi da cel mai bine http://ideone.com/wgLbx 867 ... mai mult nu pot scoate. Totusi nu-mi este de ajuns imi trebuie pentru recruitcoders .

[•blasterz]

Am vazut ... gege esti boss ... ce optimizari ?
Incercasem si eu ceva sa scot un timp la jumatate + triming dar WA :\.

LE: Asta imi da cel mai bine http://ideone.com/wgLbx 867 ... mai mult nu pot scoate. Totusi nu-mi este de ajuns imi trebuie pentru recruitcoders .

Vezi ca la recruitcoders e limita de 10 secunde ...

[•cmiN]

Corect, dar scorul il ia de pe spoj (teste, compilare, run totul se face acolo) ... oricum am reusit sa-mi iasa de 1000. Dinamica clasica numai ca pentru generarea solutiei trebuie folosit un vector nu o structura/clasa cum am facut eu. Si apoi pentru fiecare caracter se cauta pozitiile de unde a ramas cautarea anterioara. Desi pare ineficient e mai rapid.

[•blasterz]

Pai e la fel de eficient, dar faptul ca folosesti mai putina memorie te ajuta mult (memorie putina => timp de executie mai mic)