Zadanie

Šandyna je šikovná bioinformatička a vo svojej práci často manipuluje RNA a DNA rôznych vírusov. Naposledy potrebovala izolovať sekvenciu istého Krutého Sveta-Paralyzujúceho vírusu. Žiaľ, pri pokuse sa jej to nepodarilo, miesto toho len izolovala \(n\) úsekov aminokyselín a nie presnú sekvenciu ktorú by potrebovala. Ale ešte nič nie je stratené! V laboratóriu biologickými čarami vie Šandyna spájať sekvencie, aby dostala RNA vírusu. Ale to nie je len tak, spájať genetické sekvencie. Niektoré sa pripájajú ťažšie než iné. Potrebuje preto zistiť ako ich čo najľahšie spojiť do chceného RNA. Pomôžte jej!

Úloha

Šandyna má reťazec \(T\), RNA vírusu ktorý chce zostaviť. Tiež už má \(n\) úsekov genetického kódu. Genetický kód si vieme zapísať ako reťazec malých písmen anglickej abecedy. Šandyna má tiež vzorky nukleidov reprezentovaných každým písmenom. Šandyna začína s prázdnou sekvenciou a tú výslednú by chcela zostrojiť pomocou týchto štyroch postupov:

  • Na začiatok aktálnej sekvencie prilepí jeden nukleid (písmenko). Prilepenie nukleidu \(c\) má cenu \(cl_c \cdot |S|\) .

  • Na koniec aktuálnej sekvencie prilepí jeden nukleid (písmenko). Prilepenie nukleidu \(c\) má cenu \(cr_c \cdot |S|\)

  • Na začiatok aktuálnej sekvencie prilepí genetickú sekvenciu číslo \(i\) (\(1 \leq i \leq n\)). Prilepenie sekvencie má cenu \(kl_i \cdot |S|\)

  • Na koniec aktuálnej sekvencie prilepí genetickú sekvenciu číslo \(i\) (\(1 \leq i \leq n\)). Prilepenie sekvencie má cenu \(kr_i \cdot |S|\)

Kde \(|S|\) je dĺžka aktuálnej sekvecie. Všimnime si, že pridať prvý nukleid/sekvenciu je vždy zadarmo.

Šandyna nevie vytvárať paralelne viac sekvencíí a potom ich prilepiť k sebe. Ako najlacnejšie môže vytvoriť správny genetický kód?

Formát vstupu

Na prvom riadku je číslo \(n\) - počet predom izolovaných sekvencií.

Na ďalších \(n\) riadkoch sú tieto sekvencie, \(p_1\) až \(p_n\), reprezentované ako reťazce malej anglickej abecedy.

Na ďalšom riadku je \(26\) medzerami oddelených cien pripojenia jediného nukleidu na začiatok: \(cl_a\), až \(cl_z\).

Na ďalšom riadku je \(26\) medzerami oddelených cien pripojenia jediného nukleidu na koniec: \(cr_a\), až \(cr_z\).

Na ďalšom riadku je \(n\) medzerami oddelených cien pripojenia genetických sekvencií na začiatok: \(kl_1\), až \(kl_n\)

Na ďalšom riadku je \(n\) medzerami oddelených cien pripojenia genetických sekvencií na koniec: \(kr_1\), až \(kr_n\)

A na poslednom riadku je reťazec \(T\) - genetická sekvencia ktorú Šandyna chce vytvoriť.

Formát výstupu

Vypíšte jediný riadok: najmenšiu cenu za ktorú vie Šandyna sekvenciu vytvoriť.

Hodnotenie

Vo všetkých vstupoch platia nasledovné limity:

  • \(1 \leq |T| \leq 1\,000\)

  • \(0 \leq n \leq 100\,000\)

  • Všetky počiatočne izolované genetické sekvencie \(p_i\) majú dĺžku najviac \(100\).

  • Všetky ceny sú medzi \(1\) a \(10^9\)

  • Všetky reťazce obsahujú iba malé písmená anglickej abecedy

Sú \(4\) testovacie sady. V nich navyše platia nasledovné obmedzenia:

Sada 1 2 3 4
\(n \leq\) \(0\) \(10\) \(10\,000\) \(100\,000\)

V sade \(2\) navyše platí \(|p_i| \leq 10\).

Príklady

Input:

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
10 1 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26


abaca

Output:

15

Najlepšie je budovať sekvenciu odzadu. Cena je tak \(0 + 3\cdot 1 + 1\cdot 2 + 2 \cdot 3 + 1 \cdot 4 = 15\)

Input:

3
aba
ba
xy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
3 2 1 3 5 9 10 11 11 9 9 8 7 6 5 1 33 22 11 90 1 1 2 3 5 8
1 2 3
1 1 1
abacaba

Output:

5

