Komentarz do zadania 1 z pierwszego egzaminu, ASD 2012/13

W USOSie wpisałem bardzo skrótowe notatki co do oceny. Zadania można oglądać w środę, 20.02.2012, w godzinach 10:30-12:00.

Rozwiązanie wzorcowe

Kluczowym pomysłem było potraktowanie każdego odcinka nie jako odcinka, ale jako zbioru maksymalnie 6 punktów o współrzędnych całkowitych. Wówczas, w punkcie (a), naszą strukturą jest zwykły słownik (np. AVL), gdzie elementami są punkty o współrzędnych całkowitych, które należą do jakiegoś odcinka. Słownik ma maksymalnie 6n = O(n) elementów, a zapytanie to zwykły search w słowniku, czyli O(log n).

W punktach (b) i (c) należy wpierw stworzyć listę wszystkich punktów całkowitoliczbowych na wszystkich odcinkach, a następnie ją posortować. Tutaj korzystamy z założenia, że współrzędne są do n3: traktujemy każdą współrzędną jako O(1)-cyfrową liczbę w zapisie o podstawie n, i sortujemy współrzędne jako słowa równej długości, w czasie O(n). Mając posortowaną listę punktów, zadanie jest już proste: (b) to po prostu liczba różnych elementów na liście, a (c) łatwo policzyć, jeśli każdy punkt pamięta jeszcze, czy pochodził z odcinka pionowego czy poziomego.

Punktacja i najczęstsze błędy

W pełni poprawne rozwiązanie oczywiście dostawało 5pkt za każdy podpunkt.

W części (a) był jeden bardzo popularny błąd. Wiele osób próbowało robić tak: osobno rozpatrujemy, czy dany punkt (a,b) należy do jakiegoś odcinka pionowego i osobno do poziomego, robimy osobne (symetryczne) struktury dla tych pytań. Skupmy się na odcinkach poziomych. Każda struktura trzyma odcinek (x1,y)-(x2,y) jako krotkę (y,x1,x2) i porządkuje je leksykograficznie (były też podobne lub równoważne definicje, np. AVL po y, który trzyma w węzłach AVLe po (x1,x2)). Wyszukujemy pierwszy mniejszy od punktu (a,b) (czyli pewnie formalnie, od odcinka (a,b)-(a,b)) i sprawdzamy, czy nas pokrywa. To niestety nie jest poprawne: załóżmy, że mamy dany odcinek (1,0)-(6,0) oraz (2,0)-(3,0). Pytając o (4,0), znajdziemy (2,0)-(3,0), które nas nie przykrywa, a jest później w porządku niż przykrywające nas (1,0)-(6,0).

Widziałem w pracach dwa popularne rozwiązania powyższego problemu. W pierwszym, zlepiamy przecinające się odcinki tak, by każde dwa odcinki w strukturze były rozłączne - i wtedy to wyszukanie daje dobrą odpowiedź. W drugim, zauważamy, że tak naprawdę tylko O(1) odcinków może przykrywać punkt (a,b): (a-5,b)-(a,b), (a-4,b)-(a,b), (a-4,b)-(a+1,b) ... (a,b)-(a+5,b), i odpowiednie pionowe. I po prostu o każdy z tych odcinków pytamy zwykły słownik odcinków. Można też zaimplementować rozwiązanie pośrednie: dla każdego (x,y) zapamiętać najdłuższy odcinek pionowy i poziomy zaczynający się w (x,y), i odpytać tą strukturę o (a,b), (a-1,b), ..., (a-5,b) i symetrycznie w pionie.

W częściach (b) i (c) punktowałem następująco:

  1. jeśli ktoś używał za dużo pamięci (np. n3), ale czas miał liniowy, to dawałem 2pkt;
  2. za czas O(n log n) było 2pkt; tu wielu z Państwa używało struktury z punktu (a), nie zauważając, że jej budowa trwa O(n log n) (o ile się nie zrobi jakiejś sztuczki);
  3. używanie tablicy haszującej na trzymanie punktów na odcinkach było warte 3pkt; tablica haszująca, z losową funkcją z rodziny uniwersalnej, daje oczekiwany, a nie pesymistyczny czas liniowy;
  4. niepoprawne rozwiązanie, ale które próbuje używać sortowania liniowego liczb do n3 dostawało jednorazowego bonusa 4pkt;
  5. niepoprawne rozwiązanie, ale które próbuje zlepiać odcinki i coś na nich operować dostawało jednorazowego bonusa 1pkt;