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,

Leave a Comment

Name:
E-mail:
URI:
Enter this code: