3 ostatnie dni

Omówienie zadań i wykładu 2006-07-25
Dzień 6

1. Podciągi

Mamy dane dwa ciągi liter. Mamy znaleźć najkrótszy niewspólny podciąg.

ababa
abbab

Bierzemy ostatnią literę ciągu pierwszego i szukamy jej ostatniego występowaniu w ciągu drugim. Wtedy problem sprowadzamy do znalezienia najkrótszego wspólnego ciągu pomiędzy pierwszym zmniejszonym o jeden i drugim zmniejszonym do ostatniego wystąpienia tej litery.

Teraz liczymy tą metodą dynamicznie dla każdego prefiksu ciągu pierwszego.

Klasa: dynamik
Złożoność: O(n^2)

2. Bajtocji

Dane są wektory. Znajdź sumę wektorów, która jest “najdłuższa”.

Sortujemy wektory po kątach. Opłaca się dodawać wektory tylko takie które będą odchylone o 90 i mniej stopni od wektora wypadkowego. Kolejno rozpatrujemy półpłaszczyzny, których oś przechodzi przez ośrodek układu współrzędnych. Rozpatrujemy półpłaszczyzny, dla każdego wektora i ćwiartek układu współrzędnych.

Klasa: geometria obliczeniowa

3. Gra

Gra słupkowa. Jest n słupków na każdym ai kamieni. Gracze kolejno biorą dowolna niezerową naturalną liczbę kamieni o najwyżej k kolorach.

Grę tę można sprowadzić do gry nim. W nimie sytuacja jest przegrana gdy xor liczb jest równy 0.

Reprezentujemy liczby kamieni w postaci binarnej i zliczamy wszystkie jedynki na tych samych pozycjach. Jeśli istnieje conajmniej jeden wiersz w którym liczba jedynek nie jest podzielna przez k+1, istnieje strategia wygrywająca. Trzeba teraz wykonać ruch który zmieni sumę jedynek tak aby każda była podzielna przez k+1.

Istnieje problem jak znaleźć ruch wygrywający. Szukamy nastarszego bitu, których liczb nie jest podzielna prze k+1. Jeśli zamienimy ten bit na 0 to możemy ustawić bity młodsze dowolnie.

Klasa: teoria gier
Złożoność: O(n*k) k -> ilosc różnych bitów

Wykład do zadania trójkat

Mamy dany zbiór punktów. Chcemy znaleźć trójkąt o najwiekszym polu, którego wieszołki są na danych punktach.

Odrzucamy punkty, które nie są na otoczce wypukłej.

Lemat 1:
Każdy trójkąt lokalnie najlepszy przecina trójkąt globalnie najlepszy.

(TOLEARN: wyszukiwanie ternalne)

Omówienie zadań i wykład 2006-07-27
Dzień 7

1. Wstążki

Mamy dany podzielony materiał i chcemy podzielic go na n możliwie największych kawałków.

Rozwiązanie: wyszukiwanie binarne

2. Wycieczka

Mamy daną szachownicę n*4. Należy obliczyć na ile sposobów można dojść z lewego górnego pola do lewego dolnego, nie przechodząc żadnego pola dwa razy.

Próbujemy wyprowadzić wzór rekurencyjny
An+1 = An+2Bn+2Cn+Dn+En+1
Bn+1 = An+2Bn+2Cn+Dn+En+1
Cn+1 = An+Cn+Bn+Fn+1
Dn+1 = An+2Bn+Dn+1
En+1 = 2Cn+En+q
Fn+1 = An+Fn
Znając te wzory można napisać rozwiązanie o złożoności O(n). Rozwiązanie w czasie logarytmicznym można otrzymać stosując macierz.

An
Bn
Cn
Dn
En
Fn
1
=
1 2 2 1 1 0 1
1 2 1 1 0 0 1
1 1 1 1 0 0 1
1 2 0 1 0 0 1
0 0 2 0 1 0 1
1 0 0 0 0 1 0
0 0 0 0 0 0 1
*
v1

v1 = M*v0
vn = Mn*v0

Teraz problem ten można sprowadzić do mnożenia macierzy w czasie O(lgn). Korzystamy z łączności mnożenia.

Wykład:
String matching

x[1..m] – wzorzec
y[1..n] – tekst
n>m
szukamy wzorca w tekście
1. Algorytm naiwny.
2. KMP

P[0] = -1; t = -1;
for i=1 to n
while t>=0 and x[t+1] != x[i]
t=P[t];
t++; P[i] = t;

i = 0; j = 0;
while i<=n-m
while j&lt=m and x[j+1]==y[i+j]
j++;
if j==m then return WYSTAPIENIE;
shift = j-P[j];
i=i+shift; j=max(0, P[j]);

Zadanie szablony z OI:
liczymy P[] ….

