I Gobeliny XX OI
- Przechodzimy wielokąt zgodnie z ruchem wskazówek zegara.
- Jeśli odcinki n i n+1 mają być nieoświetlone, to możemy je zamienić w jeden (pod warunkiem, że ich punkt wspólny leży po lewej stronie prostej wyznaczonej przez pierwszy pkt. odcinka n i drugi pkt. odcinka n+1)
- Po takim przejściu mamy 2 możliwości:
a) wszystkie odcinki mają być oświetlone
b) istnieją odcinki, które mają być nieoświetlone
- Co ciekawe, dla obu przypadków postępowanie jest podobne. Znów przechodzimy graf clockwise i teraz:
- dla odcinka oświetlonego wywalamy część wielokąta leżącą po lewej stronie
- dla odcinka nieoświetlonego wywalamy część po prawej stronie
- W wywalanej części nie może znajdować się lampa. "Wywalanie" to może być np. usuwanie punktów, które mieliśmy w dalszej kolejności odwiedzić.
- Jeśli mieliśmy do czynienia z przypadkiem a) to w powstały na końcu w wielokąt wstawiamy lampę i sprawdzamy, czy oświetli nam wszystkie odcinki. Dla b) lampa musi się znajdować na przecięciu się prostych wyznaczonych przez odcinki zaciemnione.
II Algorytmy tekstowe
1. Podstawowe pojęcia (link do poprzednich zajęć z 7 listopada)
2. Algorytm KMP
- wyznacza tablice sufixową (KMP_Make)
- która może posłużyć do odnalezienia wzorca w podanym słowie (KMP_Match)
- pseudokod O(n+m) n - długość słowa, m - długość wzorca
3. Zadanie Szablon XII OI.
- Zauważamy, że rozwiązanie, czyli szukany najkrótszy szablon, musi być pref-sufixem podanego napisu S.
- Trzeba trochę zmodyfikować KMP tak aby nie odnajdywał najdłuższych pref-sufixów podsłów słowa S (na końcu także samego S), ale wszystkie(od najkrótszych do najdłuższych) pref-sufixy tylko słowa S
- Jeśli na tym poprzestaniemy to mamy algorytm O(n^2) (dla każdego pref-sufixu sprawdzamy czy jest szablonem). Takie sprawdzanie to nic innego jak wyszukiwanie wzorca w tekście.
- Ostanie spostrzeżenie, prowadzące do rozwiązania wzorcowego O(n*log_n):
1. Oznaczmy przez X zbiór wszystkich pref-sufixów słowa S.
2. Niech X będzie posortowany rosnąco względem długości pref-sufixów.
3. Jeśli y_i oraz y_i+1 należą do X to jeżeli y_i+1 /2 <= y_i to możemy y_i+1 przedstawić tylko za pomocą odpowiedniego połączenia ze sobą dwóch y_i (widać ładnie na rysunku).
4. Oznacza to, że jeżeli y_i nie jest najkrótszym szablonem, to jako kolejny wzorzec wybieramy więc takie y, że y > 2*y_i co powoduje że sprawdzimy co najwyżej log_n ilości pref-sufixów.
III Zadanie Wojna PA 2012
1. Treść
2. Omówienie
Zachęcamy do zapisania obu zadań! Dla leniwych kody pojawią się wkrótce… ;)
