Diskusija o drugom krugu kvalifikacija

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

Nadam se da vam se zadatak svideo. :slight_smile:

2 Likes

Da, postoji jedan takav slucaj.

1 Like

Tada je resenje -1, tako da imamo i taj slucaj.

1 Like

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.

Ja sam koristio petlju while preko C

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

Od toga kada izlaze rezultati dosli smo do 87 reply-eva na post, nice :smile:

Zar ne pravi prazan hod to sto svaki put ponovo trazi parenta kad ide ka najblizem pustenom na gore?

Ja nisam pre dfsa nasao parente, vec sam ih trazio tokom “penjanja” na gore. Zanima me da li je to ista slozenost.

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

Tako je, unutar tog drugog dfs-a ispituješ sve grane svakog čvora samo jednom po čvoru i zato je linearna složenost.

1 Like

Neke informacije o tome kad ce rezultati?

Vrv sutra ujutru, tako je bilo prosli put, a moguce i kasnije, treba im oko 2 dana.

Priliminarni rezultati

https://takprog.petlja.org/srednjaskola/post/53

3 Likes

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

Možda se tebi tako prikazuje ako koristiš Notepad na Windows-u koji ne ume lepo da prikazuje Unix novi red. Više informacija ovde.

1 Like

Upravo tako pa kako onda da ga ubacim u c++ (freopen, fstream, ili neki drugi program poput notepada)?

Možeš učitavati direktno iz fajla, ili otvoriti fajl recimo u programu Notepad++ pa onda kopirati.

2 Likes