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.

6. Kody z wykładu są TUTAJ
Update: wzorcówka do Różnicy