4. Ohromná estetickosť vzorové riešenie

12
aabbccddabcd

9

20
ghjahjghsajdjhlfslja

7

V prvom rade si uvedomme, čo je našou úlohou.

Zistite, koľko najviac si ich Matúš môže priniesť domov, ak chce v obchode stráviť iba jeden súvislý časový úsek a chce, aby množina týchto gúľ spĺňala zaujímavú ohromne estetickú podmienku: Všetky získané gule musí byť možné zavesiť vedľa seba tak, aby vzniknutá postupnosť ich farieb bola rovnaká z ľavej aj z pravej strany.

V preklade toto znamená, že chceme nájsť najdlhší súvislý podreťazec, z ktorého vieme spraviť palindróm. Spraviť palindróm znamená, že môžeme meniť poradie písmen v tomto podreťazci tak, aby výsledný reťazec bol palindróm.

Čo vieme o palidróme?

Palindróm je reťazec, ktorý je rovnaký z jednej aj z druhej strany. Existuje v ňom teda nejaký stred, od ktorého sa vľavo a vpravo nachádzajú rovnaké znaky v rovnakom poradí.

Keďže všetky znaky, nachádzajúce sa vľavo od stredu, sa nachádzajú aj vpravo od stredu, vieme, že sa v palindróme každý znak, nachádzajúci v jednej polovici, nachádza celkovo dvakrát.

Samozrejme, to platí, ak má palindróm párnu dĺžku a jeho stred je tak presne medzi dvoma písmenami. Ak má palindróm nepárny počet znakov, jeden znak je presne v strede. Tento stredný znak sa nenachádza vľavo ani vpravo od stredu, preto nemá svoju “dvojičku” v druhej polovici palindrómu a je nám jasné, že sa v palindróme nachádza práve raz.

Z takejto úvahy sa dozvedáme, že v palindróme párnej dĺžky sa musí každý znak vyskytovať párny-počet-krát a v palindróme nepárnej dĺžky sa musia všetky znaky okrem práve jedného vyskytovať párny-počet-krát.

Zjednodušene: V palindróme sa musí žiadny alebo jeden znak vyskytovať párny-počet-krát.

Všetky podreťazce

Okay. Chceme asi zistiť početnosti znakov v jednotlivých podreťazcoch vstupného reťazca gúľ a nájsť taký najdlhší podreťazec, že žiadny alebo práve jeden znak má v ňom nepárnu početnosť.

Ak má reťazec dĺžku \(n\), existuje \(\frac{(n+1)\cdot n}{2}\) jeho podreťazcov (1 dlžky \(n\), 2 dĺžky \(n-1\), 3 dĺžky \(n-2\), \(n\) dĺžky 1), čo je asymptoticky \(n^2\). Ak by sme pre chceli každý jeden podreťazec rátať početnosti jeho znakov osobitne, museli by sme spracovať vštky znaky vo všetkých podreťazcoch. Počet znakov vo všetkých podreťazcoch je asymptoticky \(n^3\).

Okrem toho by sme pre každý podreťazec museli skontrolovať \(k\) početností znakov, aby sme zistili, či spĺňa podmienky. \(k\) je veľkosť abecedy, no v zadaní sme sa dozvedeli, že je to najviac 20, preto môžeme toto číslo brať ako konštantu. Z toho vidíme časovú zložitosť \(\mathcal{O}(n^3)\).

Niečo lepšie

Predchádzajúce riešenie vieme značne vylepšiť jednoduchou myšlienkou. Nepotrebujeme pre každý jeden podreťazec rátať početnosť odznova, vieme využiť informáciu z o jedno menšieho podreťazca.

Ak nebudeme rátať početnosti znakov v každom podreťazci osobitne, ale využijeme to, že početnosť v reťazci o dĺžke \(x\) sa len pre jeden znak líši od početnosti jeho podreťazca o dĺžke \(x-1\). To znamená, že počas výpočtu početností pre nejaký podreťazec so znakmi \(C_i\) až \(C_j\) sme už vyrátali aj početnosti pre podreťazce so znakmi \(C_i\rightarrow C_{i+1}, C_i\rightarrow C_{i+2},\dots C_i\rightarrow C_{j-1}\). To znamená, že nám vlastne stačí spracovať len \(n\) podreťazcov (\(C_0\rightarrow C_n, C_1\rightarrow C_n,\dots C_n\rightarrow C_n\)). Priemerná dĺžka týchto podreťazcov je \(\frac{n}{2}\) znakov.

Vidíme, že takýmto prístupom nám časová zložitosť klesne na \(\mathcal{O}(n^2)\). Pamäťová zložitosť je tu \(\mathcal{O}(n)\). Potrebujeme si pamätať len celý vstupný reťazec.

