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.
wersja strony: 5, ostatnia edycja: 28 Feb 2013 19:17