2. Klasówka 2015/16 (14.01.2016)#
Zadanie 1 [2+3+5 = 10 punktów]#
Dla dodatniej liczby całkowitej n, kratownicą \(n \times n\) nazywamy graf o \(n^2\) wierzchołkach i \(2n(n-1)\) krawędziach, którego wierzchołki można poetykietować parami liczb (x,y), dla x=1,2, …, n i y=1,2, …, n, w taki sposób, że wierzchołek (x,y) jest połączony (sąsiaduje) z wierzchołkami: (x-1,y), (x+1,y), (x,y-1) oraz (x,y+1), o ile tylko sąsiad o takiej etykiecie istnieje. Oto przykład kratownicy 3x3:
Policz ile jest różnych drzew BFS w kratownicy 3x3 o korzeniach w wierzchołkach stopnia 2.
Policz ile jest różnych drzew DFS w kratownicy 3x3 o korzeniach w wierzchołkach stopnia 2.
Przyjmijmy, że dana jest dodatnia liczba całkowita n oraz lista 2n(n-1) krawędzi pewnego grafu, którego wierzchołki poetykietowano liczbami całkowitymi od 1 do \(n^2\). Zaproponuj algorytm, który w czasie liniowym stwierdzi, czy dany graf jest kratownicą \(n \times n\).
Uwaga: dwa drzewa BFS (DFS) się różnią, jeśli istnieje wierzchołek o różnych ojcach w tych drzewach; na potrzeby tego zadania BFS-drzewo, to drzewo najkrótszych ścieżek prowadzących do korzenia.
Podpowiedź
Warunek konieczny ale nie wystarczający: stopnie wierzchołków muszą odpowiadać wierzchołkom kraty (4 wierzchołki stopnia 2, 4(n-2) wierzchołków stopnia 3, \((n-1)\cdot(n-1)\) wierzchołków stopnia 4)
sprawdź czy stopnie wierzchołków są zgodne z powyższym warunkiem
zbuduj podgraf złożony tylko z wierzchołków stopnia 2 i 3 i sprawdź czy tworzy cykl długości 4(n-1)
wierzchołki stopnia 2 odpowiadają rogom, wierzchołki stopnia 3 odpowiadają bokom
nadaj wierzchołkom z cyklu współrzędne na kracie
nadawaj kolejnym wierszom wierzchołków współrzędne
gdy wszystkie wierzchołki otrzymały współrzędne na kracie, sprawdź czy krawędzie są zgodne z kształtem kraty.
Zadanie 2 [5+5 = 10 punktów]#
Niech A będzie skończonym, dynamicznie zmieniającym się ciągiem, którego elementami są liczby ze zbioru {-1,0,1}. Podciąg kolejnych elementów A nazwiemy dobrym, gdy jego suma jest równa zero. Podciąg jest super-dobry, gdy jest dobry i suma elementów w każdym jego prefiksie jest nieujemna.
Przykład: W ciągu A = [1,1,0,-1,0,0,1,-1,1,1,-1], podciąg -1,1,1,-1 jest dobry, ale nie super-dobry. Super-dobrym podciągiem jest na przykład 1,0,-1.
Zaproponuj algorytm, który w czasie liniowym obliczy długość najdłuższego super-dobrego podciągu danego ciągu A.
Zaproponuj strukturę danych, która pozwoli na wydajne wykonywanie następujących operacji na A:
Ini(A):: A := []; //wykonywana tylko raz, na początku
Wstaw(A,e,i):: wstaw nowy element e jako i-ty w A, \(1\le i \le |A|+1\);
Usuń(A,i):: usuń i-ty element z A, \(1\le i \le |A|\)
SuperDobry(A,i,j):: sprawdź, czy podciąg A[i..j] jest super-dobry, \(1\le i \le j \le |A|\);
W każdym zadaniu uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.