Egzamin 2018/19 (29.01.2019)#

Zadanie 1 [6 punktów]#

Dane są dwie liczby całkowite dodatnie n i m oraz n+m domkniętych przedziałów liczb całkowitych - n przedziałów białych i m przedziałów czerwonych. Każdy przedział zadany jest jako para liczb wyznaczających odpowiednio lewy i prawy koniec przedziału. Wszystkie końce przedziałów są parami różne. Zaprojektuj efektywny algorytm, który oblicza liczbę par różnokolorowych przedziałów, w których przedział czerwony jest całkowicie zawarty w przedziale białym.

Zadanie 2 [14 punktów]#

Słowa kluczowe: teksty

W tym zadaniu rozważamy słowa zbudowane z cyfr 0, 1, …, 9. Każde takie słowo można traktować jako zapis w układzie dziesiętnym pewnej nieujemnej liczby całkowitej. Zaprojektuj efektywny algorytm, który dla danego niepustego słowa x:

  1. [3 punkty] obliczy liczbę wszystkich takich par indeksów (i, j), \(1 \le i \le j \le |x|\), że słowo x[i..j] jest zapisem liczby podzielnej przez 3;

  2. [4 punkty] wyznaczy taką parę indeksów (i, j), \(1 \le i \le j \le |x|\), że słowo x[i..j] jest zapisem największej liczby podzielnej przez 3 wśród wszystkich podsłów słowa x;

  3. [7 punktów] obliczy liczbę wszystkich parami różnych podsłów (różniących się długością lub znakami na odpowiadających sobie pozycjach) słowa x będących zapisami liczb podzielnych przez 3

Podpowiedź

  1. Sumy prefiksowe cyfr (mod 3). Liczbę par można otrzymać przechodząć wartości sum prefiksowych i zliczając ile prefiksów ma sumę 0, 1, 2.

  2. Analogicznie jak a) + dla każdej pozycji j wyznaczamy najdłuższego kandydata $(i, j)$ (bez wiodących zer) następnie wybieramy najdłuższe słowo, jeśli jest więcej to wybieramy największe leksykograficznie. Sortowanie słów za pomocą drzewa sufiksowego.

  3. Drzewo sufiksowe + programowanie dynamiczne.

Zadanie 3 [6 punktów]#

Słowa kluczowe: wzbogacanie

Niech S będzie dynamicznym, skończonym zbiorem liczb całkowitych, każda pokolorowana na biało lub czerwono. Początkowo zbiór S jest pusty, a następnie wykonujemy na nim ciąg operacji postaci:

  • Insert(x,k): wstaw do S element x o kolorze k;

  • Delete(x,k): usuń z S element x koloru k;

  • Gap(): funkcja której wartością jest minimalna wartość bezwzględna różnicy dwóch różnokolorowych elementów w zbiorze S lub -1, gdy w S nie ma elementów o różnych kolorach.

Zaprojektuj efektywną strukturę danych dla zbioru S.

Podpowiedź

Drzewo zrównoważone wzbogacone o atrybuty: minGap (w podrzewie), min/max element (w poddrzewie), secondMin/secondMax (w poddrzewie ale o innym kolorze niż min/max).

Zadanie 4 [14 punktów]#

Słowa kluczowe: grafy

Niech a[1..n+2] będzie tablicą liczb całkowitych z przedziału [1, n], dla pewnego dodatniego n. Grafem \(G_a\) nazywamy nieskierowany graf \((V,E)\), w którym \(V = \{1, 2, \ldots, n\}\), natomiast \(E = \{ i—j : i \ne j\ \mbox{oraz}\ \{a[i], a[i+1], a[i+2]\} \cap \{ a[j], a[j+1], a[j+2]\} \ne \emptyset\}\).

  1. [2 punkty] Jaka może być maksymalna wysokość DFS-drzewa w grafie Ga o korzeniu w wierzchołku 1?

  2. [2 punkty] Jaka może być maksymalna wysokość BFS-drzewa w grafie Ga o korzeniu w wierzchołku 1?.

  3. [2 punkty] Udowodnij, że graf Ga jest dwuspójny wierzchołkowo (jest spójny i nie zawiera wierzchołków rozdzielających).

  4. [8 punktów] Przyjmijmy, że wagą krawędzi i—j jest wartość najmniejszego elementu w zbiorze \(\{a[i], a[i+1], a[i+2]\} \cap \{a[j], a[j+1], a[j+2]\} \ne \emptyset\}\). Zaprojektuj efektywny algorytm, który dla danej tablicy a oblicza wagę najlżejszego drzewa rozpinającego dla grafu Ga.

Uzasadnij poprawność swoich rozwiązań i przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów.