Drugie Etapy OI

Osiedla (XXVI OI)

Zauważmy, że krawędzie możemy skierować tak, aby każda dwuspójna składowa tworzyła jedno osiedle. Istotnie, możemy krawędzie drzewowe skierować do dołu, a wsteczne do góry. Jest to również optymalne skierowanie. Faktycznie, nie możmy poszerzyć żadnego z osiedli. Gdyby tak nie było, moglibyśmy poszerzyć pewną dwuspójną składową, co oczywiście jest niemożliwe z definicji.

Strajki (XXIV OI)

Będziemy utrzymywali aktualną liczbę spójnych w zmiennej $c$, początkowo równej $1$. Powiedzmy, że rozpoczynamy strajk w wierzchołku $u$. Musimy zatem zwiększyć $c$ o liczbę sąsiadów $u$, w których nie trwa strahk. Analogicznie, kiedy strajk kończymy. Jeżeli za każdym razem będziemy iterować się po wszystkich sąsiadach $u$ otrzymamy złożoność $\mathcal{O}(nm)$. Możemy jednak ukorzenić drzewo w wybranym wierzchołku i w $s[u]$ utrzymywać liczbę przejezdnych synów $u$. Redukuje to złożoność do $\mathcal{O}(m)$.

Marudny Bajtazar (XXVII OI)

Zauważmy, że odpowiedź jest nie większa niż $\log_2 n$. Istotnie, podsłowo o długości $k > \log_2 n$ nie mógłby wystąpić w ciągu $2^k$ razy. Niech każde podsłowo będzie identyfikowane przez odpowiednią liczbę zapisaną w systemie binarnym. Możemy dla każdej długości podsłowa $k$ zliczać wystąpienia każdego z podsłów o długości $k$ w ciągu. Łatwo teraz w czasie logarytmicznym znaleźć odpowiedź iterując się po wszystkich długościach $k$. Liczniki możemy łatwo aktualizować przy każdym zapytaniu w czasie $\mathcal{O}(\log^2 n)$. Ostateczna złożoność to zatem $\mathcal{O}(m\log^2 n)$.

Kontenery (XXIV OI)

Dla każdego $d_i > \sqrt{n}$ po prostu zasymulujemy ustawianie kontenerów. Natomiast dla każdego $d_i \le \sqrt{n}$ przetrzymywać będziemy tablicę, powiedzmy $t[1..n]$, na której końcowo wykonamy sumy prefiksowe co $d_i$, to znaczy: $$p[j] = p[j - d_i] + t[j],$$ gdzie $p[j]$ to nasza tablica sum prefiksowych. Aby w $p[j]$ znajdowała się liczba kontenerów na $j$-tej pozycji, przy $i$-tym zapytaniu musimy zwiększyć $t[a_i]$ o $1$ i zmniejszyć $t[a_i + (\ell_i - 1)d_i + 1]$ o $1$.

Liczby względnie pierwsze (XXIX OI)

Łatwo możemy zliczyć liczby względnie pierwsze z $n$ mniejsze od ustalonego $m$, używając zasady włączeń i wyłączeń. Iterujemy się po wszystkich dzielinkach $n$ zliczając odpowiednio ich wielokrotności mniejsze od $m$. Możemy teraz szukać binarnie $k$-tej liczby względnie pierwszej z $n$. Następne $c$ liczb względnie pierwszych znajdziemy po prostu iterując się po liczbach $k+1, k+2, \ldots$ i sprawdzając ich względną pierwszość z $n$.