English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [ZBI] Rozwiązanie
Ktoś coś? Ja mam dynamik w O(n^2 log n), i miałem nadzieję go zopcić jakimś FFT/sqrt, ale coś nie wyszło...
Obstawiam, że na >-90% to będą jakieś czary na EGF (exponential generating function), ale jakie to nie mam pojęcia (tzn. nie wzięcie kodu i przywalenie prostą konwolucją, ale jakieś faktyczne nietrywialne algebraiczne przekształcenia na nich).
Aczkolwiek przyznam, że już sam dynamik w O(n^2 log n) jest dość trudnym zadaniem... Więc może się podzielę zajawką. Zliczyć te drzewa w O(n^dużo) to nie tak trudno standardowym trikiem z fixowaniem centroidu, ale aby uzyskać n^2 log n, to trzeba wpaść na pomysł, aby fixować nie centroid, a tak jakby "centroid ważony zbiorem niezależnym" i wtedy w ogóle pozbywamy się w dynamiku wymiaru, który liczy nam rozmiar drzewa
Aczkolwiek przyznam, że już sam dynamik w O(n^2 log n) jest dość trudnym zadaniem... Więc może się podzielę zajawką. Zliczyć te drzewa w O(n^dużo) to nie tak trudno standardowym trikiem z fixowaniem centroidu, ale aby uzyskać n^2 log n, to trzeba wpaść na pomysł, aby fixować nie centroid, a tak jakby "centroid ważony zbiorem niezależnym" i wtedy w ogóle pozbywamy się w dynamiku wymiaru, który liczy nam rozmiar drzewa
> standardowym trikiem z fixowaniem centroidu
jest gdzieś opisany ten trick?
jest gdzieś opisany ten trick?
@Franciszek
Zgaduję, że chodzi o coś takiego, jak w tym zadaniu:
https://codeforces.com/problemset/problem/724/F
(w tutorialu będzie opis)
Pytaniem jest - ile jest nie-izomorficznych drzew o rozmiarze n bez labeli.
Zasadniczo, można policzyć dp[n_vertices][subtree] - ile jest drzew o rozmiarze n_vertices z największym poddrzewem o rozmiarze subtree z wyróżnionym elementem - korzeniem. Można to zrobić w O(n^2 log(n)) z sumami prefiksowymi i kombinacją z powtórzeniami, a potem zliczać liczbę nie-izomorficznych drzew z tego dynamika przy założeniu, że korzeniem jest centroid - będzie przypadek szczególny przy 2 centroidach i parzystej liczbie wierzchołków.
Te 2 sekwencje są szerzej opisane tu:
https://oeis.org/A000081
https://oeis.org/A000055
Z tego można było zaklepać dynamik w jakimś O(n^4 log(n)) do tego zadania dodając jeszcze 2 wymiary.
Zgaduję, że chodzi o coś takiego, jak w tym zadaniu:
https://codeforces.com/problemset/problem/724/F
(w tutorialu będzie opis)
Pytaniem jest - ile jest nie-izomorficznych drzew o rozmiarze n bez labeli.
Zasadniczo, można policzyć dp[n_vertices][subtree] - ile jest drzew o rozmiarze n_vertices z największym poddrzewem o rozmiarze subtree z wyróżnionym elementem - korzeniem. Można to zrobić w O(n^2 log(n)) z sumami prefiksowymi i kombinacją z powtórzeniami, a potem zliczać liczbę nie-izomorficznych drzew z tego dynamika przy założeniu, że korzeniem jest centroid - będzie przypadek szczególny przy 2 centroidach i parzystej liczbie wierzchołków.
Te 2 sekwencje są szerzej opisane tu:
https://oeis.org/A000081
https://oeis.org/A000055
Z tego można było zaklepać dynamik w jakimś O(n^4 log(n)) do tego zadania dodając jeszcze 2 wymiary.
dzięki!
Ja jakoś w żadnym momencie myślenia nad tym zadaniem nie ustalałem liczby wierzchołków. Wydało mi się, że rozmiar independent setu nie jest tutaj czymś specjalnym, i to przejście z drzew nieukorzenionych na ukorzenione zadziałałoby gdyby to co nas interesuje w drzewach było dowolną funkcją f(T) (o ile umiemy przeliczać f po doczepieniu rootowi dodatkowego poddrzewa, co jest prawdą zarówno gdy f = liczba wierzchołków, jak i gdy f jest takie jak tutaj). Ale może to nie jest prawda?