Zjednodušenie a prefixy

Položme si otázku: Naozaj potrebujeme vedieť konkrétne početnosti znakov? HmPovedal by som, že nás aj tak vo výsledku zaujímajú iba parity týchto početností (či sú párne alebo nepárne). To by ale predchádzajúce riešenie aj tak nezlepšilo, aj tak by sme museli spracovať \(n\) podreťazcov.

Navyše, prečo musíme spracovať osobitne \(n\) podreťazcov? Teraz si uvedomme, ak máme informácie o paritách v podreťazcoch \(C_i\rightarrow C_j\) a \(C_i\rightarrow C_k\) pre \(j < k\), vieme z toho zistiť aj paritu podreťazcu \(C_j\rightarrow C_k\). V podstate prefixové súčty.

Ak je medzi indexami \(i\) a \(j\) početnosť nejakého písmena \(a_{ij}\) a medzi indexami \(i\) a \(k\) \(a_{ik}\), početnosť mezi indexami \(j\) a \(k\) je potom \(a_{jk} = a_{ik} - a_{ij}\). To isté platí aj pre paritu tejto početnosti. Ak, napríklad, \(a_{ij} = parne\) a \(a_{ij} = neparne\), tak \(a_{jk} = neparne\).

Zo spracúvania \(n\) podreťazcov, začínajúcich na indexoch \(0\dots n-1\), sa dostávame k tomu, že nám stačí spracovať celý reťazec len raz. Počas jeho spracúvania, spracúvame postupne všetky podreťazce začínajpce na indexe 0. V predchádzajúcom odesku sme si ukázali, že ak poznáme parity reťazcov, začínajúcich na rovnakom indexe, poznáme aj parity medzi ich koncami. Ak poznáme parity všetkých podreťazcov, začínajúcich na indexe 0, poznáme aj parity všetkých podreťazcov medzi všetkými ich koncami, čo sú vlastne všetky podreťazce celého reťazcu. Čo s nimi?

Xor a zapamätanie najľavejšej

\(a_{jk} = neparne\), ak \(a_{ij} \neq a_{ij}\). To vyzerá ako xor.

V zadaní sa spomína, že v reťazci je najviac \(20\) rôznych znakov. Každý z týchto 20 znakov môže mať párnu alebo nepárnu paritu. To je dokopy \(2^{20}\) kombinácií parít jednotlivých znakov.

HmInformáciu o parite nejakého podreťazcu si môžeme reprezentovať, napríklad, nejakým binárnym číslom s 20 bitmi. Ak máme dva takéto podreťazce, začínajúce na rovnakom indexe, xorom ich parít dostaneme paritu podreťazcu medzi ich koncami.

Ku každej parite existuje 20 takých, ktoré sa líšia práve v jednom znaku. Ak spracúvame vstupný reťazec z ľava do prava a sme na nejakom i-tom znaku reťazca, zaujíma nás, či a kde vľavo od neho sa nachádza znak, na ktorom sa parita nelíši od aktuálnej alebo sa líši v práve jednom znaku. To znamená, že podreťazec medzi nimi má vyhovujúcu paritu (0 alebo 1 nepárnych).

Dokonca, môžeme povedať, že má zmysel hľadať len tú najľavejšiu z takých parít. Hľadáme najdlhší podreťazec, preto pre nás nemá zmysel nie-najľavejšia parita, pretože tá by určite nepatrila najdlhšiemu takému podreťazcu, ak by existovala nejaká ľavejšia, čiže vzdialenejšia od aktuálne spracúvaného znaku.

Zhrnutie vzorového riešenia

Pamätáme si pre každú paritu, kde najskôr sa v reťazci vyskytuje. Pre každý aktuálne spracúvaný index reťazcu si nájdeme najľavejšiu vyhovujúcu paritu (ak existuje), lebo tá začína najdlhší podreťazec končiaci v aktuálnom znaku. Keď takto spracujeme celý reťazec, je nám známa dĺžka najdlhšieho podreťazcu, z ktorého je možné vytvoriť palindróm.

Časová zložitosť. Pre každý znak v reťazci potrbujeme len nájsť najľavejší s vyhovujúcou paritou, ktorých je \(k+1\). To nám dáva krásne \(\mathcal{O}(n\cdot k)\), kde \(n\) je dĺžka reťazcu a \(k\) je počet farieb. Ak si ale povieme, že 20 (najviac farieb) je konštanta, ostane nám \(\mathcal{O}(n)\).

S pamäťou je to tu trošičku smutnejšie. Okrem vstupu si ešte potrebujeme pamätať najľavejšiu pozíciu pre každú možnú paritu. Tých je až \(2^{20}\), takže pamäťová zložitosť nám tu vychádza na \(\mathcal{O}(n + 2^{20})\).