21.03.2013
1. Korale z I etapu XVII Olimpiady Informatycznej.
- Dobieramy dowolną liczbę pierwszą większą (nazwijmy ją p) co najmniej 2 razy niż rozmiar alfabetu.
- Dobieramy dużą liczbę pierwszą, której kwadrat nie przekroczy long longa (np 10^9+7). Nazwijmy ją BASE.
- Hash słowa a to ( a[0]+a[1]*p+a[2]*p^2+…a[n]*p^n. )%BASE
- Zahaszowanie wszystkich sufiksów słowa: hash[i]=hash[i+1]*p+a[i]. Pętle wykonujemy od n-1 do 0.
- Wzór na hash podsłowa a[ begin ,end ] to: ( hash[begin] - hash[end]*p^(end-begin+1) )%BASE. Pamiętajcie o stablicowaniu potęg modulo BASE.
- Można rozpatrzyć wszystkie możliwe k. Wszystkich podciągów jest rzędu n*log(n)
- Tworzymy set hashy i dla każdego kolejnego podciągu o długości k sprawdzamy ,czy hash jego bądź jego odwrotności wystąpił wcześniej.
2. Okropny Wiersz z II etapu XIX Olimpiady Informatycznej.
- Lemat: Aby słowo miało okres długości k musi mieć prefikso-sufiks o długości n-k.
- Wygenerowanie wszystkich dzielników każdej z liczb i sprawdzanie przy pomocy hashowania, czy podsłowo ma taki pełny okres.
- Rozwiązanie wzorcowe wykorzystujące Lemat o okresowości i Sito Eratostenesa.
- Lemat o okresowości: jeśli słowo ma okresy a i b to ma też okres NWD(a,b).
3. Różnica z II etapu XVIII Olimpiady Informatycznej.
- Rozpatrywanie każdej pary liter ,jako najczęściej i najrzadziej występująca.
- Stworzenie listy wystąpień każdej litery.
- Reprezentacja ciągu wystąpień: 1 to wystąpienie najczęstszej litery, -1 to wystąpienie najrzadszej litery.
- Wynikiem dla pary jest podciąg spójny o największej sumie. Pamiętamy ,że w tym podciągu musi wystąpić co najmniej jedno -1.
4. Pociągi z II etapu XV Olimpiady Informatycznej.
- Tworzymy dla każdego pociągu jego historię, do jakich grup należał.
- Zmiana hasha gdy w słowie a zmienia się literka na pozycji i: hash-= stara_literka*p^i hash+=nowa_literka*p^i
- Dla każdej grupy trzymamy info jak zmieniała się jej liczność, podczas zamian.
- Po zakończeniu zamian budujemy drzewa przedziałowe dla grup.
- Sprawdzamy dla każdego pociągu, jaka była maksymalna liczność w grupach ,które odwiedził w czasie ,kiedy tam był.
5. Coś z innej beczki: Paliwo z Potyczek Algorytmicznych 2011.
- Najpierw bierzemy wierzchołki na średnicy drzewa ,potem obojętnie co dalej.
wersja strony: 7, ostatnia edycja: 12 Oct 2013 13:35