English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: Praca domowa - jak zrobić?
Jak w temacie
Struktura rozwiązania jest dość podobna do algorytmu KMR, może to pomoże w wyobrażeniu sobie tych operacji.
Weźmy taki problem: mamy m dwuelementowych ciągów i dość niewiele (k1+k2=k) zmian (innymi słowy n=2 i więcej elementów niż zmian). Możliwych różnych dwuelementowych ciągów jest k+1. Posortujmy je i każdemu ciągowi przypiszmy jego indeks. Teraz mamy m jednoelementowych ciągów i k zmian w nim, bez straty informacji. Jeśli będziemy śledzić tylko zmiany to potrafimy taką operację wykonać w O(k).
Wróćmy do wyjściowego problemu. Połączmy parami każde dwa kolejne indeksy 1..n, redukując zagadnienie z n do n/2 w zamortyzowanym czasie O(m), ponieważ każda zmiana występuje tylko w jednej z wybranych par. Po O(log n) takich kroków dostaniemy n=1 a zmiany będą mówiły jakie są indeksy w posortowanym ciągu, czyli całość zajmuje O(m log n).
Weźmy taki problem: mamy m dwuelementowych ciągów i dość niewiele (k1+k2=k) zmian (innymi słowy n=2 i więcej elementów niż zmian). Możliwych różnych dwuelementowych ciągów jest k+1. Posortujmy je i każdemu ciągowi przypiszmy jego indeks. Teraz mamy m jednoelementowych ciągów i k zmian w nim, bez straty informacji. Jeśli będziemy śledzić tylko zmiany to potrafimy taką operację wykonać w O(k).
Wróćmy do wyjściowego problemu. Połączmy parami każde dwa kolejne indeksy 1..n, redukując zagadnienie z n do n/2 w zamortyzowanym czasie O(m), ponieważ każda zmiana występuje tylko w jednej z wybranych par. Po O(log n) takich kroków dostaniemy n=1 a zmiany będą mówiły jakie są indeksy w posortowanym ciągu, czyli całość zajmuje O(m log n).
Ja to zrobiłem w czasie O(nlg^2n) i pamięci O(nlgn) z wykorzystaniem persistent segment tree. Dla każdego ucznia tworzę sobie nowe drzewo, które różni się w lgn węzłach od poprzedniego ucznia. W węzłach drzewa trzymam wartości hasha na odp przedziale tekstu.
Następnie robię zwykłe sortowanie liczb - porównanie dwóch liczb sprowadza się do znalezienia pierwszego elementu, na którym się różnią hashe i porównania elementów z tekstu na tej pozycji - obie te operacje na drzewach przedziałowych zajmują lg n, czyli całość nlgn porównań * lgn = O(nlg^2n).
Następnie robię zwykłe sortowanie liczb - porównanie dwóch liczb sprowadza się do znalezienia pierwszego elementu, na którym się różnią hashe i porównania elementów z tekstu na tej pozycji - obie te operacje na drzewach przedziałowych zajmują lg n, czyli całość nlgn porównań * lgn = O(nlg^2n).