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