W USOSie wpisałem bardzo skrótowe notatki co do oceny. Zadania można oglądać na konsultacjach (piątki 10:15-11:45, 5790) jak już będą publicznie dostępne wyniki w USOSie.
Mam jedną anonimową pracę. Jeśli ktoś oddał prace, a - po opublikowaniu punktów - będzie miał pustą kratkę w USOSie, proszę o maila.
Najczęściej pojawiającym się poprawnym rozwiązaniem było przechowywanie ciągu jako drzewa zrównoważonego binarnego (np. AVL), gdzie każdy węzeł odpowiada elementowi ciągu, a porządek elementów ciągu to porządek in-order. W ten sposób elementy wcześniej występujące w ciągu przechowywane są jako "mniejsze" wg porządku drzewa binarnego. Ważną uwagą jest tutaj to, że nie musimy jawnie przechowywać kluczy (pozycji): AVL lub inne drzewo wyszukiwań radzi sobie ze zrównoważeniem bez nich, a przechowywanie ich jawne jest niemożliwe jeśli chcemy mieć operacje Wstaw i Usuń.
By znaleźć i-ty element, w każdym węźle przechowujemy liczbę elementów w jego poddrzewie - w ten sposób jesteśmy w stanie w czasie O(log n) zejść w dół do odpowiedniego elementu. Mając takie wyszukanie, Wstaw i Usuń sprowadza się do standardowych operacji wstawiania i usuwania z wybranego zrównoważonego drzewa binarnego.
By wyliczyć liczbę elementów w poddrzewie, korzystamy z tego, że wszystkie rotacje i inne zmiany, które robimy na drzewie, są lokalne. Potrafimy wyliczyć tą liczbę dla danego węzła w czasie stałym, znając wielkości poddrzew dla obu synów węzła. Tak więc, jesteśmy w stanie lokalnie poprawiać tę wartość dla modyfikowanych węzłów (których jest O(log n)).
By zaimplementować operację suma_parzystych(), musimy w każdym węźle trzymać dwie liczby: sumę wartości na pozycjach parzystych oraz nieparzystych w podciągu wyznaczonym przez podddrzewo, którego korzeniem jest dany węzeł. I tu jest ważny szczegół: to "parzyste" lub "nieparzyste" określamy lokalnie, w tym podciągu, a nie w całym ciągu: pierwszy element podciągu jest na pozycji nieparzystej, drugi parzystej itd. Nie jesteśmy w stanie utrzymać efektywnie tych pól dla "globalnej" definicji parzystej/nieparzystej pozycji, gdyż np. wstawienie elementu na pozycję pierwszą wymusiłoby zamianę tych pól we wszystkich węzłach drzewa, których jest n. Podobnie jak poprzednio, mając te dwie liczby dla synów węzła, możemy w czasie stałym wyliczyć je dla ojca.
W sumie więc mamy O(1) na inicjalizację i odczytanie wartości sumy parzystych elementów ciągu, i O(log n) na pozostałe operacje.
Alternatywnym rozwiązaniem jest trzymanie - podobnie jak w powyższym opisie - dwóch ciągów dynamicznych jako drzew binarnych zrównoważonych; jeden ciąg składa się z elementów na pozycjach parzystych w oryginalnym ciągu, a drugi z elementów na pozycjach nieparzystych. Teraz, przy operacji Usuń i Wstaw musimy zamienić miejscami sufiksy tych dwóch ciągów. To nie jest proste, ale nie jest nierobialne.
Jeśli próbujemy implementować ciągi jako AVLe czy drzewa czerwono-czarne, to nie widzę, by dało się to łatwo zrobić: nie mamy żadnej gwarancji, że te dwa drzewa wyglądają podobnie (mają tylko prawie taką samą liczbę elementów) i nie widać, jak zrobić dobrze przepinanie poddrzew (które ponadto może bardzo zniszczyć niezmienniki balansujące drzewo). Natomiast można użyć drzew zrównoważonych, które mają dostępną operację scalania i rozdzielania, np. 2-3 drzew lub drzew typu splay. W tym rozwiązaniu wymagałem, by dobrze opisać, jak wygląda to zamienianie poddrzew: w splayach trzeba uważać, by przypadkiem nie podnieść za bardzo potencjału (w analizie).
W pełni poprawne rozwiązanie oczywiście dostawało 7pkt.
Implementacja samego dynamicznego ciągu, bez operacji suma_parzystych(), była warta 3pkt.
Kilka osób próbowało jawnie wpisywać klucze ,,rzeczywiste'', np. nowy i-ty element dostawał średnią arytmetyczną klucza starego (i-1)-szego elementu i starego i-tego. Nie znam żadnej dobrej i prostej implementacji takich kluczy, przy których wykładniki tych kluczy nie zaczynają szybko rosnąć; zauważmy, że przy powyższej implementacji z średnimi ciąg k wstawień elementów na drugą pozycję daje mianowniki rzędu 2^k, których zapis binarny rośnie liniowo z liczbą operacji, a my musimy generować te klucze na bieżąco, nie znając przyszłych operacji i przyszłej struktury drzewa. Kompletne rozwiązanie, ale z jawnymi kluczami ,,rzeczywistymi'', dostawało 5pkt, a 2pkt jeśli nie miało operacji suma_parzystych().
Wiele osób poprawnie operowało ciągiem, definiowało w jakiejś formie sumy parzystych i nieparzystych elementów poddrzewa, ale następnie niepoprawnie je aktualizowało. Najczęściej błąd polegał na:
Rozwiązaniom, które nie całkiem poprawnie utrzymywały dynamiczny ciąg, ale coś kombinowały z sumami zarówno parzystymi jak i nieparzystymi, dawałem za to dodatkowego punkta. Jeśli to kombinowanie było całkiem poprawne (sformułowanie, że sumy ojca można wyliczać znając sumy synów), były to trzy punkty.
Wiele osób próbowało też utrzymywać ciąg w AVLu, ale elementy ciągu miały być trzymane tylko w liściach. Niestety, rotacje nie utrzymują zbioru liści: węzeł, w wyniku rotacji, może stać się lub przestać być liściem, co zazwyczaj sporo psuło w koncepcji rozwiązania (choć nieraz można było dostać punkta za kombinowanie z sumami parzystymi i nieparzystymi).
Było też kilka rozwiązań podliniowych, ale gorszych od O(log n) (zazwyczaj O(sqrt(n))). Dostawały one 1pkt.
W przypadku rozwiązania podobnego do alternatywnego, parę osób próbowało przepinać poddrzewa AVLa, argumentując, że jest ich tylko O(log n). To prawda, że jest ich tyle, ale nie ma żadnej gwarancji, że te dwa drzewa będą podobne i będzie jak przepinać. Ponadto, takie przepinanie może mocno zepsuć niezmienniki równoważące drzewo (np. różnicę wysokości w AVLu) i równoważenie może wymagać dużo pracy.