|
Titlul: 678 Talharie Scris de: Adrian Diaconu din Martie 23, 2008, 10:12:14 Aici puteţi discuta despre problema Talharie (http://infoarena.ro/problema/talharie).
Titlul: Răspuns: 678 Talharie Scris de: Sanduleac Dan din Martie 23, 2008, 20:35:59 sal everybody. mor aici :) ](*,)
Am folosit ca exemplu sursa mea de la password din arhiva pt aceasta problema, in care fac un fel de kmp (numai ca facand operatii doar pe substring cum ar veni..) - rez in O(n) Scurta explicatie: La fiecare moment am o pozitie din care banuiesc ca va incepe cea mai mica rotatie, si de la acea pozitie pana la pasul curent din sirul analizat (cel alcatuit din input+input) imi construiesc la fiecare pas cate putin vectorul overlap, sau pi, sau cum ii zice, de la kmp :). Vad daca pot sa micsorez si mai mult acesta rotatie presupusa minima pastrand din ea doar cel mai lung sufix comun cu prefixul, peste care vin cu un caracter mai mic decat cel care urma imediat dupa prefix. Problema e ca aici nu pot pastra decat anumite rotatii circulare care sunt conform regulii cu k, asa ca am zis ca daca gasesc o rotatie mai mica lexicografic decat cea presupusa, merg mai departe gasind si rotatii mai mici dar nu o salvez decat daca acea rotatie se poate obtine prin salturi de cate k. Pare corect, totusi iau 0, numai WA for test in `seq 1 10` si nu stiu de ce. Pareri ? Titlul: Răspuns: 678 Talharie Scris de: Savin Tiberiu din Martie 23, 2008, 22:23:22 cam putin 30 ptr suff-array, e totusi o diferenta intre n^2 si nlog^2n :thumbdown:
Titlul: Răspuns: 678 Talharie Scris de: Sanduleac Dan din Martie 23, 2008, 23:28:15 Incearca cu metoda turneului (eu acuma am auzit de ea - luai 90-100 cica.. misto metoda :D).
Meanwhile back to me and my problems.. :) anyone ? Titlul: Răspuns: 678 Talharie Scris de: Andrei Grigorean din Martie 24, 2008, 20:50:41 Intr-adevar, ar trebui sa obtii mai multe puncte cu un suffix array, insa am generat testele asa pentru a evita pe cat posibil ca o bulaneala sa ia prea multe puncte.
Solutia oficiala este cea a turneului :). Titlul: Răspuns: 678 Talharie Scris de: Oltean Dorin din Aprilie 01, 2008, 09:24:41 Nu puteti da mai multe informatii despre metoda tuneului ? ... nu prea am auzit de ea ... multumesc :thumbup:
Titlul: Răspuns: 678 Talharie Scris de: Paul-Dan Baltescu din Aprilie 01, 2008, 10:10:48 Tii pozitii canditate pentru pozitia de inceput a rotatiei si la fiecare pas incerci sa elimini jumatate din aceste pozitii. Mai multe detalii gasesti in articolul cu rotatia lexicografic minima (http://infoarena.ro/rotatie-lexicografic-minima).
Titlul: Răspuns: 678 Talharie Scris de: Oltean Dorin din Aprilie 01, 2008, 13:21:57 ms mult de link (ar trebui sa citesc toatea articolole ca am ce invata :oops:) ... am reusit sa o rezolv :P
|