Zadanie

Konečne sa to stalo. Je na svete nová celotrojstenová infraštruktúra. Je úplne dokonalá, spĺňa všetko, by si od nej čakal. Je univerzálna pre všetky semináre, dlhodobo udržateľná, dobre zdokumentovaná… Vyskakuješ meter dvadsať od šťastia. Nič ti nemôže pokaziť tento úžasný pocit. Kontroluješ si inbox tvojho trojsten mailu, v ktorom nachádzaš samé pochvalné maily od vedúcich, mobil na stole ti pípa od všetkých tých pochvalných správ na Slacku. Čo je to ale za divný zvuk? Veď to znie ako zvonenie mobilu… Zrazu si uvedomíš, že si zase zaspal v T21 na gauči, pomaly otvoríš oči, a uvedomíš si, že to bol iba sen. Zdvihneš mobil, a zisťuješ, čo sa zase deje. Volá nejaký Trojsten vedúci, že, ehm, ako to povedať, nevie svoje heslo do Trojsten účtu.

Ale že to nie je až taká tragédia, lebo predtým ako ho zabudol, si vymyslel pomôcku ako zmenšiť počet možných hesiel. Vyrobil si papieriky, na ktoré si napísal slová, o ktorých vie, že sa na všetkých pozíciách líšia od hesla. A dokonca, týchto papierikov je presne \(n\).

Vzápätí ale dodáva, že on by ti vlastne nevolal, on tie možnosti vyskúša aj sám, ale potrebuje, aby si mu umožnil mať väčší počet pokusov na zadanie hesla. Po chvíli frfľania súhlasíš, a kým sa stihneš spýtať, koľko pokusov potrebuje, tak už máš na stole všetky tie papieriky… To aby si si zase všetko zistil sám…

Úloha

Na každom z \(n\), \(1\leq n \leq 1\,000\) papierikov je napísané slovo, ktoré tvoria len malé písmená anglickej abecedy. Všetky tieto slová sú rovnako dlhé, majú najviach \(13\) znakov, a majú rovnakú dĺžku ako heslo. O všetkých slovách viete, že sa na všetkých pozíciách líšia od hesla (i-te písmeno slova sa líši od i-teho písmena hesla). Koľko je hesiel, ktoré sa líšia od všetkých slov?

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\), počet slov, o ktorých vieme, že sa líšia od hesla na každej pozícii. Na každom z nasledujúcich \(n\) riadkov sa nachádza jedno slovo. Všetky tieto slová sú rovnako dlhé.

Formát výstupu

Vypíšte jedno číslo - počet možností ktoré ostávajú pre heslo.

Príklad

Input:

3
pes
les
tri

Output:

13248

Možností sú napríklad “aaa”, “aab”, “kon”, “ale”, “nie” …, no nie “eee” či “lod”.

Input:

2
raz
dva

Output:

13824

  1. Miestnosť kde sídli KSP na Matfyze↩︎

Anglická abeceda má \(26\) rôznych písmen. Teda ak by neexistoval žiadny papierik (a poznali by sme dĺžku hesla), tak by sme pre každú pozíciu mali \(26\) možností, aký znak dosadiť. Ak heslo má \(d\) znakov, tak výsledný počet možných hesiel by bol rovný \(26^d\). My ale vieme, že nejaký papierik určite existuje. Potrebujeme teda pre každú pozíciu vylúčiť všetky znaky, ktoré sa nachádzajú na tej pozícii na niektorom papieriku.

Pomalé riešenie

To, čo potrebujeme zistiť ako prvé, je dĺžka nášho hesla. Vezmeme si ľubovoľné slovo na vstupe a zistíme, koľko má znakov. Zo zadania vieme, že rovnako veľa znakov bude mať aj heslo, ktoré hľadáme. Potom si vytvoríme pole \(P\) dĺžky hesla, a na každom indexe bude toto pole obsahovať pole, v ktorom bude všetkých 26 písmen abecedy. Každé takéto pole bude hovoriť o tom, ktoré znaky sme pre danú pozíciu v hesle ešte nevylúčili. Následne budeme prechádzať slová na papierikoch. Pri každom indexe \(i\) v tomto slove, odstránime daný znak v poli \(P[i]\) (ak tam ešte je). Takto prejdem všetky slová, a nakoniec zistíme súčin počtov písmen, ktoré ostali v poliach a tým dostaneme náš výsledný počet hesiel.