Šandyna by mala začať s nukleidom \(c\). Potom za cenu \(1\cdot 1 = 1\) by mala pripojiť sekvenciu ‘aba’ na začiatok a napokon tú istú sekvenciu aj na koniec (za cenu \(1\cdot 4 = 4\), keďže sekvencia po druhom kroku bola ‘abac’. Celková cena je teda \(5\).

Stavanie z jednotlivých nukleidov

V prvej sade za dva body máme iba nukleidy (\(n=0\)) a tak nemusíme implementovť žiadny algoritmus na vyhľadávania podreťazcov. Stačí nám jednoduché dynamické programovanie: pre každý (súvislý) podreťazec si spočítame aká je minimálna cena za ktorý ho vieme dostať.

Cenu pre podreťazec začínajúci na pozícii \(i\) a končiaci na pozícii \(j\) (\(i < j\)) získame iba tak, že sme na začiatok, alebo na koniec prilepili nukleid. Vyskúšame obe možnosti, a keď podreťazce spravcovávame od najkratších, tak získame takto riešenie v čase aj pamäti \(O(|T|^2)\).

Krátke sekvencie

V druhej sade už máme nejaké sekvencie, ale je ich málo a sú krátke. Vieme teda rýchlo zistiť, či na nejakú pozíciu sekvencia pasuje. Môžeme upraviť dynamické programovanie pre prvú sadu: okrem pozretia sa na reťazce o prvé/posledné písmenko kratšie, si pre všetkých \(n\) sekvencií pozrieme, či mohol podreťazec vzniknúť pridaním sekvencie na koniec/začiatok. Toto nám pre každý podreťazec zaberie \(O(n \cdot \max |p_i|)\), čo bohato stačí na získanie ďalších dvoch bodov v druhej sade.

Lepšie riešenie

Prvé dve sady vyžadovali nie až tak trikové dynamické programovanie. Pre posledné dve sady je však pomalé a musíme ho zlepšiť.

Algoritmus nám spomaľujú dva hlavné faktory:

Po prvé, naivné hľadanie, či vieme sekvenciu pridať, alebo nie, je príliš pomalé. Aj keby sme si to pre každú pozíciu predpočítali, bolo by to \(O(n|T|\max |p_i|)\) operácií, čo je priveľa. Vedeli by sme to zlepšiť algoritmom KMP, takto dostaneme zložitosť \(O(n(|T| + \max |p_i|))\).

Druhý problém nastáva s dynamickým programovaním: reťazcov je príliš veľa, takže skúšať pre každý podreťazec všetkých \(n\) je pomalé. Pomôže nám nasledovné uvedomenie: sekvencie nie sú veľmi dlhé. Každý podreťazec môže vzniknúť buď pridaním jedného písmenka na koniec/začiatok, alebo prilepením sekvencie s dĺžkou od 1 do 100 (také sú limity na dĺžky sekvencií). Pre každú pozíciu si dostatočne rýchlym algoritmom vypočítame pre každú dĺžku, či existuje sekvencia, ktorá sedí a aká je najlacnejšia sekvencia pre pridanie zo začiatku/konca. Pre každý podreťazec (od najkratších, cenu nulových vieme) si spočítame najmenšiu cenu, za ktorú ho vieme dostať. Následne spočítame cenu pre dlhšie reťazce pridávaním po písmenku/sekvencie na koniec/začiatok. Pre každý podreťazec takto skúsime najviac \(2 + \max |p_i|\) pridaní, takže časová zložitosť dynamického programovanie je \(O(|T|^2 \max |p_i|)\).

S predpočítaním dostaneme časovú zložitosť \(O(|T|^2 \max |p_i| + n(|T| + \max |p_i|))\) a pamäťovú zložitosť \(O(\sum p_i + |T|^2 + |T|\max |p_i|)\), čo stačí na šesť bodov.

Vzorové riešenie

Aj posledné riešenie, ktoré sme tu doteraz videli, je príliš pomalé pre \(n\) okolo stotisíc. Konkrétne, pomalé je hľadanie všetkých výskytov sekvencíí v reťazci \(T\). Našťastie existuje zovšeobecnenie KMP pre vyhľadávanie viac podreťazcov, a to sa volá Aho-Corasick. (Tutoriál napríklad tu)

Tento algoritmus už nájde všetky výskyty v čase \(O(|T| + \sum p_i)\) a keď ním nahradíme \(n\) volaní KMP, dostaneme vzorové riešenie za osem bodov.

Iné riešenie

Existujú riešenia založené na hešovaní. Keďže sekvencie sú krátke, pre každú dĺžku si vieme pamätať samostaný set s hešmi. Následne to, či existuje reťazec dĺžky \(l\), ktorý končí na pozícii \(i\), si vieme zistiť spočítaním vhodného rolling hashu a nazretím do setu.

Toto riešenie tiež vie získať osem bodov. Dôvod, prečo je ako vzorové uvedený Aho-Corasick, je len ten, že na hash ide teoreticky nájsť vstup, na ktorom bude veľa kolízií a tak nepôjde/bude pomalé.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.