Zadanie
Odjakživa to tak bolo… V kadiach pred Tesclandom kapre, na cestách čľapkanica, v izbe predčasne vybrakovaný adventný kalendár. V obývačke stromček, na ňom obaly od salóniek, z toho polovica prázdna. Prázdniny sa už nezadržateľne blížia, no Matúš ešte musí dokončiť ten projekt z dejepisu o prínose Etruskov pre Staroveký Rím.
Dejepis je super, ale v tomto predvianočnom čase naň už niet dostatok síl. Na druhej strane, v Tesclande sa momentálne chystá zaujímavá akcia. Každých \(15\) minút, dostanú všetci zákazníci prítomní v predajni vianočnú guľu. Vianočné gule sú dostupné v \(20\) farbách, no zákazník si farbu nevyberá. Našťastie, je dopredu známe, kedy sa budú rozdávať ktoré farby.
Matúš sa tak rozhodol, že nudu plynúcu z písania domácich úloh nahradí niečim užitočnejším a pôjde do Tesclandu nazbierať nejaké gule. Nechce ale ľubovoľné farby… Rád by vyzbieral čo najviac gúľ takých, že ak ich potom všetky zavesí nad svoj písací stôl, postupnosť ich farieb bude rovnaká z ľavej aj z pravej strany.
Samozrejme, nepôjde tam len-tak hocikedy, keďže tie domáce úlohy naozaj musí niekedy dokončiť a nemôže teraz všetko svoj čas stráviť v obchode (aj keď rád by). Chcel by tam stráviť čo najmenej času a nechce tam ísť viac ako raz. Inými slovami, pôjde tam raz, strávi tam určitý čas, počas ktorého dostane nejaké vianočné gule (a žiadnu neodmietne), a potom sa vráti domov.
Matúš tam naozaj chce ísť. Pomôžte mu vopred zistiť, koľko najviac gúľ si domov prinesie, aby neporušil dané pravidlá.
Úloha
Poznáte postupnosť farieb vianočných gúľ v poradí, v akom sa budú rozdávať. 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. (Vianočné gule môžu byť zavesené v inom poradí, v akom boli rozdávané v obchode)
Formát vstupu
Na prvom riadku vstupu sa nachádza \(1 \leq n \leq 300\,000\) udávajúce počet rozdávaní vianočných gúľ v obchode (Pri jednom rozdávaní, získa každý človek v supermarkete vianočnú guľu).
Na druhom riadku vstupu sa nachádza \(n\) farieb gúľ v poradí, v akom budú rozdávané, pričom farba gule je vyjadrená malým písmenom anglickej abecedy od a
po t
.
Formát výstupu
Na výstup vypíšte jedno číslo, dĺžku najdlhšej súvislej podpostupnosti získaných gúľ, ktorej preusporiadaním (alebo aj ponechaním v pôvodnom poradí) môže vzniknuť postupnosť spĺňajúca podmienku o ohromnej estetickosti.
Príklady
Input:
12
aabbccddabcd
Output:
9
Ak bude Matúš v obchode od prvej po deviatu (vrátane) štvrťhodinu, vyzbiera vianočné gule týchto farieb: aabbccdda
. Tieto vieme zavesiť nad písací stôl, napríklad, v takomto poradí: dcbaaabcd
, čo je palindróm, a teda táto súvislá podpostupnosť vianočných gúľ spĺňa Matúšove nekompromisné podmienky. Z pohľadu voľným okom je jasné, že táto podpostupnosť má dĺžku 9 a je najdlhšia možná.
Input:
20
ghjahjghsajdjhlfslja
Output:
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})\).
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ť.