Egzamin poprawkowy 2025/26 (21.02.2026)

Zadanie 1 [12 punktów]

W tym zadaniu rozważamy tablicę \(a[1,\ldots,n]\) zawierającą n parami różnych liczb całkowitych, gdzie n jest liczbą całkowitą większą od 1. Jeżeli \(a = [e_1, e_2, \ldots, e_n]\), to przez Revers(i,j), \(1 \le i \le j \le n\), oznaczamy operację odwrócenie kolejności elementów w podtablicy \(a[i, \ldots, j]\). Dla przykładu, w wyniku wykonania Revers(3,5) na tablicy a = [1,2,3,4,5,6] dostaniemy a = [1,2,5,4,3,6].

1. [3 punkty] Wiadomo, że na uporządkowanej rosnąco tablicy a wykonano dokładnie jedną operację Revers. Zaproponuj optymalny ze względu na porównania algorytm sortujący rosnąco tablicę a.

2. [4 punktów] Wiadomo, że na uporządkowanej rosnąco tablicy a wykonano dokładnie k operacji Revers, \(0 < k \le n\). Udowodnij, że liczba porównań niezbędna do posortowania rosnąco a wynosi co najmniej \(\Omega(k \log k + n)\).

3. [5 punktów] Zaproponuj efektywny algorytm, który posortuje tablicę a, o której mowa w punkcie b), w czasie \(O(n \log k)\)

Zadanie 2 [11 punktów]

Dla całkowitej liczby \(n > 1\) linią \(L_n\) nazywamy graf skierowany \((V_n, E_n)\) taki, że \(V_n = \{1, 2, \ldots, n\}\) i \(E_n = \{1\rightarrow 2, 2\rightarrow 3, \ldots, (n-1)\rightarrow n\}\).

1. [2 punkty] Do linii \(L_{2026}\) dodajemy 1000 nowych, różnych krawędzi, ale nie pętli (krawędzi typu \(i\rightarrow i\)). Jaka jest najmniejsza, a jaka największa możliwa liczba silnie spójnych składowych w nowym grafie?

W zadaniach b) i c) rozpatrujemy dynamicznie zmieniający się graf skierowany G = (V,E), który początkowo jest równy \(L_n\), dla pewnego \(n > 1\).

2. [4 punkty] Zaprojektuj strukturę danych, która umożliwia wydajne wykonywania co najmniej n następujących operacji na grafie G:

   • Ini():: inicjalizacja struktury danych,

   • Add(j, i):: dodaj krawędź \(j\rightarrow i\), o której wiadomo, że nie ma jej w grafie i przy założeniu \(1 \le i < j \le n\),

   • SC(i, j):: odpowiedz, czy wierzchołki należą do tej samej silnie spójnej składowej.

3. [5 punktów] Zaprojektuj strukturę danych, która umożliwia wydajne wykonywania następujących operacji na grafie G:

   • Ini():: inicjalizacja struktury danych,

   • Add(i, j):: dodaj krawędź \(i\rightarrow j\), o ile nie ma jej w grafie i przy założeniu \(1 \le i \ne j \le n\),

   • Remove(i, j):: usuń krawędź \(i\rightarrow j\), o ile jest w grafie i przy założeniu \(i+1 \ne j\),

   • SingleSC(i):: odpowiedz, czy wierzchołek i tworzy jednowierzchołkową silnie spójną składową.

Zadanie 3 [9 punktów]

W tym zadaniu rozważamy słowa o długości n > 2 zbudowane z liter a i b i zakończone symbolem $.

1. [3 punkty] Jaka jest najwyższa, a jaka najniższa wysokość drzewa sufiksowego dla tego rodzaju słowa o długości 6. Uwaga: wysokość mierzymy liczbą krawędzi.

2. [6 punktów] Zaproponuj wydajny algorytm, który dla danego słowa x o długości co najmniej 3 i dodatniej liczby całkowitej \(k \le |x|/2\), znajdzie liczbę różnych palindromów o długości 2k występujących w słowie x.

Zadanie 4 [8 punktów]

1. [4 punkty] Dla n > 1 dana jest tablica a[1..n] liczb całkowitych z przedziału \([1,\ldots,n^2]\). Zaprojektuj efektywny algorytm, który dla zadanych dodatnich liczb całkowitych m i k obliczy ile jest par (i,j) takich, że \(1 \le i < j \le n\), \(j \le i+m\) oraz \(|a[i] - a[j]| = k\).

2. [4 punkty] Wiadomo, że w tablicy a[1..n] zapisano tylko liczby całkowite z przedziału [1..2026]. Zaprojektuj efektywny algorytm działający w miejscu, który dla zadanych dodatnich liczb całkowitych \(m < n\) i \(k < 2026\) obliczy ile jest par (i,j) takich, że \(1 \le i < j \le n\), \(j \le i+m\) oraz \(|a[i] - a[j]| = k\).

Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.