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.