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<=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,
CV & Resume
del.icio.us
Top Coder