repeat forever
read(symbol)
while j>-1 and x[]
j = P’[j]
if j==m
write 1
j=P(m)
else
write 0

Omówienie zadań z zawodów drużynowych 2006-07-29

1. Jasnowidz
2. Mecz
łatwe

3. Przedziały
Mamy dane przedziały. Znaleźć najdłuższy ciąg przedziałów się zawierających.

Sortujemy względem początków, a dalej jak zadanie góra na poprzednim contesteście.

4. Drugi

Znajdź drugi po największym elemencie porównań. Mamy ograniczoną liczbę porównań.

Rozwiązanie: drzewo turniejowe.

5. Rozwiązywanie gier

Stany gry reprezentuja wierzchołki. Krawędzie możliwe ruchy. Dwóch graczy wykonuję na przemian ruchy. Przegrywa ten który nie może wykonać ruchu.

Przeliczamy dla każdego wierzchołka w ilu ruchach można wygrać lub przegrać. Wykonujemy to tablicując grę od tyłu.

6. Hodowcy drzew

Mamy dwa ciągi określone wzorem rekurencyjnym.

a0 = 1;
b0 = 0
an+1 = 3*an+bn
bn+1 = 5*an

Mamy policzyc wartości an, i bn mod 1000000 dla bardzo dużych n (1000000 cyfr). Nawet korzystając z macierzy czas rozwiązania nie być akceptowalne.

Va = 10^18
exist a,b a Va = VB
Va+1 = Mv1%10^9
VB+1 = Mv0%10^9
Va+k = VB+k
Va+(a)%T = Vn
T = b-a

a) v1, v2, v3 …
v(2^r)
O(b)
b)Vn = V2n
O(b)
c) a<20

T=3*10^8
T=3/10*D

7. Drogi jednokierunkowe

Mamy dany graf z krawedziami jednokierunkowymi i dwu.

Znajdz maksymalna liczbe krawedzi, ktore mozna zamienic z dwukierunkowych na jednokierunkowe, aby silna spojnosc krawedzi byla zachowana.

Jedyne krawedzie których ukierunkować się nie da to mosty.

Etapy algorytmu:
a) znajdujemy mosty,
b) krawędzie kierujemy DFS takie, które można przejść tylko w jedna stronę,
tzw. nie da się dojść do tego miejsca w inny sposób,

Dzień 5 omówienie i wykład

Omówienie zadań i wykład 2006-07-24
Dzień 5

1. Kwadrat

Dla danego ciągu liczb naturalnych. Znajdź jak najdłuższy spójny podciąg, którego iloczyn daje kwadrat liczby całkowitej.

Rozkład wszystkich liczb na czynniki pierwsze. Jeśli suma wystąpień wszystkich czynników jest parzysta, to na pewno dany iloczyn jest dobry.

Liczymy dla każdego prefiksu, bitowe odwzorowania parzystości iloczynu tego prefiksu. Sortujemy te prefiksy i szukamy powtórzeń. Wybieramy, te prefiksy których różnica długości jest największa.

Złożoność: O(n*m) m – liczba liczb pierwszych

2. Dinozaury

Mamy daną siatkę z płotami. Liczymy ile jest zamkniętych obszarów.

Rozwiązanie a:
DFS lub BFS przechodzimy całą planszę i szukamy ile razy musimy wywoływać po raz ponownie funkcję. Jest to ilość zamkniętych obszarów. Rozwiązanie jest to trudne w implementacji z uwagi na pamięć.

Rozwiązanie b:
v – liczba wierzchołków
e – liczba krawędzi
f – liczba ścian
Wzór Eulera: (działa dla grafów planarnych)
v+f = 2+e

Żeby wyeliminować problem obszarów otwartych do boków umieszczamy wszystko w dużym równoległoboku i na końcu odejmuje 1 od liczby ścian.

3. Przekładanie kart

Mamy talie kart. Karta to liczba. Przekładamy karty w specyficzny sposób. Karty są stopniowo układane na stos, tak aby suma punktów na stosie była jak najczęściej podzielna przez 100.

Permutacje kart, można wyrazić jako skok pomiędzy kolejnymi elementami.

Jakiś trik z policzeniem optymalnego przełożenia dla prefiksów, a potem dynamicznie liczyć rozwiązania dla dłuższych podciągów.

Wykład:
1. Algorytm Shella (sortowanie).
O złożoności: O(n*lg^2(n))
2. Grafy planarne
Graf planarny to graf płaski, który można narysować bez przecięć.
n – liczba wierzchołków
m – liczba krawędzi
3f=2n
n+2/3m>=k
m>=3n-6
Fakty:
a) każdy graf planarny ma wierzchołek stopnia mniejszego ni? 5,
b) każdy graf planarny jest 5 kolorowalny,
c) graf K5, K3.3 nie są grafem planarnymi i nie są homograficznymi podgrafami grafu planarnego,

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