Zadanie

Vzrušujúce noviny! V auguste sa bude konať veľkolepá lingvistická konferencia v Memphis v Tennessee. A pozvaní sú všetci! Budú aj prednášky. Prednášku bude mať napríklad Viktor. O čom? Isto ste počuli o významných objavoch nekrolingvistky Kristíny. Minulé kolo sa jej podarilo ukázať, že isté prastaré atlantídske zvitky sú z neznámych socio-kultúrnych dôvodov napísané tak, aby obsahovali palindrómy1… Ale čo to môže znamenať? Odkiaľ pramení táto atlantídska fascinácia palindrómami? Viktor si myslí, že zistil odpoveď. Na jednom zvitku totiž našiel niečo takéto:

Pokiaľ sa Viktor nemýli, jedná sa o historicky vôbec prvé vyobrazenie obrovskej kozmickej ploštice (pohľad zvrchu). Určite sa pýtate “?”. Všetko pochopíte, až budete starší, približne presne o pár sekúnd. Predstavte si, že ste atlantíďan. Keď za vami takáto kozmická ploštica príde, naskytne sa vám približne nasledovný pohľad (kozmická ploštica spredu - be not afraid):

Ale čo! Vidíte to aj vy? Táto kozmická ploštica vyzerá úplne ako palindróm (os súmernosti je vyznačená)!!! Viktor verí, že prví atlantíďania nadizajnovali svoje písmo podľa ploštičej tváre, a aj potom, čo kozmické ploštice vymreli2, sa moderný skript snaží túto spomienku zachovať už spomínaným spôsobom písania3.

Ale čo s týmto zistením? Samozrejme, treba zrekonštruovať, ako mohli kozmické ploštice naozaj vyzerať! Vpred-smerujúca kozmická ploštica na obrázku vyššie je totiž iba estimácia. Naviac, každá kozmická ploštica je unikátna.

Vieme, že prvé atlantídske vety vznikli z ploštičej tváre, ktorú atlantíďania rozdelili na jednotlivé slovíčka. Teda rekonštrukcia je jednoduchá: vezmeme slovíčka, ktoré poznáme, a vyskladáme z nich našu predstavu ploštičej tváre…

Úloha

Na vstupe dostanete niekoľko reťazcov pozostávajúcich z malých písmen anglickej abecedy. Vašou úlohou je na výstup vypísať ľubovoľný palindróm, ktorý vie vzniknúť tak, že niektoré zo vstupných reťazcov v nejakom poradí zapíšeme priamo za seba (môžu sa aj opakovať, a nemusíte použiť všetky), prípadne zistiť, že sa to nedá.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet slov, ktoré poznáme.

Na každom z \(n\) nasledovných riadkov je jedno slovo – reťazec dĺžky \(d_i\) (\(1 \leq d_i \leq 10\)) pozostávajúci z malých písmen anglickej abecedy. Navyše platí, že žiadne slovo nie je prefixom ani suffixom iného, teda zo žiadneho slova nevieme dostať žiadne iné iba tak, že na jeho začiatok alebo koniec pridáme nejaké znaky.

Počty slov sú v jednotlivých sadách nasledovné:

Sada 1 2 3 4
\(1 \leq n \leq\) \(10\) \(1\,000\) \(30\,000\) \(40\,000\)

Formát výstupu

Na jedinom riadku výstupu vypíšte palindróm pozostávajúci z malých písmen anglickej abecedy, ktorý sa dá zo vstupných slov vyskladať. Ak ich existuje viac, vypíšte ľubovoľný z nich. Ak neexistuje žiaden, vypíšte -1.

Príklady

Input:

5
jelenovi
ani
sobovi
nelej
pivo

Output:

jelenovipivonelej

Input:

3
takyto
palindrom
neexistuje

Output:

-1

Input:

2
aktivi
tka

Output:

aktivitka

  1. palindróm je taký reťazec, že odzadu sa číta rovnako ako odpredu, teda napríklad “aktivitka”. Vedúci KSP palindrómy zbožňujú a majú ich každé raňajky.↩︎

  2. momentálne asi vedeckou komunitou najuznávanejšia teória je, že kozmické ploštice nezmizli, len sa vplyvom gravitácie z plochého tvaru zaguľatili a do dnešného dňa prežívajú v podobe basketbalových lôpt.↩︎

  3. azda atlantíďania verili, že kozmické ploštice sa ku nim vrátia, pokiaľ sa text bude opäť na ich podobizeň podobať?↩︎

Základná myšlienka riešenia

Najprv si predstavme, že jednoducho skladáme reťazec zo zadaných podreťazcov (nazvime ich “kúsky”). Ako to môžeme robiť? Aké máme kedy možnosti, ako v ktorom momente pokračovať? Na začiatku si vieme zvoliť ľubovoľný znak, ktorým nejaký kúsok začína. Potom ľubovoľný znak, ktorým niektorý z takto začínajúcich kúskov pokračuje. Až dosiahneme bod, keď sme napísali nejaký celý kúsok, vieme určite, že ďalšie znaky do toho istého kúsku patriť nemôžu, keďže by sme vyskladali nejaký kúsok, ktorého prefixom je ten kúsok, ktorý sme teraz dokončili…

