Olympiad in Informatics

I’ve just returned¹ from the final stage of Olympiad in Informatics(OI). I scored 14th place² which gave me a title of laureate. It’s a really high position, because it is the hardest algorithm competition at a high school level. This post is a brief summary of my thoughts about it.

Background

Although that the Polish education system has its drawbacks, there is a definitely positive thing. The Olympiads. In fact it’s hard to translate this term into English. By “Olympiad” I mean a national competitions from different subjects for a high school students. In contrast to normal competitions, they are organised by the most prestigious Universities. This series of competitions require far more knowledge and skills than is normally taught at school. It’s a kind of motivation for students to learn more than it’s in official program.

Competition

OI is slightly different than the rest of the Olympiads. It consist mainly of algorithm problems. The objective is simple, write a program that will calculate the answer for given input within time and memory limits. For example, for a given graph find the route that has length exactly k. Judging is totally automatic. A score is evaluated based on how many of the tests your program has passed correctly. Unlikely the other algorithm competitions, the most important aspect is thinking rather than coding. The contest is divided into two sessions, each of it lasts 5 hours and include only 2-3 problems, so finding an optimal solution is the crucial part.

Place

The another reason why OI stands out is a location of the finals. Most of the Olympiads choose an academic city, while the OI 3rd stage is in a awesome coast resort – Sopot. Thanks to one of the sponsors, Combidata, we were accommodated in a training centre. It’s situated near the sea. Although in spring it’s too cold to swim, it’s truly pleasure to walk on the sand.

People

What’s really important is the people. It’s one of my few possibilities to talk about technical issues. Wanting a short discussion about various garbage collectors? Or a short talk about open source licensing? During the finals we have opportunity to meet/talk about almost all of the programming topics.

To give an image what’s sort of people are there, a short statistics:

Popular OS: linux flavour, mostly gentoo
Popular languages: C++ + a wide range of interpreted ones
Favourite (future) employer: Google
Other fields of interest: mathematics, physic + very odd one

Miscellaneous

At this competition I learned that I don’t exist ;-). I had a starting number 404 (HTTP not exist).

Results

To be honest, I dreamed about achieving a better result. I’ve made one genuinely silly mistake. I coded a constant value with one more zero than it was written in a problem set. It cost me a lot of points. On the other hand, I performed well enough to be almost on the top.

Summary

Preparation for OI took me long hours and many months of hard work, but it definitely worth it. Not only I learned many algorithms, but also I learned how to solve problems. It widen my mind, show new possibilities, give me a chance to meet new friends, etc. Although this contest concentrate on algorithm, it’s a good starting point to discover other branches of informatics.

1. In fact a week ago. I published the post with a delay. [back]
2. Results of Olympiad in Informatics 2007 [back]

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