Kreczmar – Dzień 4

Omówienie zadań 2006-07-23
Dzień 4

1. Rysio budowniczy

Sprawdzić czy dany na wejściu graf jest planarny.

Złożoność: O(n)
Klasa: algorytmy grafowe

G(V, E)
|E|<=3*|V|-6

Podgrafy Kurakowskiego (odsyłam na wikipedie).

Wszystkie mosty możemy usunąć.

Zmieniamy graf za pomocą DFS na palmę (?). Wszystkie rozgałęzienia DFS traktujemy jako liście. Pamiętamy też drogi powrotu. Następnie zmieniamy numeracje (od korzenia do liści). Następnie używamy DFS po raz kolejny żeby podzielić graf na segmenty. Segment to zbiór ścieżek z drogą powrotną, tworzący cykl. Dla każdego wierzchołka trzymamy najgłębszy element powrotu. Umieszczamy kolejno segmenty. Za każdym razem sprawdzamy czy umieszczony segment koliduje z poprzednimi. Jeśli tak, to umieszczamy drogę powrotną po drugiej stronie. Krawędzie można umieszczać metodą zachłanną, ale nie jest to metoda najoptymalniejsza.

Algorytm Hopcroft i Tarjan (1974)
(wykładowca odsyła do googli)

2. Trójkąty

Dany jest zbiór punktów. Znajdź trójkąt o największym polu, którego wierzchołki są punktami.

Złożoność: O(n*lgn)

Sprawdzenie wszystkich możliwości zajmie O(n^3), co jest zbyt duże dla danych w teście. Pierwszym krokiem do optymalniejszego rozwiązania problemu, jest obliczenie wypukłej otoczki. Dalej bierzemy tylko punkty na otoczce. Jeśli będziemy rozpatrywali dla wszystkich punktów trójkąt spamiętując od którego punktu należy zaczynać, otrzymamy rozwiązanie o złożoności O(n^2).

Algorytm liniowy, na początku wygląda tak samo jak w kwadratówce. Trik polega na tym, że przesuwamy wszystkie punkty zgodnie ze wskazówkami zegara, tak żeby zwiększać pole. Jeśli nie jest to możliwe przesuwamy 2 punkt.
(nie wiadomo dlaczego miałoby to działać)

Kreczmar Dzien 3

Omowienie zadan 2006-07-22
Dzien 3

1. Najwiecej Radosci

W grafie znalezc droge o dlugosci dokladnie M krawedzi, taka zeby sumaryczny koszt byl jak najwiekszy.

Chociaz zadanie z pozoru wydaje sie byc grafowe, wcale takim nie jest. Ograniczenia w zadania pozwalaja zastosowac macierz sasiedzctwa zamiast list sasiedztwa.

Teraz rozpatrujemy problem ogolniejszy, znajdujemy takie drogi pomiedzy kazda para wierzcholkow.

Tu nasuwa sie algorytm Belmana-Forda. Trzeba go iterowac tyle razy, ile ma miec dlugosc sciezka. Zeby zmniejszyc zlozonosc stosujemy algorytm optymalnego mnozenia macierz.

Zlozonosc: O(n^2*lgT)
Klasa: srednio grafowe (zgodnie z zyczeniem )

2. Gory

Znajdowanie najdluzszego podciagu nierosnacego w czasie O(n*lgn).
(mozna to znalezc w jakis madrych i fajnych ksiazkach).

Klasa: dynamik

Tutaj ten algorytm wystarczy zmodyfikowac, zeby oprocz dlugosci pamietal tez ciekawosc i wybieral sposrod sciezek o rownej dlugosci te ciekawsze.

(C++: sprytne zastosowanie map z STL)

3. Spalic sieci

Zadanie, w ktorym koncowy rezultat zalezal od tego co przyslali uczestnicy. Sprawdzanie Tomasza Kulczynskiego: O(n(n+n))

Omowienie 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)

Notatki z omowienia zadan 1 dzien

For those who don’t know Polish: Below are solutions to algorithm problems from 1st day of informatics training camp.

(brak polskich literek, notowane na szybko)

Omowienie zadan 2006-07-20
Latwe i trudne

Prowadzacy: Filip Wolski

(niestandardowa gadka)

Dzien probny:
1. Ciagi artmetyczne
Autor: Maciej Laszcz

Dany jest ciag liczb calkowitych i trzeba w nim znalezc najdluzszy podciag bedacy ciagiem artmetycznym.

Zlozonosc: O(n^2*lgn)
Klasa: dynamik

1 -2 3 5 -3 7

Dla kazdej kolejnej liczby sprawdzamy wszystkie poprzednie liczby tworzac mozliwe ciagi (2 elementowe). Liczymy roznice i dlugosc hipotetycznego ciagu. Oprocz tego patrzymy na te struktury i probujemy jakis ciag przedluzyc. Wyszukiwanie w tych strukturach przyspieszamy za pomoca wyszukiwania binarnego lub hashowania.