Ukážka: skladajme od začiatku reťazec z kúskov “ahoj” “aha” a “hanoj”. Najprv môžeme začať znakom “a” alebo “h”. Zvoľme si “a”. Pokračujeme určite znakom “h”, teda teraz máme zatiaľ reťazec “ah”. Tretím písmenom môže byť “o” alebo “a”. Ak si zvolíme “a”, vyskladáme hotový reťazec “aha”. Vieme, že toto je koniec tohto kúsku, pretože žiaden iný kúsok nemôže začínať prefixom “aha”. Teda pokračujeme od začiatku: znova si môžeme vybrať “a” alebo “h”. A tak ďalej…

Reprezentácia slovníka

Štruktúra, ktorá nám môže pomôcť pamätať si aké písmenká sme zatiaľ v budovanom kúsku použili, je napríklad trie: strom, ktorého koreň označuje prázdny kúsok (buď keď sme na začiatku skladania alebo keď sme práve dokončili kúsok pred tým). Každý ďalší vrchol v trie označuje reťazec v jeho rodičovi, ku ktorému je na koniec pridaný jeden znak. V trie sú všetky reťazce, ktoré sú prefixom nejakého povoleného kúsku. Teda, keď chceme budovať nejaký reťazec z kúskov, vieme sa jednoducho pohybovať po trie vždy do dieťaťa aktuálneho vrcholu a z listov (dokončených kúskov) sa vrátiť do koreňa.

Skladanie palindrómu

Dobre, čo teraz? Chceme, aby náš reťazec bol nielen vyskladaný z kúskov, ale aj aby bol palindrómom. Prípadne zistiť, že neexistuje. Skladajme reťazec nielen od začiatku, ale aj od konca zároveň. Spravíme dve trie - jedno pre všetky povolené kúsky odpredu a jedno pre povolené kúsky odzadu.

Ako vyzerá skladanie palindrómu? V oboch trie začneme od koreňa - na začiatku ani na konci ešte žiaden znak nie je. Následne vieme pridať na začiatok aj koniec ten istý znak. Teda musí to byť nejaký taký, ktorý vieme v oboch trie pridať - teda oba momentálne vrcholy v nich majú dieťa, kde je pridaný ten istý znak. Keď v nejakom trie narazíme na koniec, vrátime sa hneď do koreňa.

Kedy skončiť

Kedy sme palindróm doskladali? Ako spoznáme, že môžeme začiatok aj koniec palindrómu, ktorý skladáme, spojiť do celku, ktorý bude tiež pozostávať z povolených kúskov? Spravíme trik: budeme hľadať iba palindrómy párnej dĺžky, v ktorých žiadne kúsky neprechádzajú stredom. Teda prvá aj druhá polovica sú samé osebe vyskladané z kúskov. Určite, ak existuje akékoľvek riešenie, existuje aj takéto - jednoducho, akékoľvek riešenie napíšeme dvakrát za seba. Stále bude palindrómom a prvá aj druhá polovica budú vyskladané z kúskov samé osebe. Takéto riešenia sa budú hľadať omnoho jednoduchšie - ak sa vrátime do situácie, že v oboch trie sme v koreni, našli sme ho. Totiž náš budovaný prefix aj suffix sú v tomto momente uzatvorené, a teda ich vieme proste nalepiť za seba a dostať riešenie.

Vyhodnotenie

Už nám teda ostáva len premyslieť si, ako zistiť, či sa takto dá vyskladať riešenie alebo nie. Teda máme niekoľko stavov, každý je popísaný dvojicou vrcholov v oboch trie a chceme zistiť, či sa zo stavu koreň-koreň dá do seba vrátiť. V podstate nám stačí DFS algoritmus zbehnutý na dvojiciach týchto vrcholov. V dvojrozmernom poli si zapamätáme pre každú dvojicu, či sme ju už navštívili. Ak nájdeme spôsob, ako sa tam vrátiť, teda riešenie existuje, tak konkrétne riešenie nájdeme, ak si pre každú dvojicu zapamätáme, z ktorej sme sa na ňu dostali a takto odzadu celú cestu zrekonštruujeme.

Zložitosť

Aké sú zložitosti našeho programu? Jeho časová zložitosť je \(O(n^2)\), pretože na začiatku spravíme obe trie - na to musíme prejsť \(n\) slov konštantnej dĺžky a každé z nich vložiť do trie odpredu a odzadu. To trvá len \(O(n)\). Potom zbehneme DFS na dvojiciach vrcholov týchto trie. Každé trie má najviac \(O(n)\) vrcholov, teda dvojíc je \(O(n^2)\) a to je aj zložitosť tohoto DFS. Jeho pamäťová zložitosť je \(O(n^2)\), pretože si pamätáme okrem dvoch trie veľkosti \(O(n)\) ešte dvojrozmerné pole veľkosti \(O(n^2)\).

from string import ascii_lowercase

size = len(ascii_lowercase)


