MOKIP 10.01.2013

I. Zliczanie inwersji

1. Inwersją w ciągu nazywamy każdą parę źle uporzadkowanych elementów.

mokip.graph2.JPG

2. Liczba inwersji waha się od 0 (w ciągu posortowanym) do O(n^2), więc sprawdzanie wszystkich możliwości jest średnio wydajne.

3. Inwersje można liczyć wykorzystując sortowanie przez łączenie (ang. mergesort).
Każde rekurencyjne wywołanie algorytmu zwraca liczbę inwersji w sortowanym przedziale.
Przy operacji łacznia, wstawiając liczby z drugiej połowy przedziału, dodajemu do liczby inwersji ilość niewstawionych jeszcze liczb z pierwszej połowy przedziału. Złożoność metody jest równa złożoności mergesort'a O(n log n)

4. Alternatywnym rozwiązaniem dla zliczania inwersji w permutacji (permutacja musi składać się z n kolejnych liczb i każdą zawierać tylko raz: np. 6 4 2 3 5 1, ale już nie 1 2 7 3 5 6) jest wykorzystanie drzewa przedziałowego:
Najpierw robimy dodaj(i,1) dla każdej pozycji i [0,n).
Nastepnie, dla każdej kolejnej liczby p[i] w permutacji dodajemy sumę z przedziału [0,p[i]) i wywołujemy dodaj(p[i],-1),aby usunąc liczbę ze "spisu".
Po n-1 iteracjach otrzymamy liczbę wszystkich inwersji w permutacji.
Złożoność tej metody to również O(n log n)

5. Zadanie LITERY z XIX OI

6.Zadanie Tetris Attack z XIV OI

II. Spójny podciąg o największej sumie

1. Tworzymy (dynamicznie) tablicę sum prefiksowych O(n)
2. Dla każdej pozycji znajdujemy najmniejszy jej poprzednik O(n)
3. Szukamy, kiedy różnica sumy prefiksowej pomiędzy daną pozycją a najmniejszą sumą wcześniejszą jest maksymalna O(n)
4. Udało się.

Inny sposób (również w czasie linowym)

1. Przechodzimy jeden raz po tablicy 1..n, dla każdego elementu licząc wartość największego spójnego podciągu kończącego się w tym elemencie. Robimy to w czasie stałym:
2. Niech "p" będzie największą wartością spójnego podciągu kończącego się w elemencie "i". Wtedy najw. wartość spójnego podc. kończącego się w el. "i+1" obliczamy: p = p + i (jeśli p>0) lub p = i (w przeciwnym wypadku).
3. Największą wartość "p" pamiętamy w zmiennej "wynik" i ją wypisujemy na koniec ;)
4. Jeśli się nie udało, to tu jest kod (cały program to zaledwie 24 linijki!)

Zadanie Domowe: Stefan