2. Klasówka 2021/22 (13.01.2022)
================================

Zadanie 1 [6 punktów]
---------------------

.. index:: amortyzacja

W tym zadaniu analizujemy grę polegającą na układaniu żetonów na nieskończonej,
jednowymiarowej planszy, której pola ponumerowano kolejno
:math:`\ldots, -2, -1, 0, 1, 2, \ldots`.
Jedno posunięcie w grze polega na wybraniu pola i położeniu na nim jednego żetonu.
Jeśli po położeniu żetonu okaże się, że na dwóch sąsiednich polach umieszczono tyle
samo żetonów (co najmniej po jednym), to przenosimy wszystkie żetony z jednego z tych pól
na drugie, czyszcząc pierwsze pole i podwajając liczbę żetonów na drugim polu.
W przypadku, gdy mamy możliwość wyboru dwóch sąsiednich pól dokonujemy takiego wyboru
arbitralnie. Następnie kontynuujemy opisany proces czyszczenia pola i
podwajania liczby żetonów na polu sąsiednim do momentu, w którym na dwóch sąsiednich
polach nie będzie tyle samo żetonów (przy czym jedno z nich musi zawierać co najmniej 1 żeton).

**Przykład**

Załóżmy, że na polach o numerach 1, 2, 3, 4, 5 znajduje się odpowiednio 0, 1, 2, 4 i 6 żetonów.
Po dołożeniu na pole o numerze 1 jednego żetonu dostaniemy następujący układ żetonów na planszy:
0, 0, 0, 8 i 6.
Elementarny ruch w grze polega na położeniu lub zdjęciu żetonu.
Zatem przeniesienie k żetonów z pola na pole wymaga wykonania k operacji zdjęcia
żetonu z planszy i k operacji położenia żetonu na planszy.
Dokonaj analizy kosztu zamortyzowanego jednego posunięcia w grze mierzonego
liczbą ruchów elementarnych.

.. hint::
   :class: dropdown

   Obserwacje:

   * maksymalna wysokość stosu po *n* operacjach to *n*
   * każdy element, który jest przekładany trafia na stos dwa razy większy,
     stąd przy *n* operacjach każdy żeton może zostać przełożony co najwyżej :math:`\log_2 n` razy
   * czyli zamortyzowany koszt pojedynczej operacji to :math:`O(\log n)`


Zadanie 2 [7 punktów]
---------------------

.. index:: struktury danych, wzbogacanie

W tym zadaniu rozważamy dynamiczny, różnowartościowy ciąg liczb całkowitych C.
Na ciągu C wykonujemy operacje:

* Ini(C):: C := [] // inicjacja ciągu pustego - tylko raz, na początku wykonywania
  wszystkich operacji
* Insert(C,x,i):: wstaw element x na pozycję i w ciągu C, :math:`1 \le i \le |C|+1`
  //możesz przyjąć, że x nie ma w ciągu C
* Delete(C,i):: usuń i-ty element z ciągu C, :math:`1 \le i \le |C|``
* Sorted(C,i,j):: sprawdź, czy podciąg :math:`C_i, C_{i+1}, \ldots, C_j`
  jest uporządkowany rosnąco,
  :math:`1 \le i \le j \le|C|`
* BSComp(C,i,j):: sprawdź, czy elementy :math:`C_i` oraz :math:`C_j`
  (:math:`1 \le i \le j \le|C|`)
  byłyby porównywane ze sobą w pierwszym przebiegu sortowania tablicy
  :math:`a[1..|C|] = [C_1, C_2, \ldots, C_{|C|}]` algorytmem BubbleSort:

.. code-block::

    for k = 1, 2, ..., |C|-1 do
        if a[k] > a[k+1] then a[k] :=: a[k+1]; //zamiana wartości zmiennych

Zaproponuj strukturę danych umożliwiającą wydajne wykonywanie powyższych operacji.

.. hint::
   :class: dropdown

   Wzbogacamy drzewo dla dynamicznego ciągu (z operacjami Ini, Insert, Delete) o dodatkowe atrybuty:

   * isSorted
   * firstValue
   * lastValue
   * maxValue

   Elementy :math:`a[i]` i :math:`a[j]` (:math:`i < j`) są porównywane wtw, gdy: :math:`a[i] = \max(a[1..j-1])`



Zadanie 3 [7 punktów]
---------------------

.. index:: AVL

Dane jest AVL-drzewo T. Zaproponuj wydajny algorytm, który obliczy dla ilu węzłów
zewnętrznych w T, po wstawieniu w ich miejsce nowego elementu zostanie wykonana
pojedyncza rotacja, a dla ilu podwójna.
Uwaga: atrybutami węzła w drzewie są: klucz, lewy, prawy - wskaźniki do korzeni
odpowiednio lewego i prawego poddrzewa, wzr - współczynnik zrównoważenia; dostęp do
drzewa jest dany przez wskaźnik do jego korzenia.

**Przykład**

.. tikz::

    \tikzstyle{every node}=[circle, draw]
    \tikzstyle{every child}=[level distance=1cm]
    \tikzstyle{level 1}=[sibling distance=3cm]
    \tikzstyle{level 2}=[sibling distance=1.5cm]
    \node (tree) {10}
        child {
            node {5}
            child { node[rectangle] {A} }
            child {
              node {7}
              child { node[rectangle] {B} }
              child { node[rectangle] {C} }
            }
        }
        child {
            node {20}
            child { node[rectangle] {D} }
            child {
              node {30}
              child { node[rectangle] {E} }
              child { node[rectangle] {F} }
            }
        }
    ;

* *A* - 0 rotacji
* *B* - podwójna rotacja
* *C* - pojedyncza rotacja
* *D* - 0 rotacji
* *E* - podwójna rotacja
* *F* - pojedyncza rotacja

Wynikiem działania algorytmu będą w tym przypadku liczby 2 i 2 odpowiednio liczba węzłów
zewnętrznych, dla których zostanie wykonana pojedyncza rotacja i liczba węzłów zewnętrznych,
dla których zostanie wykonana podwójna rotacja.

.. hint::
   :class: dropdown

  TBD

W każdym zadaniu uzasadnij poprawność rozwiązania i dokonaj analizy złożoności
obliczeniowej zaproponowanych algorytmów.