Editorial for Film


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Prvi podzadatak se može rešiti generisanjem svih stringova dužine do 18 a zatim proverom za svaki od njih da li se svaki dati string javlja tačno jednom. Treba biti pažljiv jer je moguće da dati stringovi sadrže slova koja nisu među prvih K slova engleskog alfabeta.

Drugi podzadatak se može rešiti generisanjem svih mogućih preklapanja data dva stringa, uključujući i situaciju kada se stringovi uopšte ne preklapaju.

Na sličan način se može rešiti i treći podzadatak, samo je u slučaju kada imamo N = 3 stringa povećava se složenost generisanja preklapanja.

Postoji i drugačije rešenje za ova dva podzadatka, čija ideja je jako važna za rešavanje zadatka za maksimalni broj poena. Recimo, za N=3, posmatrajmo jedno parcijalno rešenje, odnosno, prefiks nekog najkraćeg validnog stringa. Neka je mask bit-maska sa 3 bit-pozicije koja nam govori da li se i-ti string do sada već javio, i neka su p_1,p_2,p_3 dužine najdužeg stringa koji je sufiks trenutnog rešenja a ujedno i prefiks prvog, drugog i trećeg stringa, redom. Dodavanjem jednog slova mi možemo da proverimo koje su nove vrednosti najdužeg sufiksa za sva tri stringa. Ako je neka od tih dužina sufiksa postala jednaka dužini celog stringa, to je novo pojavljivanje tog stringa. Ako se taj string već javio, rešenje postale nevalidno, inače, u odgovarajući bit trenutne bit-maske treba upisati bit 1. Korisno je unapred izračunati prelaze, tj. trojke (l, x) \rightarrow l', gde je l stara dužina prefiksa stringa, x slovo koje se dodaje, l' je nova dužina tog najdužeg prefiksa. Ovi prelazi se mogu izračunati KMP algoritmom, ali i ne moraju, s obzirom da brute-force implementacija ima vremensku složenost O(L_i^3). Nas onda samo zanima najkraći put (gledano po broju slova) od stanja (mask=000_2, p_1=0, p_2=0, p_3=0) do nekog stanja gde je mask=111_2. Pored prelaza, ovo rešenje radi u složenosti O(K \times L_1 \times L_2 \times L_3).

Za maksimalni broj poena dovoljno je da primetimo da ne moramo da pamtimo najduži prefiks za svaki pojedinačni string, već je dovoljno da nam stanje bude najduži sufiks trenutnog parcijalnog rešenja koji je ujedno i prefiks nekog od datih stringova, tačnije, stanje će nam biti tačno o kom prefiksu se radi - ovih prefiksa može biti najviše \sum L_i. Prelaze možemo izračunati u linearnom vremenu pomoću Aho-Corasick algoritma ali, kao i ranije, ne moramo, jer ponovo brute-force nalaženje prelaza radi u vremenskoj složenosti O((\sum L_i)^3) i može se implementirati elementarnim (i sporim) algoritmima pretrage stringova. Sada, konačno rešenje izgleda ovako: Napravimo graf čiji su čvorovi uređeni parovi (mask, prefix) gde je mask bit-maska sa N pozicija koja nam govori o tome da li se i-ti string do sada javio, a grane su usmerene i od svakog čvora izlazi tačno K grana, po jedna za svako slovo, dolazni čvor za svaku granu se može naći gore opisanim postupkom pomoću izračunatih prelaza. Sada je rešenje najkraći put u ovom grafu od čvora \((0, "")\) do nekog čvora čija se bit-maska sastoji samo od jedinica. Ovaj najkraći put možemo naći običnim BFS algoritmom. Vremenska složenost je O((\sum L_i)^3 + (\sum L_i) \times 2^N \times K).


Comments

There are no comments at the moment.