15153. Do odpowiedzi! [AL_07_04]

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

Skrócony opis problemu:

Mając tablicę o rozmiarze $n$, przechodzimy ją zmieniając pozycję o kolejne liczby pierwsze i oznaczając komórki, na których stanęliśmy jako "zużyte". Komórki te pomijamy przy poruszaniu się. Gdy dojdziemy do końca to przeskakujemy na początek tablicy. Na koniec pozostaje tylko jedna niezużyta komórka i to jej numer mamy wypisać (zaczynając numerację od 1).

Np. dla $n=4$:

$$1234 \rightarrow 1X34 \rightarrow XX34 \rightarrow XXX4$$

W pierwszym kroku skreślamy drugą liczbę. W drugim zmieniamy pozycję o 3 - 3, 4, 1 i skreślamy to 1. W ostatnim zmieniamy pozycję o 5: 3, 4, 3, 4, 3 - skreślamy zatem 3. Wynik to 4.

Uwaga: założę w zadaniu, że mamy już daną tablicę liczb pierwszych, jako że łatwo ją uzyskać korzystając z sita Eratostenesa.

Rozwiązanie naiwne:

Możemy poruszać się tak jak powyżej. Czyli przechodzimy po kolei komórki tablicy i inkrementujemy licznik aż uzyskamy daną liczbę pierwszą i wtedy oznaczamy komórkę jako 0 i w następnych iteracjach nie bierzemy jej pod uwagę i nie inkrementujemy licznika jeśli staniemy na 0 w przyszłości.

Złożoność: duża. Dla pierwszych $n-1$ liczb pierwszych przesuwamy się o daną liczbę pierwszą i dodatkowo o wszystkie liczby, które po drodze usunęliśmy.

Rozwiązanie sprytniejsze:

Możemy zauważyć, że dla dużych liczb pierwszych przechodzimy całą tablicę wiele razy, szczególnie gdy usunęliśmy już z niej sporo elementów. Znając zatem ilość pozostałych w tablicy niezużytych komórek (równej z początku $n$, a potem dekrementowanej przy każdym zużyciu komórki) możemy pominąć przebiegi całej tablicy. Jeśli zatem mamy przejść 97 niezużytych komórek, a pozostało ich np. 15 to robimy 97 mod 15 i okazuje się, że wystarczy, że przejdziemy tylko 7 komórek.

Złożoność: $O(n^2)$. Dla każdej z $n-1$ liczb pierwszych przechodzimy maksymalnie raz całą tablicę (jako że wartość mod $n$ to maksymalnie $n-1$), więc otrzymujemy złożoność kwadratową.

Rozwiązanie jeszcze sprytniejsze:

Największą wadą naszego poprzedniego rozwiązania jest to, że musimy jednak przechodzić komórka po komórce. A robimy tak, gdyż musimy odróżnić komórkę zużytą od niezużytej. Inaczej moglibyśmy od razu skoczyć do następnej interesującej nas komórki. Czemu zatem nie usuwać tych zużytych komórek? Skorzystajmy zatem z vectora, który usuwa komórki w czasie $O(x)$, gdzie $x$ to ilość komórek po tej, którą chcemy usunąć (bo jak usunie komórkę to wszystkie za nią przesuwa o 1 miejsce). Tak więc znajdujemy interesującą nas komórkę, usuwamy ją, a następnie przeskakujemy w czasie stałym na następną.

Złożoność: $O(n^2)$. Pesymistycznie złożoność jest taka sama jak w poprzednim przypadku, jeśli będziemy usuwać ciągle z początku vectora, lecz tak naprawdę poruszamy się po całym vectorze, więc powinno być to rozłożone, dając lepszy czas i AC w powyższym zadaniu.

Algorytm:

int main()
{
    int n, primes[100000]; // dane
    int i, j, k;
    vector<int> v;

    if(n < 4)
    {
        puts("1");
        return 0;
    }
    for(i = 1; i <= n; ++i)
        v.push_back(i);
    for(i = j = 0; i < n-1; ++i)
    {
        k = primes[i]-1+j; k %= v.size();
        v.erase(v.begin()+k);
        j = k; j %= v.size();
    }
    printf("%d\n", v[0]);
}

