Vlastnosti palindrómov

Pozrime sa najprv na vlastnosti palindomov párnej dĺžky. Vieme, že vlastnosť všetkých palidrómov je, že sa čitajú rovnako odpredu ako odzadu. Môžeme si teda všimnúť, že ak palindróm rozdelíme presne v polovici (toto vieme urobiť, lebo pracujeme s palindrómom párnej dĺžky) a druhú polovicu obrátime, tak táto obrátená druhá polovica bude zhodná s prvou polovicou palindrómu. Teda ak sa nejaký znak nachádza v prvej polovici palindrómu, tak sa určite nachádza aj v druhej polovici a platí, že počet výskytov tohto znaku v prvej polovici palidrómu je zhodný s počtom výskytov tohto znaku v druhej polovici palidrómu. Z toho vyplýva, že počet výskytov každého znaku v celom palindróme musí byť párny pri palindrómoch párnej dĺžky.

Palindrómy nepárnej dĺžky si vieme predstaviť ako palindrómy párnej dĺžky s pridaným znakom v strede, medzi polovicami. Keďže tento pridaný znak je v strede, teda je pri čítaní z oboch smerov na rovnakom mieste, tak nepotrebuje ďalší znak ktorý by s ním tvoril dvojicu. Preto bude mať pri nepárnom palindróme práve jeden znak nepárny počet výskytov.

Teda pre vetu na vstupe musí platiť nasledovná podmienka, aby sa dala naformátovať do podoby palindrómu - medzi počtami výskytov jednotlivých znakov v celom palindróme môže byť najviac jeden znak s nepárnym počtom výskytov.

Ako zostaviť palindróm?

Teraz už vieme či sa palindróm dá alebo nedá vytvoriť a dostávame sa k druhému problému. Ako ho vytvoriť?

Predpokladajme, že už sme zistili koľko krát máme ktorý znak k dispozícii.

Začnime tým, že si vytvoríme prvú polovicu palindrómu. Vieme, že každý znak sa v tejto prvej polovici vyskytuje polovične veľa krát ako je celkový počet jeho výskytov v palindróme (ak je počet výskytov znaku v celom palindróme nepárny počet, tak ho zatiaľ budeme považovať za o jedna menší, párny počet). Čiže každý znak dáme do prvej polovice $n/2$ krát ($n$ označuje koľko krát je daný znak v celom palindróme).

Druhú polovicu teraz vieme vytvoriť veľmi ľahko a to obrátením prvej polovice.

Nesmieme však zabudnúť, že pri palindrómoch nepárnej dĺžky nám ešte ostal jedn znak s nepárnym počtom výskytov v celom palindróme a umiestnime ho do stredu medzi polovice.

Týmto sme úspešne vytvorili palindróm z množiny znakov.

Implementácia

Našu implementáciu začneme s načítaním vstupu a vytvorením cyklu pre $T$ viet.

T = int(input())
for i in range(T):
    N = int(input())
    veta = input()
    ...

Najprv si potrebujeme pre každý znak vo vete spočítať, koľko krát sa v nej nachádza. Na to vieme v Pythone použiť štruktúru dict (aleternatívne map alebo unordered_map C++). Pre každý znak sa pozrieme či už je v štruktúre a ak nie, pridáme ho s hodnotou $0$. Potom zvýšime zapamätaný počet tohto znaku o 1.

znaky = {}

for z in veta:
    if z not in znaky:
        znaky[z] = 0
    znaky[z] += 1

Teraz si chceme overiť či sa viac ako jeden znak vyskytuje vo vete nepárne veľa krát. Túto časť vieme využiť aj na to aby sme si rovno zapamätali ktorý znak sa vyskytuje nepárne veľa krát.

neparny = ""
for z in znaky:
    if znaky[z] % 2 == 1:
        if neparny != "":
            # Toto je druhy neparny pocet, palindrom sa neda spravit
            # Skoncime cyklus a zapamatame si chybu
            neparny = "CHYBA"
            break
        neparny = z
