CV & ResumeOmowienie zadan 2 dzien
Omowienie zadan 2006-07-21
Dzien 2
Zadania trudniejsze
1. Hydraulik
Obracanie rur tak, zeby sie nic nie wylewalo.
Przeksztalcamy klocki na male grafy.
zakonczenie -> 1 wierzcholek i 4 krawedzie
…
“Tworzymy” z planszy szachownice pomalowana na dwa kolory. Wierzcholki malujemy na kolor taki na jakim polu stoi lub owrotnie (jeden wierzcholek I-). Wtedy laczymy przeciwstawne kolory. Dalej tworzymy graf dwudzielny stosujac maksymalne skojarzenie. W kazdym grafie wszystkie nieskojarzone krawedzi sa rurami. Jesli nie istnieje pelne maksymalne skojarzenie to zadanie to nie ma rozwiazania.
Zlozonosc: O( (n+k)*sqrt(n) ) n -> ilosc pol, k -> ilosc krawedzi
Klasa: algorytmy grafowe
(TODO: zalaczyc rysunek)
2. Polaczenia
Mamy dana prostokatna plansze. Kazde pole moze miec wartosci ‘*’, 0, 1, 2, 3, 4. Niektore pola maja byc polaczone z sasiednimi polami (gora, dol, prawo, lewo). Te z cyframi maja miec dokladnie tyle sciezek jaka wartosc. ‘*’ moze miec 0 sciezek lub 2 i wiecej.
Zakladamy ze mamy czesc wierszy rozwiazanych. Jedyne co potrzebujemy wiedziec o tych wierszach to z jakich miejsc wychodza sciezki na “zewnatrz”. Probujemy rozwiazac jedno sasiednie pole w ponizszym wierszu. Tak postepujemy az zapelni sie caly wiersz i tak dalej do konca.
Na koncu zeby otrzymac cofamy sie odtawarzajac najlepsze rozwiazanie:
Streszczenie: przegladanie wszystkich mozliwosci z spamietywaniem, tak zeby sie nie cofac
Zlozonosc: O(2^m*nm) m -> liczba kolumn, n -> iczba wierszy
Klasa: dynamik
3. Dzialki trojkatne
Dla danego zbioru punktow, znajdz liczbe trojkatow, ktore zawieraja dokladnie 3 punkty, z ktorych kazdy jest w wierzcholku. 2 dowolne punkt nie pokrywaja sie
Dla kazdego punktu sortujemy pozostale wzgledem katow, potem sprawdzamy wszystkie mozliwe trojkaty zawierajace te wierzcholki. Sprawdzamy czy jakis inny go “blokuje”. “Blokuje” czyli ostatni punkt jaki tworzy trojkat jest zawarty w rozpatrywanym nastepnym trojkacie.
Klasa: geometria obliczeniowa
Zlozonosc: O(n^2*lgn)
del.icio.us
Top Coder