Trzy słowa o zadaniu 4 z I egzaminu z ASD 2010/2011
=====================================================

Zadanie okazało się średnio trudne. 

W części (a) najłatwiej było:
 - skonstruować jedynego (z dokładnością do zamiany liter a i b)
  słowo-kandydata dla danej tablicy P:
   s[1] = 'a'
   s[i] = 'b' jeśli P[i] = 0 oraz i > 1
   s[i] = s[P[i]] jeśli P[i] > 0 oraz i > 1
  - policzyć dla tablicy s tablicę prefikso-sufiksów i sprawdzić
  czy wyjdzie to samo.
To oczywiście działa w czasie liniowym.
Wiele rozwiązań robiło to tak, jak wyżej.
Pojawiała się też alternatywna, też poprawna konstrukcja słowa s:
   s[1] = 'a'
   jeśli P[i+1] = P[i]+1, to s[i+1] = s[P[i]+1],
   w przeciwnym przypadku P[i+1] = przeciwna litera do s[P[i]+1]
Wiele rozwiązań próbowało robić, jak wyżej, ale "na bieżąco"
wyliczać tablicę prefikso-sufiksów tworzonego słowa i sprawdzać,
czy wyjdzie to samo. Wielu osobom się to udało, ale tu czaiły
się problemy i wiele rozwiązań niepoprawnie dokonywało tego sprawdzenia.
Właściwie wszystkie takie rozwiązania nie działały na jednym
z następujących dwóch przykładów:
 P[0..4] = 0,0,0,1,0
 wówczas s[1..4] = abab, ale wtedy P[4] = 2.
 P[0..10] = 0,0,0,1,2,0,1,2,3,4,1
 wówczas s[1..10] = ababbababa, ale wtedy P[10] = 3.
Szczególnie zdradliwy jest ten ostatni przykład, gdzie
prefikso-sufiks okazuje się być pomiędzy P[10]=1 a P[9]+1=5.

Parę osób źle zrozumiało zadanie, myśląc, że dane jest też słowo
s i wystarczy policzyć, czy ma daną tablicę prefikso-sufiksów.
W zadaniu było jasno napisane, że dana jest tablica P[],
a mamy sprawdzić czy "dla pewnego słowa", a nie danego.

Punktacja:
5pkt   poprawne rozwiązanie działające w czasie liniowym
2pkt   rozwiązanie, z którego dało się odzyskać poprawne tworzenie
       słowa s[] w czasie liniowym, ale dalej było coś popsute
3pkt   rozwiązanie, które próbuje przedłużać o literę a i b,
       i doliczać tablicę P, i wybierać pasującą literę,
       ale bez uzasadnienia, że naraz nie mogą i a i b pasować
2pkt   rozwiązanie poprawnie weryfikujące utworzone słowo,
       ale coś jest zepsute w samym tworzeniu słowa
0pkt   niepoprawne lub ponadliniowe rozwiązanie
0pkt   zakładanie, że słowo s[] jest dane
-1pkt  brak analizy złożoności

W części (b) oceniałem liberalnie. Można było zarówno
założyć, że dana tablica zaczyna się od P[1], i że od P[0].
Akceptowałem też twierdzenie, że P[8]=2 w tworzonym słowie
(choć jest to P[8]=5), gdyż zauważenie prefikso-sufiksu
wielkości 2 załatwiało sprawę.
Nie akceptowałem natomiast, poza niepoprawną argumentacją,
argumentacji "odpalam algorytm z punktu a i mówi NIE",
bez słowa komentarza, jak on działa (napisanie "i algorytmowi
się nie zgadza na P[8]" wystarczało).

Punktacja:
2pkt   poprawna argumentacja
0pkt   niepoprawna argumentacja, lub powołanie się na algorytm
       bez słowa dodatkowego komentarza