Algorytmika (2010L) - kryteria oceny pierwszego zadania domowego

Rozwiązania można oglądać we wtorek 29 marca, między 15:00 a 16:30 w 5790. Można też próbować w innych terminach, ale nie ma gwarancji, że będę u siebie w pokoju.

Część A

Wszystkie poprawne rozwiązania sprowadzały się w zasadzie do tego samego pomysłu. Należało skonstruować graf o O(n) wierzchołkach i O(n²) krawędziach i użyć algorytmu MKM do znalezienia w nim maksymalnego przepływu. Całość działała wówczas w czasie O(n³). Na rozwiązanie powinny składać się następujące części (poniżej zakładam, że suma c_i jest równa sumie r_i):

Opis konstrukcji grafu
Dowód, że przepływ całkowitoliczbowy o wartości c₁ + c₂ + ... + c_n jest tożsamy z macierzą zgodną (w obydwie strony). Wystarczy po jednym zdaniu w każdą stronę. W prawo: macierz definiujemy tak a tak, zgodność wynika z warunku zachowania przepływu. W lewo: pokazujemy definicję przepływu na podstawie macierzy, zgodność macierzy daje warunek zachowania przepływu, reszta warunków na przepływ wynika wprost z definicji.
Określenie złożoności algorytmu obliczającego przepływ w grafie.

Kryteria oceny:

-2 za złożoność gorszą niż O(n³) (na przykład przez użycie algorytmu innego niż MKM)
-1 za redakcję rozwiązania, jeśli rozwiązanie niejawnie zakładało, że każdy przepływ jest całkowity ORAZ dowód był tylko w jedną stronę lub nie zawierał żadnych argumentów (a jedynie np. konstrukcję). Inne usterki się raczej nie zdarzały, punkt odejmowałem jedynie, gdy w rozwiązaniu pojawiły się obydwie.
-3 za konstrukcję grafu z O(n²) wierzchołkami.

Część B

10 punktów za rozwiązanie liniowe z dobrym uzasadnieniem
7 punktów za O(n log n) (zazwyczaj spowodowane wyszukiwaniem binarnym w ostatniej fazie lub wolniejszym sortowaniem). Jeśli brakowało zdania o tym, że sortowane liczby są O(n), to niestety musiałem uznać, że rozwiązanie chodzi w O(n log n).
4 punkty za O(n²)
3 punkty za rozwiązania wielomianowe, wolniejsze od O(n²)
2 punkty za rozwiązanie zachłanne O(n²)bez dowodu

Kilka słów o redakcji rozwiązań

Rozwiązania różniły się od siebie znacznie pod względem długości. Najkrótsze w pełni poprawne mieściło się na jednej stronie, zaś najdłuższe zajmowało 7 stron. Zazwyczaj im dłuższe było rozwiązanie, tym większe fragmenty dawało się usunąć bez straty dla jego jakości. Poniżej zamieszczam przykładowy opis rozwiązania części B z kilkoma uwagami i poradami. Zwracam uwagę na rzeczowy i zwięzły sposób opisania rozwiązania - lepiej zredagowane rozwiązania pozwolą nam je szybciej oceniać.

Mamy graf o wierzchołkach s, t, R₁, R₂, ..., R_n, C₁, C₂, ..., C_n. Od s do R_i prowadzi krawędź o przepustowości r_i, między R_i a C_j są krawędzie jednostkowe, od C_j do t prowadzą krawędzie o przepustowościach c_j. Na podstawie rozważań z części A wiemy, że wystarczy znaleźć w tym grafie wartość maksymalnego przepływu, czyli, z twierdzenia o MP i MP, wartość minimalnego przekroju.

Niech (S, V - S) to dowolny przekrój w tym grafie. Do części S musi należeć źródło s. Oznaczamy przez S_R zbiór tych elementów z części R, które nie należą do S zaś przez S_C - przecięcie S z częścią C. Jeśli |S_R| = k, zaś |S_C| = l, to przepustowość tego przekroju to
r_i₁ + r_i₂ + ... + r_{i_k} + c_j₁ + c_j₂ + ... + c_{j_l} + (n-k)(n-l)
dla pewnych ciągów indeksów i oraz j.

Jasne jest, że dla ustalonych k i l powyższa suma jest najmniejsza, jeśli weźmiemy odpowiednio k oraz l najmniejszych wyrazów z ciągów r oraz c. (Tu chciałbym zwrócić uwagę, że nieudowadnianie tego faktu jest wskazane, bo poprawia czytelność rozwiązania). Na początku algorytmu możemy sprawdzić, czy wszystkie wyrazy tych ciągów są mniejsze niż n i, jeśli tak jest, sortujemy ciągi przez zliczanie, w O(n). Jeśli pewien wyraz jest większy od n, rozwiązanie nie istnieje. Dalej zakładamy więc, że ciągi te są posortowane niemalejąco.

Możemy teraz zapisać przepustowość minimalnego przekroju (o odpowiednich rozmiarach przecięć z poszczególnymi częściami grafu) w następującej postaci:
r₁ + r₂ + ... + r_k + (c₁ + k-n) (c₂ + k-n) ... + (c_l + k-n) + (n-k)n
Znajdziemy minimum powyższego wyrażenia dla każdego k. Zauważmy, że najlepiej wziąć takie l, by zsumować wszystkie wyrazy c_j ≤ n-k. Korzystamy tu jedynie z faktu, że podzbiór pewnego zbioru liczb całkowitych A ma najmniejszą sumę, gdy składa się ze wszystkich liczb nieujemnych w A.
Obliczamy zatem (w O(n)) tablicę indeksowaną liczbami od 0 do n, która w komórce i pamięta ile jest wyrazów ciągu c nie większych od i oraz jaka jest ich suma. To pozwala znaleźć minimalną wartość badanego wyrażenia dla każdego k w czasie stałym. Tym sposobem możemy w czasie liniowym znaleźć przepustowość minimalnego przekroju.

Warto jeszcze dodać, że opis w postaci podobnej do powyższej jest dużo łatwiejszy do zrozumienia niż napisanie kodu rozwiązania i tłumaczenie poszczególnych wierszy. Pseudokod przydaje się, gdy chcemy pokazać jak wygląda przepływ sterowania między poszczególnymi fazami algorytmu (np. w opisie algorytmu Dinica), jednak jeśli algorytm daje się poskładać z kilku prostych kawałków, zwyczajny opis wydaje się lepszym rozwiązaniem.