2217. Statystyka pozycyjna [KC022]

Zadanie:
https://pl.spoj.com/problems/KC022

Skrócony opis problemu:

Dla danej liczby $k$ należy wypisać $k$-tą statystykę pozycyjną. Innymi słowy należy wypisać $k$-tą największą liczbę z podanego zbioru (nie multizbioru - usuwamy duplikaty), a jeśli nie istnieje, to wypisać znak '-'.

Podejście naiwne:

Możemy przejść tablicę $k-1$ razy i za każdym skreślać (przypisywać jej np. wartość -1) największą liczbę ze zbioru, a na końcu przejść tablicę jeszcze raz i tym razem wypisać największą liczbę.

Złożoność: $O(k \cdot n)$, gdzie $n$ to ilość liczb z wejścia.

Podejście sprytniejsze:

Możemy posortować malejąco liczby z wejścia, a następnie w czasie stałym wypisać $k-1$-tą liczbę z posortowanej tablicy ($k-1$ jeśli indeksujemy od 0).

Złożoność: $O(n \log n)$, ze względu na sortowanie. Jak widzimy, to rozwiązanie jest niezależne od $k$, co jest jego zaletą. W poprzednim algorytmie w pesymistycznym przypadku mieliśmy $O(n^2)$, dla $k=n$.

Podejście sprytniejsze nr 2:

Możemy skorzystać z drzewa statystyk pozycyjnych (DSP). Jest to drzewo zrównoważone, do którego można dodawać elementy i je usuwać w czasie logarytmicznym ($O(\log n)$). Jeśli bowiem dodamy do zwykłego drzewa binarnego po kolei: 2, 3, 4, 5, ... to będziemy przechodzili wszystkie poprzednie elementy przy dodawaniu nowych. Pesymistyczna złożoność dodawania i usuwania z drzewa niezrównoważonego jest zatem liniowa ($O(n)$). Przykładowe drzewa zrównoważone to drzewa AVL lub częściej używane drzewa czerwono-czarne.

Dodajemy więc kolejne liczby do DSP, a na końcu szukamy $k$-tego największego elementu, dzięki informacji o wielkości poddrzew. Innymi słowy, dla każdego wierzchołka trzymamy informację, jak duże jest jego lewe i prawe poddrzewo. Powiedzmy, że chcemy znaleźć 7-dmy najmniejszy element, lewe poddrzewo ma rozmiar 3, a prawe 10. Skoro chcemy lewe poddrzewo ma rozmiar 3, to znaczy, że 3 najmniejsze elementy są w lewym poddrzewie. Interesuje nas zatem prawe poddrzewo. Schodzimy więc poziom niżej i patrzymy na lewego i prawego potomka prawego poddrzewa. Itd. aż dojdziemy do jednego elementu. Wykonamy logarytmiczną ilość operacji, gdyż przejdziemy drzewo od góry do dołu, a więc całą jego wysokość, której rozmiar wynosi właśnie $\log n$.

Zaletą DSP jest również to, że możemy modyfikować naszą tablicę w czasie logarytmicznym. Np. możemy chcieć usunąć 5-ty pod względem wielkości element, a następnie znaleźć 7-dmy element. W przypadku poprzedniego rozwiązania musielibyśmy od nowa sortować tablicę. Oczywiście przy tylko jednej zmianie moglibyśmy pamiętać o ignorowaniu 5-tego elementu, ale przy większej ilości usunięć już nie.

Wadą DSP jest... konieczność zakodzenia DSP. ;-) Poniższy algorytm ma wszystkie zalety DSP i łatwo się go implementuje.

Złożoność: $O(n \log n)$, bo mamy $n$ elementów, które dodajemy do drzewa w pesymistycznym czasie $O(\log n)$. Jest to jednak szybsze rozwiązanie od poprzedniego, gdyż nie na początku dodajemy elementy do drzewa w czasie logarytmicznym, ale od mniejszego rozmiaru drzewa.

Podejście sprytniejsze nr 3:

Autorem tego rozwiązania jest Filip Czaplicki.

Rozwiązanie to podobne jest do poprzedniego. Różni się tylko rodzajem użytego drzewa. Tym razem użyjemy drzewa przedziałowego.

Prosiłbym o zapoznanie się z tym opisem drzew przedziałowych, gdyż będę na nim bazował. Jest to jednak naprawdę bardzo dobry tutorial i żeby wytłumaczyć tutaj dogłębnie drzewa przedziałowe musiałbym praktycznie go przepisać.

