Za koncizno rešenje četvrtog zadatka, preporučujem guglanje “Affine gap penalty”. Ovakva vrsta poravnanja dva stringa je, inače, poželjna pri poravnanju DNK sekvenci, zato što je evolutivno češće da se delovi DNK ubacuju ili izbacuju na nivou većeg broja susednih nukleotida (podstringova) odjednom.
Hirschbergov algoritam, koji je ovde naveden u prethodnoj diskusiji, je samo prostorno optimizovana verzija Needleman-Wunsch algoritma (koji rešava problem ekvivalentan podzadatku X = 0 u ovom zadatku, i zahteva samo jednu DP matricu umesto tri).
Ja sam slicno radio.
Samo me zanim misljenje drugih da li ce ovo biti TLE, sacu da detaljnije objasbim.
Prvo dfsom nadjem rastojanje svakog cvora od root-a i stavim sve to u neki niz.
Nakon toga idem kroz m upita i radim nesto ovako:
Ako je vec odvrnuta ta slavina ispisujem 0. Inace ulazim u ovakvu rekurzivnu funkciju, pretrazujem sve cvorove u listi povezanosti tog cvora, i nadjem onaj koji ima manje rastojanje od korena od posmatranog cvora, pa onda ako je taj sto ima manje rastojanje pusten(ako je odvrnuta voda na toj slavini), vracam taj cvor, inace nastavljam isto na tom cvoru. Na kraju ispisujem razliku rastojanja nadjenog cvora i posmatranog cvora od korena.
Ako si ovo implementirao dobro onako kako si rekao onda je isto O(N+M), pokušaj da dokažeš za vežbu.
Nepotrebno si samom sebi zakomplikovao, mogao si unutar dfs-a umesto da tražiš rastojanje svakog čvora od root-a samo nađeš koji je prvi čvor na putu od tog čvor do root-a (njegov parent).
Jeste, moja je greska, nesto sam se zabunio, slozenost jeste O(N + M), jer cu proci samo jednom kroz svaki cvor(i neke od grana koje su povezane sa njim).
E ljudi test primeri u .zip fajlu znate oni .in i .out nisu dobro napisani ca 4 zadatak, naime nakon cetvrtog inta odma ide string i to ne odvojen( npr. 456 50 20 30kladjsjkas)
Uzgred da li neko ima ideju zasto LCS+BFT ne radi za 100 nego 60 poena?
u principu svako podudaranje iz dva niza se moze posmatrati kao cvor i samo odredjeni cvorovi su povezani vise je stablo sa minimalnim grananjem nego graf ali kapirate