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