2. Sumowanie

Mamy permutacje liczb od 1 do n. Sumujemy sasiednie element tworzac nowy ciag o jeden mniej liczny. Tak postepujemy tak dlugo az ciag bedzie mial 1 element.

Np.

3 1 2 4
4 3 6
7 9
16

Klasa: sprytniejszy brut

Latwo zauwazyc podobienstwo tego problemu do trojkata pascala. Rownowaznoscia operacji w dzialaniu jest mnozenie poczatkowe ciagu z odpowiednimi wartosciami w trojkatu Pascala i sumujemy.
Trojkat pascala:

1
1 1
1 2 1
1 3 3 1

Przyklad mnozenia:
1*3+3*1+3*2+1*4

Korzystajac z tego faktu, sprawdzamy wszystkie mozliwosci w kolejnosci leksykograficznej.

Dzien 1:
3. Perly

aacca
bacac
baaaa
bbdda

Litery symbolizuja perly. Jas chce wyciac najdluzszy sznur z perel tego samego typu.
(FIXME: sznur ma grubosc 1 perly)

Trzeba zastosowac algorytm DFS. Nalezy chodzic tylko po tych samych perlach. Jesli dojdzie sie rozgalezienia (w szczegolnosci punkt poczatkowy), trzeba pamietac wyniki 2 najlepszych zapuszczen defesow i probowac je zlaczyc (ewentualnie dlugosci z ktorej przyszlismy).

2. Jas prawoskretny

Jas rozwozi pizze. W plaszczyznie 2 jest miasto i miejsca gdzie dostarczy pizze. Kazde 2 miejsca sa polaczono w lini prostej drogi. Jas nie lubi odwiedzac 2 razy tego samego miejsca, wiec tego nie robi. Znajdz trase ktora przechodzi przez wszystkie punkty i moze skrecac tylko w prawa strone (zgodnie z wskazowkami zegara).

Klasa: geometria obliczeniowa
Rozwiazanie: wypukla otoczka
Zlozonosc: O(n*lgn)

3. Pizza

Jas zaplacil za pizze i musi wydac reszte kolegom. W kraju kazdy nominal dzieli wszystkie wieksze.

Zlozonosc: O(n*k)

Wydawac kolejnym klientom w najwiekszych mozliwych nominalach. Uwagi implementacyjne: posortowac nominaly.
4. Kumple

Trzeba podzieli ludzi na 2 grupy, ktore bylyby je “jak najbardziej” rownoliczne. Problemem jest to ze czesc osob chce koniecznie byc z kims lub _nie zyczy_ sobie kogos widziec w tej samej grupie.

Klasa: grafowe i dynamik

Ten problem rozwiazujemy w dwoch etapach. W pierwszym rozpatrujemy niezalezne grupy (takie ktore nie maja miedzy soba relacji) w drugim laczymy grupy miedzy ktorymi nie ma relacji.

Latwo zauwazyc ze relacja przyjazni lub wrogosci jest wzajemna. Zakladamy dla pierwszej nieprzydzielonej osoby, ze nalezy do pierwszej grupy. Liczymy wszystkie konsekwencje. I postepujemu tak az wszystkie osoby beda przydzielone. Latwo zauwazyc ze przy kazdym razie gdy zakladamy ze ktos nalezy do grupy pierwszej to jest to niezalezna podzbior problemu. Latwo
zauwazyc ze mozemy “odwracac” przynaleznosci. Tworzymy tablice roznic (w liczebnosci).

Np.:

Res: value:0
Team 1: 1 6
Team 2: 5 4
Res: value:1
Team 1: 7
Team 2:
Res: value:2
Team 1: 2 3
Team 2:

Teraz ten problem rozwiazuje tak jak dyskretny problem plecakowy. Dynamicznie liczymy wszystkie mozliwosci i szukamy tego ktory najblizszy by liczbie polowy sumy wszystkich roznic.

5. Odzysk
(FIXME: nie dokonca zrozumialem Filipa Wolskiego, jesli ktos ma cos lepszego to niech przysle)

Probujemy odzyskac ciag. Mamy dane mozliwe wartosci w ciagu i liczby:
a1,a1+a2, … , a1+a2+…+an-1+an
an+an-1+…+a1, an-1+…+a1, … , a1
w dowolnej kolejnosci.

Sortujemy wszystkie liczby i patrzymy czy sumujac dowolne dwie rozne liczby rowno odalone od srodka daja ta sama sume. Jesli nie to nie istnieje taki ciag.

Majac te pary probujemy je wstawiac od zewnetrznych do dwoch wejsciowych ciagu. Sprawdzamy wszystkie mozliwosci. Jesli znajdziemy poprawna to odtwarzamy pierwotny ciag z wejsciowych ciagow.

Zlozonosc: O(n^2)