28.02.2013

Teoria grafów w zadaniach:

1. Metro z II etapu XIII Olimpiady Informatycznej:

• Definicja średnicy drzewa i sposób wyznaczenia.
• Zadanie treningowe: Średnica drzewa (UWAGA NA ZŁOŚLIWY LIMIT PAMIĘCIOWY)
• Omówienie rozwiązania wzorcowego.
• Trik z usuwaniem listy sąsiedztwa.

2. Kości z II etapu XII Olimpiady Informatycznej:

• Sformułowanie zadania w teorii grafów.
• Nadanie krawędziom losowych orientacji.
• Startowanie z wierzchołka o maksymalnym stopniu wyjściowym i znajdowanie z niego drogi do dowolnego wierzchołka, którego stopień jest co najmniej o 2 mniejszy.
• Zamiana orientacji wszystkich krawędzi na tej ścieżce.

3. Stacja z finału XV Olimpiady Informatycznej:

• Wyjaśnienie treści zadania i specyfikacji I/O.
• Rozmiar poddrzewa: dla danego wierzchołka rozmiar jego poddrzewa wynosi: 1 (on sam) + suma rozmiarów poddrzew wszystkich jego synów.
• Aktualizacja rozmiarów poddrzew w czasie stałym podczas zmiany korzenia z A na B (B jest sąsiadem A):
• ROZMIAR[A]=N-ROZMIAR[B], ROZMIAR[B]=N. (WAŻNA KOLEJNOŚĆ!!!)
• Przechodzenie grafu algorytmem DFS i liczenie wyników dla kolejnych proponowanych stacji.

4. Inspekcja z finału XVIII Olimpiady Informatycznej:

• Wyjaśnienie treści zadania wraz z specyfikacją IO.
• Warunek istnienia rozwiązania dla określonego wierzchołka: maksymalne poddrzewo (oczywiście nie licząc korzenia) <= (n-1)/2 +(n-1)%2.
• WAŻNE: WIERZCHOŁKI MOŻNA USTAWIĆ W PORZĄDKU PREORDER. Wtedy poszczególne przedziały reprezentują listę potomków danego wierzchołka.
• Bardzo przyjemne zadanie: Megalopolis z II etapu XIV Olimpiady Informatycznej.
• Aktualizacja odległości wierzchołków od korzenia przy zmianie korzenia z A na B:
• Dla wierzchołków z przedziału: < czas_wejścia[B],czas wyjścia[B] ) odległość zmniejsza się o 1. Dla pozostałych zwiększa się o 1.
• Zastosowanie Drzewa Przedziałowego typu (+.max), do aktualizacji odległości.
• Drzewo PLUSMAX jest przydatne, dlatego polecam zadanie Koleje z I etapu IX Olimpiady Informatycznej.
• Wzór na wynik: 2* (suma wszystkich odległości) - maksymalna odległość.
• Złośliwy przypadek, gdy 2* (maksymalne poddrzewo) >=(n-1). Wtedy maksymalną odległość wyciągamy tylko z wierzchołków należących do maksymalnego poddrzewa.
• Ciekawy lemat ułatwiający rozwiązanie: Rozwiązanie istnieje dla co najwyżej dwóch wierzchołków.
• Mały haczyk ,który zabiera punkty: Maksymalny rozmiar poddrzewa liczymy tylko przy wchodzeniu do wierzchołka, NIGDY przy wracaniu z jego syna. Taki błąd zmienia złożoność na kwadratową.

5. Kody z wykładu:

• Implementacja wszystkich zadań z wykładu.
• Drzewo PlusMax (zwiększ przedział,maksimum z przedziału).
• Drzewo PlusPlus (zwiększ przedział, suma z przedziału).
• Rozwiązanie zadania Średnica Drzewa, które omija złośliwy limit pamięciowy,

6. Zadanie Domowe: OSADNICY Z CATANU

• Podpowiedź: pomyśl ,dla jakiego testu wynikiem jest n-1.