7.03.2013

1. Gra w kropki i kreski

  • artykuł w Delcie
  • skoro wiemy jak grać by wygrać możemy już przejść tu (mój wynik ;)
  • zachęcam do napisania algorytmu, bo nie ma to jak przegrać z własnym programem ;)

2. "Odśnieżanie" ONTAK 2012

  • omówienie w Delcie
  • niestety, nie mogłem nigdzie znaleźć sprawdzaczki, ani chociażby treści zadania

3. KMR (Karpa-Millera-Rosenberga)

  • dość przyjazne wytłumaczenie z którego korzystałem na Algorytmiczne Wiki
  • dla słowa S o długości n w czasie O (n*log_n) tworzy tablicę DBR[log_n][n], która pozwala nam szybko wypisać w kolejności leksykograficznej wszystkie podsłowa S o zadanej długości (DBR = Dictionary of Basic Factors - słownik podsłów bazowych)
  • niech S: aabdbeb, n= 7
  • w skrócie:

1. najpierw dzielimy S na podsłowa długości k = 1, sortujemy je i zamieniamy na liczby odpowiadające ich kolejności po posortowaniu (a = 1, b = 2, d= 3, e = 4)
2. teraz S: 1, 1, 2, 3, 2, 4, 2
3. uzupełniamy tablice DBR[0][1...n] powyższym ciągiem
4. powtarzamy algorytm iteracyjnie dla k = kolejne potęgi 2
5. czyli dla k = 2 dzielimy S na podsłowa, które reprezentujemy za pomocą pary (a, b), gdzie:
'a' to kolejność jaką zajmuje podsłowo długości k/2 zaczynające się od tej litery (pamiętamy jej indeks w S) po posortowaniu
'b' to kolejność jaką zajmuje podsłowo długości k/2 zaczynające się w słowie S na pozycji pozycja_a + k/2 po posortowaniu
chodzi o to, że to nasze podsłowo długości 'k' skłąda sie z dwóch podsłów długości k/2 zaczynających się na odpowiednich pozycjach w S
6. sortujemy te pary
7. uzupełniamy DBR[1][1...n] pozycjami, na jakich po posortowaniu znajdują cię podsłowa zaczynające się w S na pozycjach 1..n (np. jeśli podsłowo zaczyna się w S na poz = 6, a po posorowaniu jest 4-te w kolejności, to DBR[1][6] = 4)

  • o czym informuje nas tablica DBR? przykłady:

DBR[0][5] = 10 podsłowo długości 2^0=1 zaczynające się na pozycji 5 w S jest 10 w kolejności leksykograficznej wśród podsłów tej długości
DBR[3][5] = 10 podsłowo długości 2^3=8 (to na kółku pokręciłem, bo powiedziałem że długości 3, a ma być oczywiście 8) zaczynające się na pozycji 5 w S jest 10 w kolejności leksykograficznej wśród podsłów tej długości
DBR[2][4] = 9 podsłowo długości 2^2=4 zaczynające się na pozycji 4 w S jest 9 w kolejności leksykograficznej wśród podsłów tej długości

  • jak odpowiadać na pytanie: Wypisz leksykograficznie wszystkie podsłowa S długości k = 7?

1. najpierw zastanówmy się, jak wydobyć informacje o jednym podsłowie
2. niech P będzie tym podsłowem, niech zaczyna się w S na pozycji pos = 3 i ma długość 'k'
3. dla 'k' będącego potęgą dwójki (k = 2^i) byłoby łatwo, bo wystarczyłoby sprawdzić DBR[i][pos]
4. jeśli DBR[i][pos] = 9, to P wśród podsłów długości 'k' jest 9-te w kolejności leksykograficznej (jednakże może być wiele takich samych słów jak P)
5. natomiast dla 'k' nie będącego potęgą 2, np k = 7, robimy tak:
6. sprawdzamy DBR[2][pos], DBR[1][pos+2^2], DBR[0][pos+2^2+2^1] (najlepiej to sobie narysować)
7. jeśli były równe kolejno np. 3, 6, 1 to tworzymy ciąg (3, 6, 2)
8. teraz takie same ciągi tworzymy dla pozostałych podsłów, na koniec je sortujemy

4. Kody do zadań z II etapu OIa (bez Inspektora)