1. Klasówka 2021/22 (25.11.2021)#
Zadanie 1 (7 punktów)#
Powiemy, że zbiór \(n\) liczb całkowitych jest prawie gęsty, jeśli zawiera podzbiór o rozmiarze większym niż \(n/3\), w którym różnica pomiędzy największym i najmniejszym elementem jest mniejsza od \(n\). Taki podzbiór nazywamy świadectwem. Dana jest dodatnia liczba całkowita \(n\) oraz \(n\)-elementowy zbiór liczb całkowitych \(S\). Zaproponuj algorytm, który w czasie liniowym sprawdzi, czy \(S\) jest prawie gęsty.
Uwaga: 3 punkty uzyskasz za algorytm, który w czasie liniowym sprawdza, czy wskazany, dowolny element z S należy do jakiegoś świadectwa.
Podpowiedź
Jeśli zbiór jest prawie gęsty, to do jego świadectwa należy co najmniej jeden z elementów o randze \([n/4, n/2, 3n/4]\). Takie elementy można obliczyć w czasie liniowym używając algorytmu magicznych piątek.
Sprawdzanie czy x należy do jakiegoś świadectwa możemy rozwiązać poprzez zliczenie liczby elementów o wartościach \([x-n,\ldots,x+n]\). Następnie musimy sprawdzić czy istnieje i takie, że \(\sum_{j=x-i}^{x-i+n} Count[j] > n/3\).
Zadanie 2 (6 punktów)#
Zaproponuj optymalny ze względu na porównania algorytm sortowania siedmioelementowego ciągu \(x_1, \ldots, x_7\), o którym wiadomo, że \(x_1 < x_2\), \(x_1 < x_3\), \(x_4 < x_5\), \(x_4 < x_6\). Udowodnij optymalność swojego algorytmu.
Zadanie 3 (7 punktów)#
Dla dodatniej liczby całkowitej \(n\) kratownicą \(M_n\) nazywamy skierowany graf \((V,E)\) bez pętli, w którym \(V = \{(x,y): x = 0, 1, ..., n\ \mbox{oraz}\ y = 0, 1, ..., n\}\) i \(E = \{(x,y)\rightarrow (x’,y’): 0\le x’-x\le 1\ \mbox{oraz}\ 0\le y’-y\le 1\}\). Wierzchołki grafu \(M_n\) pomalowano na biało lub czarno. Białą ścieżką nazwiemy każdą ścieżkę, na której wszystkie wierzchołki są białe. Dane są liczba całkowita \(n > 0\), nieujemna liczba całkowita \(m \le (n+1)^2\) oraz \(m\) różnych, białych wierzchołków \((x_1, y_1), (x_2, y_2), ..., (x_m, y_m)\). Pozostałe wierzchołki są czarne. Zaproponuj wydajny (czasowo i pamięciowo) algorytm, który obliczy liczbę wszystkich białych ścieżek z wierzchołka \((0,0)\) do wierzchołka \((n,n)\).
Uwaga: uzasadnij poprawność zaproponowanych rozwiązań oraz przeprowadź analizę złożoności obliczeniowej podanych algorytmów.