Rozwiązanie jeszcze² sprytniejsze:

Autorem tego rozwiązania jest withelm.

Możemy do rozwiązania tego zadania użyć drzewa przedziałowego. Będziemy mieli zamiast vectora liczb, którego rozmiar nieustannie maleje - tablicę, w której tylko wartości komórek maleją, a jej długość jest stała. Komórki przechowują bowiem ilość liczb w danym przedziale. Jaki przedział dana komórka reprezentuje zależy od rodzaju drzewa przedziałowego. Ja skorzystam z drzewa Fenwicka (Fenwick tree, Binary Indexed Tree), jako że jest nieco szybsze (przy tej samej złożoności).

Tak więc w komórce o indeksie 7 będziemy przechowywać ilość liczb z przedziału $\left<5;6\right>$, a więc na początku 2 (bo mamy na początku 1 piątkę i 1 szóstkę).

Dla każdej liczby pierwszej sprawdzamy zatem w czasie logarytmicznym ile jest liczb pierwszych od miejsca, w którym jesteśmy (nazwijmy jest $A$) do końca tablicy (oznaczmy to jako $x$). Jeśli jest wystarczająco, żeby przejść bez przeskakiwania z końca tablicy na początek, to nic nie zmieniamy. W przeciwnym wypadku uznamy, że przeskoczyliśmy te $x$ komórek, więc od danej liczby pierwszej odejmujemy $x$ (oznaczmy to pozostałe przesunięcie jako $y$). Następnie ustawiamy $A$ na 0 (w drzewie Fenwicka komórka o indeksie 0 nie reprezentuje żadnego przedziału) i ponownie liczymy ilość pozostałych liczb do końca tablicy (tym razem w czasie stałym, gdyż chcemy sprawdzić ilość niezużytych liczb w całej tablicy, a jest ich $n-y$, gdzie $y$ to ilość liczb zużytych). Następnie robimy nasz trick z modulo z poprzedniego algorytmu, żeby pominąć cykle, w których przechodzilibyśmy całą tablicę.

Teraz możemy w końcu usunąć liczbę oddaloną o $y$ od $A$, a aby to zrobić musimy ją wcześniej znaleźć. Możemy to zrobić w czasie $O(\log^2 n)$. Skorzystamy z wyszukiwania binarnego. Tak więc najpierw przedział $\left<A;n\right>$ dzielimy na 2 części i sprawdzamy liczność ($z$) pierwszej z nich. Jeśli $z \ge y$ to znaczy, że szukana jest w pierwszej połowie. Zamieniamy zatem koniec przedziału na $\frac{A+n}{2}-1$. W przeciwnym wypadku zamieniamy początek przedziału na $\frac{A+n}{2}+1$. Jak widać, długość przedziału zmniejsza nam się 2 razy przy każdej iteracji, co daje nam ich logarytmiczną ilość. Złożoność to kwadrat logarytmu, gdyż w każdej iteracji musimy obliczać $z$ w czasie logarytmicznym.

Gdy już ją znajdziemy, to wystarczy w czasie logarytmicznym zaktualizować tablicę, dekrementując wybrane komórki o 1.

Na koniec zostanie nam 1 nieusunięta liczba, którą możemy znaleźć przeszukując tablicę od początku, jako że w tablicy podprzedziały mają mniejszy indeks niż przedziały je zawierające. Możemy też (jak jest pokazane w poniższym kodzie) usunąć ostatnią liczbę i wypisać po prostu jej indeks.

Złożoność: $O(n \log^2 n)$.

Algorytm:

int LSOne(int x) // zwraca największą potęgę 2, przez którą jest podzielne x
{
    return x&(-x);
}

void update(int x, int y) // nadpisuje wszystkie przedziały zawierające x o y
{
    while (x <= n)
        tree[x] += y,
        x += LSOne(x);
}