Pozrime sa však na časovú zložitosť. Pre každé slovo musíme prejsť celé heslo, a pre každý znak musíme prejsť celé pole s písmenami, ktoré sme ešte nevylúčili (aby sme zistili, či tam to písmenko je), a následne, ak tam je, tak ho musíme vymazať. To pri dĺžke poľa \(w\) môže trvať až \(O(w)\). Ak si teda označíme dĺžku hesla ako \(l\), tak zložitosť je \(O(n l \cdot 26)\) (Áno, \(26\) je síce len konštanta, ale uvedomme si, že ak by v hesle mohli byť aj iné znaky ako malé písmená anglickej abecedy, táto konštanta by prestávala byť zanedbateľná. V prípade, ak ste veľkosť abecedy v poppise nespomínali, tak sme za to body nestrhávali.).

Vzorové riešenie so setom

Pre zlepšenie zložitosti môžeme namiesto polí v poli \(P\) použiť množiny – set (Ak ste ešte o niečom takom nepočuli, tak tento odstavec pokojne preskočte :) ) Rovnako v nich budeme na začiatku ukladať 26 písmen a za každým keď nejaké písmeno pre danú pozíciu vylúčime, vyhodníme ho zo setu na danej pozícii v poli. Takto zlepšíme časovú zložitosť overovania či to písmeno môžeme použiť a zlepšíme zložitosť mazania tohoto písmena (podľa toho, aký set použijeme, tak pri počte prvkov v sete \(p\) to môže byť buď na \(O(\log p)\), alebo \(O(1)\)). Výsledok vypočítame tak isto, teda ako súčin dĺžok setov.

Vzorové riešenie s poľom

Iné riešenie môže byť také, že v poli nebudú sety, ale zase polia, ale s trochu iným významom. Polia budú mať dĺžku \(26\) (1 index pre jedno písmeno abecedy) a na začiatku budú obsahovať samé nuly. Každé pole znova označuje, ktoré písmená sa na danom indexe v hesle môžu/nemôžu nachádzať, a to takým spôsobom, že index \(0\) znamená, že či môžeme použiť písmenko \(a\), index \(1\) písmenko \(b\), a tak ďalej… Znova prejdeme všetky slová a pre každé písmenko v slove si poznačíme do nášho dvojrozmerného poľa, že ho už nemôžme použiť.

Výsledok potom nájdeme tak, že si v každom vnútornom poli spočítame počet núl a vypíšeme súčin týchto počtov núl.

Treba si uvedomiť, že číslo ktoré je výsledkom môže byť dosť veľké. Vzhľadom na obmedzenia vstupov zo zadania, dĺžka hesla môže byť najviac \(13\) znakov, a existuje aspoň \(1\) papierik, takže v najhoršom prípade pre každú pozíciu vylúčime len \(1\) znak. Teda výsledný počet možností bude \(25^{13}\), čo je číslo ktoré sa nezmestí do \(32\) bitovej premennej, ale zmestí sa do \(64\) bitovej.

Časová a pamäťová zložitosť

Musíme prejsť každé slovo na vstupe, pričom počet slov je \(n\), a ich dĺžku si označme \(l\). Pre každý znak slova urobím len konštantné operácie (zápis do poľa na konkrétny index). Pri počítaní výsledku prejdem n polí dĺžky \(26\). Takže výsledná zložitosť bude \(O(nl + 26 n)\), čo je \(O(nl)\). Toľko času spotrebujeme aj na samotné načítanie vstupu, takže môžeme povedať že lepšie sa to ani nedá ;).

Do pamäte si uložím pole \(n\) polí dĺžky \(26\). Teda zaberieme pamäť \(O(26 n) = O(n)\).

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