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)