int query(int x) // zlicza sumę wartości w przedziale 1..x
{
    int res = 0;
    while(x > 0)
        res += tree[x],
        x -= LSOne(x);
    return res;
}

int query(int x, int y) // zlicza sumę wartości w przedziale x..y
{
    return query(y)-query(x-1);
}

int find(int begin, int x) // wyszukuje liczbę oddaloną od begin o x (nie mylić z begin+x)
{
    int p = n, l = begin, mid, tmp; // l to początek przedziału, p koniec, a mid środek
    while(l <= p) // dopóki przedział jest nieujemny
    {
        mid = (l + p) >> 1; // oblicz środek przedziału
        tmp = query(begin, mid); // zlicz ilość liczb z pierwszej połowy przedziału
        if(x == tmp && query(mid, mid) == 1) // jeśli ilość liczb jest równa przesunięciu ORAZ w komórce o indeksie min jest tylko jedna liczba to zwróć środek przedziału (bo mid może reprezentować przedział z więcej niż 1 liczbą, a my szukamy jednej)
            return mid;
        if(x > tmp) // jeśli w drugiej połowie
            l = mid + 1; // zamień początek przedziału na środek
        else // jeśli w pierwszej połowie
            p = mid - 1; // zamień koniec przedziału na środek
    }
    return -1;
}

int simulation(int x) // zwraca ostatnią usuniętą liczbę
{
    for(int i = 1; i <= x; ++i) // tworzenie tablicy do drzewa Fenwicka
        tree[i] = LSOne(i);
    int last = 1;
    for(int i = 0; i < x; ++i)
    {
        int shift = primes[i]; // przesunięcie to i-ta liczba pierwsza
        int tmp = query(last, x); // ilość liczb od indeksu, od którego liczymy do końca tablicy
        if(tmp < shift) // jeśli do końca tablicy nie ma odpowiedniej ilości liczb, to przejdź na początek tablicy i zmniejsz przesunięcie o ilość liczb do końca tablicy
            shift -= tmp,
            last = 0,
            tmp = x-i;
        shift %= tmp; // trick z modulo, żeby pominąć cykle przechodzące całą tablicę
        if(!shift) // jeśli nie ma przesunięcia w ogóle, to je ustaw na ilość liczb do końca tablicy
            shift = tmp;
        last = find(last, shift); // aktualizuj ostatnio odwiedzony indeks
        update(last, -1); // usuwamy 1 liczbę o indeksie last, więc zmniejszamy ilość we wszystkich przedziałach ją zawierających o 1
    }
    return last;
}

int main()
{
    int n, primes[n]; // dane
    int tree[n+1]; // tablica do drzewa Fenwicka
    printf("%d\n", simulation(n));
}

Rozwiązanie najsprytniejsze:

Autorem tego rozwiązania jest Filip Czaplicki.

Można przyspieszyć poprzedni algorytm korzystając ze zwykłego drzewa przedziałowego.

Polecam zaznajomić się z tym poradnikiem, jako że będę na nim bazował. Jest to jednak naprawdę dobry tutorial - nie dawałbym linka do byle czego. Naprawdę łopatologicznie jest to wytłumaczone.

Tak więc najpierw tworzymy sobie tablicę o rozmiarze $2n_2+1$, gdzie $n_2$ to najmniejsza potęga dwójki, większa od $n$, pomniejszona o 1. Następnie wypełniamy ją liczbami z przedziału $\left<1;n\right>$. Wypełnianie polega na wpisywaniu 1nek w odpowiednie komórki, które reprezentują przedziały.

Np. $n=5$, a my chcemy wpisać do drzewa 3. $n_2 = 7$. Wpisujemy 1nkę w komórkę 13 (5+8 - patrz tutorial), następnie w komórkę 6, następnie w komórkę 3, a na końcu w komórkę 1.

