# Pergel

<{ForumPost(poster="Datel", timestamp=2017-06-05 16:36:17)}>
**Zadání:**  
Máme vstupní řetězec délky n. Úkolem je v polynomiálním čase najít jeho minimální pokrytí pomocí palindromů, čili že text rozložíme na co nejméně palindromů.  
Plus z toho také ty palindromy nějak dostat.  
Např:  
    *steponnopets* se dá pokrýt jedním palindromem = sebou samým.  
    *abaaba* se dá rozložit jako: aba,aba = 2palindromy nebo jako abaaba=1palindrom nebo jako a,baab,a=3 palindromy...minimum je teda 1  
Jeden znak je vždy palindrom, takže *abcdefgh* se dá rozložit na 8palindromů délky 1 => horní odhad je n.  
  
Pamět 4GB  
  
**Moje řešení:**  
Nejedená se o optimální řešení.  
Šel jsem na to dynamicky. Nejdříve jsem si vytvořil tabulku P nxn, kde prvek P\[i,j] je true pokud úsek i...j tvoří ve vstupu palindrom.  
Poté jsem navrhnul tuto rekurzi:  
X\[a,b]=#minimální počet palindromů pokrývající úsek a,b  
  
X\[a,b]=1 pokud P\[a,b] true, jinak je to min přes všechny úseky a,k tvořící palindrom(odpovídá true-sloupcům v a-tému řádku v P) z výrazu(1+X\[k+1,b])  
(Ve skutečnosti sem na papíře měl minimum přes všechny palindromy\[k,e] v úseku a,b a sčítání X\[a,k-1] + 1 + X\[e+1,b], ale prý stačí podle prvního, páč stejně beru minimum přes všechny)  
Výsledek je uložen v X\[1,n]  
Čili složitost vyplnění tabulky P je prý n^2 - vzít nějak všechny prostředky a rozvíjet do stran - n*n=n^2. Já sem měl, že to jde určitě v n^3  
Vyplnění tabulky X je n^3 - v každém políčku práce n a máme n^2 políček. (S mojí verzí tedy n^4)  
  
Celkově n^3.(Moje n^4)  
  
Napsal jsem jak vyplňovat tabulku odspoda v pseudokodu, ale že si myslím že rekurze s cache je rychlejší, protože se úsek, který je palindromem nebude rozkládat na menší úseky zbytečně. Čili pro vstup který už je palindrom běží v O(1), zatímco tabulka by běžela v O(n^3) a v posledním kroku při vyplňování X\[1,n] by se nastavila jednička díky P a tabulka se ani nepoužila. Navíc stack při rekurzi je zanedbatelnej vzhledem k velikostí tabulek.  
To, že se z toho ty palindromy mají nějak získat sem zapoměl, ale na ústním se na to ani neptal, takže asi jen bonus. Asi by šlo si v X\[i,j] pamatovat vždy začátek posledního palindromu, protože pak X\[i,zacatek-1] obsahuje začátek předposledního palindromu...  
  
**Lepší řešení:**  
Dozvěděl sem se na ústní, že to jde řešit přes grafy: Vytvoří se stejná tabulka P, která se prohlásí za matici sousednosti. Řešení je pak nejkratší cesta mezi 1 a n. Protože ta odpovídá tomu, že hrana z i do j vede pouze pokud úsek i,j je palindrom a počet palindromů odpovídá počtu hran. Pak na to stačí pustit třeba BFS a složitost je asi teda n^2 když se P dá udělat v n^2 a BFS jde v n^2 s maticí sousednosti. A cesta je hledaný rozklad, která se získá z BFS snadno tím, že si budeme pamatovat vždy odkud sme se tam dostali  
Což mi přijde jako dost elegantní řešení, ale v životě by mě asi nenapadlo.   
  
**Ustní:**  
Dostal sem Holana, byl dost v pohodě, rovnou mi řekl, že písemku nečetl, tak ať mu to celé od začátku popíšu. Algoritmus se mu celkem líbil, vytkl mi jen ty zlepšení, ale asi nešlo o to najít hned nejoptimálnější alg. Fakt ale doporučuji mít vše na tom papíře, protože sem mu to z něho jen četl, ukazoval obrázky a prostě sme o tom povídali...  
  
Jako otázku sem dostal popsat virtuální metody, jak se implementují a včem jsou fajn. Což mě teda dost překvapilo, protože ostatní měli kostry, třídění, stromy..., ale tak za 10minut bylo hotovo.
<{/ForumPost}>

<{ForumPost(poster="TomRiddle", timestamp=2017-06-05 18:52:14)}>
K ústnímu u Pergela:  
Napřed se mě zeptal, jak jsem řešil zkouškovou úlohu (tedy papír pravděpodobně nečetl). Tak jsem mu ji začal vysvětlovat (šel jsem na to přes dynamické programování, složitost jsem měl $O(n^3)$) s tím, že se díval do mé písemky a kontroloval, zda mé vyprávění souhlasí. Po ani ne minutě mě zarazil a oznámil mi, že už na mě názor má. Zadal mi dvě jednoduché úlohy na grafové algoritmy, na pár minut se šel věnovat jiným lidem a pak se ke mně vrátil, podíval se na mé odpovědi, měl rýpavé doplňující dotazy (fungoval by Dijkstra na hledání nejdelší cesty, pokud bychom změnili znaménka ohodnocení hran - ne) a po jejich zodpovězení mi dal známku.   
  
Tedy pokud jdete k Pergelovi, máte dobře písemku (a dovedete to řešení rychle a výstižně popsat) a neuděláte žádnou blbost v teorii, tak vás celkem bez boje nechá jít domů s jedničkou.  
Pokud máte špatnou písemku, ale jsou v ní náznaky správných myšlenek, tak vás nechá zabojovat o trojku.   
Pokud ale nemáte optimálně písemku a uděláte nějakou fatální chybu v teorii (např. si spletete dva algoritmy a neuvědomíte si to dostatečně rychle), tak vás spíš projít nenechá.  
P.S.: Nutno dotat, že se Pergel zdál v dost dobré náladě.
<{/ForumPost}>

<{ForumPost(poster="Speedding", timestamp=2017-06-05 22:16:31)}>
S hodnocením Pergela musím souhlasit, minulý týden to u něj probíhalo naprosto stejně.
<{/ForumPost}>

<{ForumPost(poster="kruchi", timestamp=2023-05-29 20:21:43)}>
29. 5. 2023 - Velmi podobné zadání, ale máme 1000 souborů, každý s 5000 znaky, a vypsat pouze 5 názvů souborů s nejmenším počtem palindromů pro pokrytí. Také byl specifikován čas na maximálně týden a dostali jsme 8-jádrový procesor.
<{/ForumPost}>