class Node:
    def __init__(self):
        self.children = {}

    def existing_children(self):
        return set(self.children.keys())


def add_word(word: str, root: Node):
    v = root
    for c in word:
        if c not in v.children:
            v.children[c] = Node()
        v = v.children[c]


n = int(input())
words = [input() for _ in range(n)]

prefix = Node()
suffix = Node()

for word in words:
    add_word(word, prefix)
    add_word(word[::-1], suffix)

q = [(prefix, suffix, "")]

while q:
    p, s, w = q.pop(0)

    p_child = p.existing_children()
    if len(p_child) == 0:
        p = prefix
        p_child = p.existing_children()

    s_child = s.existing_children()
    if len(s_child) == 0:
        s = suffix
        s_child = s.existing_children()
    
    if p == prefix and s == suffix and w != "":
        print(w+w[::-1])
        exit(0)

    child = p_child.intersection(s_child)
    for i in child:
        q.append((p.children[i], s.children[i], w+i))

print(-1)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct trie_node{
    trie_node* parent;
    trie_node* children[26];
    int depth;
    bool end;
    int id;
};

trie_node* new_node(trie_node* parent, int letter, int id){
    trie_node* o = new trie_node;
    if(parent != NULL){
        parent->children[letter] = o;
        o->depth = parent->depth + 1;
    }else{
        o->depth = 0;
    }
    o->id = id;
    o->parent = parent;
    o->end = false;
    for(int i = 0; i < 26; i++){
        o->children[i] = NULL;
    }
    return o;
}

int save_word(trie_node* where, string s, bool reverse, int offset, int ids){
    if(offset == s.length()){
        where->end = true;
        return ids-1;
    }
    int l;
    if(reverse){
        l = s[s.length()-1-offset]-'a';
    }else{
        l = s[offset]-'a';
    }
    if(where->children[l] == NULL){
        trie_node* o = new_node(where,l,ids);
        ids++;
        ids = save_word(o,s,reverse,offset+1,ids);
    }else{
        ids = save_word(where->children[l],s,reverse,offset+1,ids);
    }
    return ids;
}

trie_node* find_node(trie_node* where,string s,int offset){
    if(offset == s.length()){
        return where;
    }
    
    return find_node(where->children[s[offset]-'a'],s,offset+1);
    
}

char vyries(trie_node* pre,trie_node* post,vector<char>& result,bool** visited,char** goal,trie_node* posl,trie_node* posr,bool ignore = false){
    
    if(posl->end){
        posl = pre;
    }
    if(posr->end){
        posr = post;
    }
    
    if(!ignore){
        if(visited[posl->id][posr->id]){
            return 'X';
        }
        visited[posl->id][posr->id] = true;
        
        if(goal[posl->id][posr->id] != 'X'){
            return goal[posl->id][posr->id];
        }
    }
    
    
    
    for(char i = 'a'; i <= 'z'; i++){
        if(posl->children[i-'a']==NULL or posr->children[i-'a']==NULL){
            continue;
        }
        result.push_back(i);
        char o = vyries(pre,post,result,visited,goal,posl->children[i-'a'],posr->children[i-'a']);
        if(o != 'X'){
            return o;
        }
        result.pop_back();
    }
    
    return 'X';
    
}

int main(){
    int n;
    cin >> n;
    string words[n];
    for(int i = 0; i < n; i++){
        cin >> words[i];
    }
    
    trie_node *preroot,*postroot;
    preroot = new_node(NULL,0,0);
    postroot = new_node(NULL,0,0);
    preroot->id = 0;
    postroot->id = 0;
    int n1 = 1;
    int n2 = 1;
    
    for(int i = 0; i < n; i++){
        string word = words[i];
        
        n1 = save_word(preroot,word,false,0,n1);
        n2 = save_word(postroot,word,true,0,n2);
    }
    
    bool* visited[n1];
    char* goal[n1];
    for(int i = 0; i < n1; i++){
        visited[i] = new bool[n2];
        goal[i] = new char[n2];
        for(int j = 0; j < n2; j++){
            visited[i][j] = false;
            goal[i][j] = 'X';
        }
    }
    goal[0][0] = 'O';
    
    for(int i = 0; i < n; i++){
        string word = words[i];
        trie_node *left,*right;
        left = find_node(preroot,word,0);
        right = postroot;
        for(int j = word.length()-1; j >= 0; j--){
            left = left->parent;
            goal[left->id][right->id] = word[j];
            right = right->children[word[j]-'a'];
            if(j == 0){
                break;
            }
            goal[left->id][right->id] = 'O';
        }
    }
    
    
    vector<char> result;
    char o = vyries(preroot,postroot,result,visited,goal,preroot,postroot,true);
    
    if(o == 'X'){
        cout << -1;
    }else{
        for(int i = 0; i < result.size(); i++){
            cout << result[i];
        }
        if(o != 'O'){
            cout << o;
        }
        for(int i = result.size()-1; i >= 0; i--){
            cout << result[i];
        }
    }
    cout << endl;
    
    for(int i = 0; i < n1; i++){
        delete visited[i];
        delete goal[i];
    }
    
}

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