Jak już wypełnimy tablicę drzewa, to możemy się brać za prawdziwy algorytm. Jest on analogiczny do rozwiązania z vectorem. Jedyna różnica to to, że usuwamy $k$-ty element z drzewa, a nie vectora. Jak jednak znaleźć ten $k$-ty element? Ano tak, że dla danego węzła (zaczynając od korzenia) patrzymy na jego dwóch synów. W każdym z nich jest rozmiar jego poddrzewa. Tak więc powiedzmy, że $k=5$, w korzeniu mamy liczbę 10, w jego lewym synu 3, a w prawym 7. My chcemy znaleźć 5-ty element, a w przedziale odpowiadającym lewemu synowi są tylko 3 elementy. Widzimy zatem, że musimy rozpatrywać jedynie prawego syna. Musimy jednak zapamiętać, że ignorujemy 3 najmniejsze elementy. Szukamy zatem w prawym poddrzewie 5-3=2-giego elementu. Schodzimy tak od korzenia po liście, w których zostanie nam przedział o długości 1 - będzie to nasza $k$-ta liczba (nazwijmy ją $x$). Mamy ją usunąć, więc wykonujemy funkcję $insert(x, -1)$ z tutoriala.

Po usunięciu $n-1$ liczb szukamy jedynej 1nki w tablicy drzewa z komórek z przedziału $\left<n_2+1;2n_2+1\right>$ - czyli sprawdzamy wszystkie liście - i wypisujemy jej indeks pomniejszony o $n_2+1$.

Drzewo przedziałowe nadaje się tu idealnie, gdyż jest proste do zaimplementowania, a przy tym działa wydajnie dla dynamicznie modyfikowanej tablicy.

Złożoność: $O(n \log n)$, jako że dla każdej z $n$ liczb dodajemy ją do tablicy w czasie logarytmicznym, następnie wyszukujemy dla każdej z $n-1$ liczb pierwszych którąś z kolei liczbę (również w czasie logarytmicznym) i na końcu ją usuwamy (dla odmiany w czasie logarytmicznym). Ostatnie przejście tablicy drzewa działa w czasie liniowym.

Ostateczny algorytm:

void 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;
        while(x <= n) // dopóki nie dojdziemy do liści
                if(k > tree[x<<1]) // jeśli w lewym poddrzewie nie ma wystarczająco elementów
                        k -= tree[x<<1], // odejmij tyle elementów ile jest w lewym poddrzewie
                        x = (x<<1)+1; // i przejdź do prawego poddrzewa
                else // przejdź do lewego poddrzewa
                        x <<= 1;
        --tree[x]; // usuń k-ty element
        while(x > 1) // i zaktualizuj tablicę drzewa
            x >>= 1,
            tree[x] = tree[x<<1]+tree[(x<<1)+1];
}

int main()
{
    int n, primes[n]; // dane
    int tree[2*n2+2];
    int n2, i, j, k;

    if(n < 4)
    {
        puts("1");
        continue;
    }
    n2 = n+1;
    if(n2-1 & n2) // jeśli n nie jest potęgą 2
    {
        frexp(n2, &n2);
        n2 = 1 << n2; // to zrób z n potęgę 2
    }
    --n2; // i pomniejsz o 1
    for(j = 1; j < 2*n2+2; ++j) // wyzeruj tablicę drzewa
        tree[j] = 0;
    for(j = 1; j <= n; ++j) // wypełnij tablicę drzewa liczbami z przedziału 1..n
    {
        k = j+n+1;
        ++tree[k];
        while(k > 1)
            k >>= 1,
            tree[k] = tree[k<<1]+tree[(k<<1)+1];
    }
    for(j = 0, k = 1; j < n-1; ++j) // usuń n-1 liczb
    {
        i = primes[j]-1+k; i = (l-1)%(n-j)+1; // %rozmiar - wcześniej omówiony trick
        order_statistic(i, n); // znajdź i-tą liczbę i ją usuń
        k = i; k = (k-1)%(n-j-1)+1; // rozmiar się zmniejszył, bo usunęliśmy 1 liczbę
    }
    for(j = n+1; j < 2*n+2; ++j)
        if(tree[j]) // jeśli znalazłeś jakąś nie usuniętą liczbę to ją wypisz i zakończ szukanie
        {
            printf(j-n-1);
            break;
        }
}