General: Kłopotliwa konstrukcja suflinków

Public message

Pamiętacie wątpliwości na kółku, o to jak konstruować suflinki, żeby nie dostać TLE? Otóż metoda którą pokazałem jest w pełni poprawna i pozwala nie martwić się jakkolwiek złożonością, gdyż działa ona oczywiście w czasie stałym. Okazuje się jednak, że zwyczajne konstruowanie, poprzez skakanie suflinkiem w dół tak długo jak trzeba, też się amortyzuje. Wykazanie tego jest ciekawym ćwiczeniem i zachęcam do zmierzenia się z nim ;) Jeśli jednak ktoś chce poznać szkic dowodu, oto on: Za funkcję potencjały przyjmujemy dla każdego wierzchołka głębokość * (stopień wyjściowy - 1). Wtedy jednemu z synów przekazujemy swój potencjał, a reszcie hojnie dajemy nowy potencjał głębokość. Widać że nigdy suma skoków suflinkami takiego potencjału nie przekroczy. Jeśli zaś zsumujemy podane wartości dla wszystkich wierzchołków, otrzymamy sumę długości wszystkich wzorców, co jest złożonością nas zadowalającą.