if neparny == "CHYBA":
    # Nasli sme aspon dva neparne pocty, vypiseme chybu
    print("CHYBA")
else:
    # Pokracujeme, staviame palindrom
    ...

Teraz už nám zostáva iba vytvoriť palindróm. Začneme vytváraním prvej polovice. Asi najintuitívnejší spôsob naprogramovania tejto časti vyzerá takto:

polka = ""
for z in znaky:
    for j in range(znaky[z]):
        polka += z

Môže sa zdať, že časová zložitosť tohto je $O(n)$, ale kvôli tomu ako funguje Python je skutočná časová zložitosť až $O(n^2)$¹. Túto zvláštnosť vieme obísť tým, že si najprv tieto znaky uložíme do zoznamu a tento zoznam potom spojíme do jedného textu. Obe tieto operácie vieme robiť v lineárnom čase.

polka = []
for z in znaky:
    # Toto je skrateny zapis, aby sme sa vyhli dalsiemu cyklu
    polka.append(z * (znaky[z] // 2))
# Prekonvertujeme zoznam znakov do textu
polka = "".join(polka)

Zostáva nám spojiť polky dokopy, prípadne medzi ne pridať znak, ktorého bolo nepárne veľa. Tento znak už buď máme v neparny a chceme ho pridať, alebo je neparny prázdny a môžme ho pridať medzi polky, nakoľko to nič neurobí.

polka = []
for z in znaky:
    # Toto je skrateny zapis, aby sme sa vyhli dalsiemu cyklu
    polka.append(z * (znaky[z] // 2))
# Prekonvertujeme zoznam znakov do textu
polka = "".join(polka)

Tým sme implementovali kompletné riešenie, ktoré vyzerá takto:

T = int(input())
for i in range(T):
    N = int(input())
    veta = input()

    znaky = {}

    for z in veta:
        if z not in znaky:
            znaky[z] = 0
        znaky[z] += 1

    neparny = ""
    for z in znaky:
        if znaky[z] % 2 == 1:
            if neparny != "":
                neparny = "CHYBA"
                break
            neparny = z
    if neparny == "CHYBA":
        print("CHYBA")
    else:
        polka = []
        for z in znaky:
            polka.append(z * (znaky[z] // 2))
        polka = "".join(polka)

        print(polka + neparny + polka[::-1])

Časová zložitosť tohto riešenia je v závislosti od toho, či použijeme pre ukladanie počtu znakov usporiadanu alebo neusporiadanu množinu $O(n \cdot \log_2{n})$ alebo $O(n)$. Pri usporiadanej množine vieme použiť argument, že hodnota v logaritme nikdy nepresiahne 26, čiže celý logaritmus nepresiahne hodnotu 5. Kvôli tomu sa z neho stáva efektívne konštanta a teda časová zložitosť optimálneho riešenia tejto úlohy je $O(n)$.

Optimalizácie

Tieto optimalizácie neboli potrebné na získanie plného počtu bodov, ale dá sa nimi program urýchliť až 2.6 násobne. Ide o tzv. neasymptotické optimalizácie čo znamená, že nezlepšujú časovú zložitosť ale aj tak zrýchľujú náš program.

Základná optimalizácia

Tým, že dopredu poznáme všetky znaky ktoré sa môžu v palindróme nachádzať, vieme si premennú znaky dopredu vyplniť nulami pre všetky možné znaky. Keby ich mohli byť rádovo milióny, túto operáciou by sme si nemohli dovoliť (prekročili by sme limit použitej pamäte), ale my vieme, že máme na výber iba 26 znakov.

Spôsobov ako presne to urobiť je veľa, ten ktorý použijeme tu je založený na ASCII kódoch znakov malej anglickej abecedy, ktoré začínajú s 97 pre a a končia s 122 pre z.

znaky = {chr(z): 0 for z in range(97, 123)}

Vďaka tomuto sa vieme zbaviť týchto riadkov, ktoré nás program silne spomaľovali:

if z not in znaky:
    znaky[z] = 0

Pred touto optimalizáciou sme s premennou znaky robili pre každý znak dve operácie: 1. Overili sme či sa znak v premennej už nachádza – z not in znaky 2. Zvýšili sme hodnotu pre znak o 1 – znaky[z] += 1

Riadok znaky[z] = 0 naś nemusí trápiť, lebo sa vykoná pre každý znak maximálne raz a v podstate sme tieto vykonania iba zjednotili do jedného riadku na začiatku.

Po tejto optimalizácii nám zostala už iba jedna z týchto operácií, čiže túto časť programu sme zrýchlili približne 2-krát. Nejde však o jedinú časť našeho programu, preto sa celková rýchlosť zvýši iba asi 1.3-krát.

Lepšia optimalizácia

Ďalšia vec ktorou si vieme pomôcť je vykašlať sa na dict a použiť štruktúru dizajnovanú práve na náš účel. V Pythonovej knižnici collections existuje štruktúra Counter, ktorá ráta počty prvkov čohokoľvek čo jej dáme.

Vďaka tomuto nám stačí naradiť celé vytváranie premennej znaky jedným riadkom. Nesmieme však zabudnúť túto knižnicu importovať.

from collections import Counter

znaky = Counter(veta)

Oproti prvému programu je tento asi 2.6-krát rýchlejší.

from collections import Counter

T = int(input())
for i in range(T):
    N = int(input())
    veta = input()

    znaky = Counter(veta)

    neparny = ""
    for z in znaky:
        if znaky[z] % 2 == 1:
            if neparny != "":
                neparny = "CHYBA"
                break
            neparny = z
    if neparny == "CHYBA":
        print("CHYBA")
    else:
        polka = []
        for z in znaky:
            polka.append(z * (znaky[z] // 2))
        polka = "".join(polka)

        print(polka + neparny + polka[::-1])

Divná Pythonovská optimalizácia

Úplne nakoniec sa oplatí spomenúť ešte jednu, celkom divnú a neintuitívnu optimalizáciu. Ak dáme celý hlavný program do funkcie a potom spustíme túto funkciu, náš program bude bežať o dosť rýchlejšie^[[https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function]].

Na programy s rôznym stupňom optimalizácií to má veľmi rôzny efekt^[Ak by ste chceli vedieť detailnejšie prečo, kľudne mi napíšte na [email protected] a rád vám to vysvetlím.]: - Program bez optimalizácií – 1.7x zrýchlenie - Program s predvyplnením premennej znaky – 1.5x zrýchlenie - Program s použitím Counter – žiadne zrýchlenie

C++ program

Tu už nebudeme popisovať kompletný implementačný postup, nakoľko je rovnaký ako pri Pythone. Správne riešenie v C++ mohlo vyzerať takto:

#include <bits/stdc++.h>

using namespace std;

void run() {
    int n;
    cin >> n;

    unordered_map<char, int> znaky;
    // predvyplnime s nulami, nie je vyzadovane ale trochu to zrychli program
    for(char z = 'a'; z <= 'z'; z++) znaky[z] = 0;

    for(int i=0; i<n; i++) {
        char a;
        cin >> a;
        znaky[a]++;
    }

    char odd = 0;
    for(auto z : znaky) {
        if(z.second % 2 == 1) {
            if(odd != 0) {
                cout << "CHYBA\n";
                return;
            }
            odd = z.first;
        }
    }

    vector<char> polovica(n/2);
    int j = 0;
    for(auto z : znaky) {
        for(int i=0; i<z.second/2; i++) {
            cout << z.first;
            polovica[j] = z.first;
            j++;
        }
    }
    if(odd != 0) cout << odd;
    for(int i = polovica.size()-1; i >= 0; i--) cout << polovica[i];
    cout << '\n';
}

int main() {
    int t;
    cin >> t;
    while(t--) run();
}