od Datel » 5. 6. 2017 16:36
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.
[b]Zadání:[/b]
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ř:
[i]steponnopets[/i] se dá pokrýt jedním palindromem = sebou samým.
[i]abaaba[/i] 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 [i]abcdefgh[/i] se dá rozložit na 8palindromů délky 1 => horní odhad je n.
Pamět 4GB
[b]Moje řešení:[/b]
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...
[b]Lepší řešení:[/b]
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.
[b]Ustní:[/b]
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.