Tak więc dodajemy do drzewa przedziałowego po kolei liczby w czasie logarytmicznym w taki sposób, że po wczytaniu każdej liczby $x$ sprawdzamy czy już ją może dodaliśmy. Jeśli $tree[x+n] > 0$ to znaczy, że już ją dodaliśmy, więc nic nie robimy. W przeciwnym wypadku, wywołujemy $insert(x, 1)$ z tutoriala. Czyli zapisujemy, że mamy jedną liczbę $x$. Drzewo przedziałowe nie będzie zatem zawierało samych liczb, ale ilość ich wystąpień. Po wczytaniu liczb będziemy mieli praktycznie gotowe drzewo i na koniec, analogicznie do poprzedniego algorytmu sprawdzamy rozmiar lewego i prawego poddrzewa i idziemy w jedno z nich aż nie przekroczymy liczby $x+M$, co będzie oznaczać, że doszliśmy do liści (czyli końcowych wierzchołków).

Złożoność: $O(n \log y)$, gdzie $y$ to długość przedziału liczb, na którym będziemy operować. Np. dla przedziału $\left<100; 600\right>$ $y=500$. W zadaniu $y=100$, więc w tym przypadku ten algorytm jest jak znalazł. Jeśli jednak $y$ by było większe i nie trzeba by modyfikować tablicy między zapytaniami, to lepiej użyć sortowania.

Uwaga: Algorytm nie działa dla liczb ujemnych. Jeśli zatem mamy przedział $\left<-100;100\right>$ to przekształcamy go w $\left<0;200\right>$, a następnie od wyniku odejmujemy 100. W tym zadaniu taka modyfikacja nie jest jednak potrzebna.

Ostateczny algorytm:

int tree[300];

int read_data(int n)
{
        int x, y = 0;
        char z;

        while(scanf("%d%c", &x, &z) > 0)
        {
                x += n+1;
                if(!tree[x]) // ignorujemy powtórki
                {
                        ++y; // zliczamy ile jest liczb na wejściu
                        ++tree[x];
                        while(x > 1)
                                x >>= 1,
                                tree[x] = tree[x<<1]+tree[(x<<1)+1];
                }
                if(z == 10)
                        break;
        }
        return y;
}

int order_statistic(int k, int n) // n jest liczbą 2^coś-1 i jest maksymalną liczbą z tych, które będziemy przeszukiwać w poszukiwaniu k-tej statystyki pozycyjnej
{
        int x = 1, i;
        for(i = 1; i < 2*n+2; ++i)
                tree[i] = 0;
        if(k < 1) // jeśli k < 1 to wypisujemy -1, ale musimy jeszcze wczytać liczby poniżej
                x = 0;
        k = read_data(n)+1-k; // mamy wypisać k-tą liczbę, ale od końca
        if(k < 1 || !x)
                return -1;
        while(x <= n) // dopóki nie osiągniemy liścia
                if(k > tree[x<<1])
                        k -= tree[x<<1],
                        x = (x<<1)+1;
                else
                        x <<= 1;
        return x-n-1;
}

int main()
{
        char z;
        int k;

        while(scanf("%d%c", &k, &z) > 0)
        {
                if(z != ' ')
                {
                        puts("-");
                        continue;
                }
                k = order_statistic(k, 127); // maksymalne x to 100, więc zaokrąglamy to do najmniejszej potęgi 2 większej od x pomniejszonej o 1
                if(k < 0)
                        puts("-");
                else
                        printf("%d\n", k);
        }
}

Podejście sprytniejsze nr 4:

Rozwiązanie to podpowiedział mi Damian Straszak.

Można to rozwiązać stosując po prostu algorytm magicznych piątek, który znajduje $k$-tą statystykę pozycyjną w czasie liniowym.

Musimy jednak uważać na duplikaty. Jak sobie z tym poradzić? Ano możemy zastosować tablicę haszującą, która haszuje nam elementy w czasie stałym ($O(1)$). Haszowanie jest jednak randomizowane. Znaczy to, że nie mamy pewności, że otrzymamy w każdym przypadku dobry wynik. Prawdopodobieństwo porażki jest jednak dla dobrych funkcji haszujących bliskie zeru.

Dla liczb całkowitych z przedziału o rozmiarze do około $10^7$ możemy użyć, zamiast haszowania, tablicowania. Wtedy jeśli $hash[x] > 0$ to $x$ już było i je ignorujemy.

Złożoność: $O(n)$, jako że jest to czas algorytmu magicznych piątek + haszowanie każdej z $n$ liczb w czasie stałym.

Uwaga: Liniowy algorytm, ale niedeterministyczny.

Ostateczny algorytm:

TODO