5.6.2017 Holan/Pergel

[Datel]

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.

[TomRiddle]

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³)) 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ě.

[Speedding]

S hodnocením Pergela musím souhlasit, minulý týden to u něj probíhalo naprosto stejně.

[kruchi]

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.