Egzamin poprawkowy 2020/21 (26.02.2021)#

Zadanie 1 [18 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie, Find-Union

Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie ciągu następujących operacji na słowie zero-jedynkowym o długości \(n > 0\):

  1. [10 punktów]

    1. \(Ini(<b_1, b_2, \cdots, b_n>) ::\) utwórz strukturę danych reprezentującą słowo \(b\); ta operacja jest wykonywana tylko raz, na samym początku.

    2. \(Zam(i: 1..n) :: b_i := 1 - b_i\).

    3. \(Blok(i: 1..n) ::\) podaj długość maksymalnego podsłowa \(<b_j,b_{j+1}, \cdots, b_k>\) złożonego z jednakowych symboli i takiego, że \(j \leq i \leq k\).

  2. [8 punktów]

    1. \(Ini(<1, 1, \cdots, 1>) ::\) utwórz strukturę danych reprezentującą słowo \(b\) złożone z samych \(1\); ta operacja jest wykonywana tylko raz, na samym początku.

    2. \(Zam(i: 1..n) ::\) if \(b_i = 1\) then \(b_i := 1 - b_i\).

    3. \(Najblizsza(i: 1..n) ::\) podaj największą pozycję \(1\) w słowie \(b\) na lewo od \(b_i\); jeśli takiej pozycji nie ma, to wynikiem jest \(0\).

Podpowiedź

  1. Drzewo przedziałowe o n liściach. Każdy liść utrzymuje informację o kolorze. Każdy węzeł wewnętrzny utrzymuje atrybuty: czyOdwrócony (czy należy odwrócić kolory w poddrzewie), dłPref (długość jednokolorowego prefiksu), dłSuf (długość jednolorowego sufiksu). Wszystkie atrybuty możemy aktualizować w czasie O(1) na podstawie informacji z poddrzew. Blok sprowadza się do znalezienia długości jednokolorowego bloku przechodzącego przez i. Złożoność operacji Zam i Blok to \(O(\log n)\).

  2. Zadanie można rozwiązać przy użyciu struktury Find-Union. Każdy zbiór reprezentuje fragment słowa b postaci: \(1 0^*\). Modyfikujemy strukturę, tak by zawsze pamiętała minimalny indeks każdego zbioru. Zam(i) powoduje scalenie dwóch sąsiednich zbiorów.

Zadanie 2 [10 punktów]#

Słowa kluczowe: grafy

Grafem trójkątnym nazywamy graf spójny, w którym każda dwuspójna składowa jest trójkątem (cyklem długości 3). Mamy dany graf trójkątny reprezentowany przez listy sąsiedztwa.

  1. [7 punktów] Zaprojektuj algorytm, który w czasie liniowym obliczy dla tego grafu liczbę różnych cykli Eulera modulo 2021. Przyjmujemy, że każdy cykl Eulera jest zadawany przez ciąg kolejno odwiedzanych wierzchołków. Dwa ciągi takie same z dokładnością do przesunięcia cyklicznego definiują ten sam cykl.

  2. [3 punkty] Ile jest różnych cykli Eulera w grafie trójkątnym zawierającym dokładnie 1 wierzchołek rozdzielającym i n trójkątów?

Zadanie 3 [12 punktów]#

Zaproponuj efektywny algorytm, który dla danej permutacji \(p = <p_1, p_2,\cdots, p_n>\) liczb \(1, 2, \cdots, n\) policzy liczbę malejących trójek \(<p_i, p_j, p_k>\), dla \(1 \leq i < j < k \leq n\).

Podpowiedź

Zadanie można rozwiązać za pomocą drzew przedziałowych w czasie \(O(n\log n)\). To jest prostsza wersja zadania k-Inwersje (z k=3).