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ócenia 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].
[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.
[4 punkty] 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 \(\Omega(k \log k + n)\).
[5 punktów] Zaproponuj efektywny algorytm, który posortuje tablicę a, o której mowa w punkcie b), w czasie \(O(n \log k)\).
Podpowiedź
Gdzie w tablicy po jednym Revers są miejsca, w których a[i] > a[i+1]? Dolne ograniczenie: argument z przeciwnikiem - Revers(i, i+1) zamienia dwa sąsiednie elementy, więc każda para sąsiadów w porządku posortowanym musi zostać porównana.
Ile różnych tablic można dostać k operacjami Revers? Czy każdą permutację pierwszych k+1 elementów (każdy element można ustawić na miejscu jednym odwróceniem)? Drzewo decyzyjne daje \(\Omega(k \log k)\), a składnik n - argument z a).
O ile jedno Revers może zwiększyć liczbę miejsc, w których sąsiednie elementy nie są kolejne w porządku posortowanym? Podziel tablicę na maksymalne fragmenty monotoniczne - ile ich jest? - odwróć malejące i scal wszystkie kopcem.
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\}\).
[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\).
[4 punkty] Zaprojektuj strukturę danych, która umożliwia wydajne wykonywanie 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 i oraz j należą do tej samej silnie spójnej składowej.
[5 punktów] Zaprojektuj strukturę danych, która umożliwia wydajne wykonywanie 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ą.
Podpowiedź
Krawędź „do przodu” \(i\rightarrow j\) (i < j) nie tworzy cyklu, a krawędź „do tyłu” \(j\rightarrow i\) skleja wszystkie wierzchołki od i do j. Ile krawędzi potrzeba, żeby skleić wszystko, i jak dodać 1000 krawędzi bez tworzenia cyklu?
Silnie spójne składowe są zawsze przedziałami kolejnych wierzchołków. Krawędź \(j\rightarrow i\) skleja wszystkie przedziały przecinające [i, j]. Find-Union ze wskaźnikiem do następnej niesklejonej granicy - każda granica jest sklejana raz.
Krawędzie „do przodu” nigdy nie tworzą cyklu z linią. Pokaż, że i leży na cyklu wtedy i tylko wtedy, gdy któraś krawędź „do tyłu” \(j\rightarrow l\) spełnia \(l \le i \le j\). Licz takie krawędzie dla każdego i: dodawanie na przedziale, zapytanie o punkt.
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 $.
[3 punkty] Jaka jest najwyższa, a jaka najniższa wysokość drzewa sufiksowego dla tego rodzaju słowa o długości 6 (wliczając symbol $)? Uwaga: wysokość mierzymy liczbą krawędzi na najdłuższej ścieżce od korzenia do liścia, a nie długością etykiet na tej ścieżce.
[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.
Podpowiedź
Najwyższe: jakie słowo ma długie, zagnieżdżone powtórzenia (dużo wierzchołków wewnętrznych jeden pod drugim)? Najniższe: ile sufiksów może zaczynać się od tej samej litery, jeśli mają się rozejść tuż pod korzeniem?
Przykład: drzewo sufiksowe słowa aaaab$ ma wysokość 4 (w liściach numery pozycji, od których zaczynają się sufiksy):
To słowo nie daje ani najwyższego, ani najniższego drzewa - istnieją słowa długości 6, dla których drzewo sufiksowe jest wyższe, i takie, dla których jest niższe.
Które okna długości 2k są palindromami? Algorytm Manachera (promienie palindromów parzystych) albo haszowanie słowa i jego odwrócenia. Potem policz różne spośród nich: identyfikatory podsłów długości 2k (KMR, tablica sufiksowa albo haszowanie).
Zadanie 4 [8 punktów]#
[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\).
[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\).
Podpowiedź
Przesuwaj okno ostatnich m elementów i trzymaj liczności wartości w oknie. Dla a[j] potrzebujesz liczności a[j]-k i a[j]+k. Wartości nie przekraczają \(n^2\) - przenumeruj je sortowaniem pozycyjnym w czasie \(O(n)\) (albo użyj słownika), a wartość większą o k znajdź dwoma wskaźnikami.
Zakres wartości ma stałą wielkość - ile pamięci zajmuje tablica liczników wszystkich możliwych wartości? Dalej jak w a).
Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.