13696. Drzwi Adriana [DALGO]

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

Skrócony opis problemu:

Jest $n$ testów. Każdy z nich składa się z $3$ liczb: $p$, $q$ i $m$. Mając liczby $p$ i $q$ należy znaleźć takie liczby $x$ i $y$, że $x \cdot p + y \cdot q=NWD(p,q)$, ale tak, aby $x \ge 0$ oraz by $x$ było minimalne.

Następnie należy nadpełnić przedział $\left<\min(x,y);\max(x,y)\right>$ liczbą $m$ (czyli do każdego elementu z przedziału dodać liczbę $m$). Po wykonaniu wszystkich testów należy wypisać cały przedział.

Podejście naiwne:

W równaniu $x \cdot p + y \cdot q=NWD(p,q)$ mamy dwie niewiadome. Możemy zatem zacząć poszukiwanie $x$ od $0$ i mając już tylko jedną niewiadomą sprawdzać czy istnieje takie całkowite $y$, że $y = \frac{NWD(p,q) - x \cdot p}{q}$. Złożoność tej części to $O(n \cdot x)$ (bo jest n testów), a jako że $x \approx n$, to możemy przyjąć $O(n^2)$.

Następnie dla każdego testu wypełniamy liniowo przedział, a na samym końcu wypisujemy wszystkie elementy przedziału. Złożoność tej części to: $O\left(n \cdot \left(\left|x\right|+\left|y\right|\right) + n\right)$. Jako że zarówno $x$ jak i $y$ są rzędu $n$, to otrzymujemy $O\left(n^2\right)$.

Widzimy, że złożoności obu części są takie same, więc ostateczna złożoność to również $O\left(n^2\right)$.

Podejście sprytne:

Zamiast obliczać $x$ i $y$ liniowo możemy skorzystać z rozszerzonego algorytmu Euklidesa.

Dostaniemy parę liczb $\left(X;Y\right)$ spełniającą powyższe równanie. Może się jednak zdarzyć, że $X<0$, jednak możemy to naprawić w czasie stałym. Dlaczego? Ustawmy sobie rozwiązania (pary liczb) w kolejności rosnącej względem składowej $x$. Na pewno otrzymamy parę, która byłaby sąsiadem pary $(0;0)$, gdyby taka istniała (czyli nie istnieje para o $x$ bliższym od $0$ niż nasze $X$ lub $y$ bliższym od $0$ niż nasze $Y$). Musimy więc tylko zamienić naszą parę na następną (czyli szukamy pary $(X2;Y2)$ takiej, że $X2>X$ oraz $X2$ jest minimalne). Mamy zatem takie równanie: $X \cdot p + Y \cdot q=NWD(p,q)$ i chcemy z jego pomocą rozwiązać takie: $(X+s) \cdot p + (Y-t) \cdot q=NWD(p,q)$, gdzie $s$ i $t$ to różnice między $X2$ a $X$ oraz $Y$ a $Y2$. $$X \cdot p + Y \cdot q=(X+s) \cdot p + (Y-t) \cdot q \\ X \cdot p + Y \cdot q=X \cdot p + s \cdot p + Y \cdot q - t \cdot q \\ s \cdot p = t \cdot q$$

Skoro chcemy znaleźć najmniejsze $s$, to musimy znaleźć najmniejsze dodatnie $t$, które po przemnożeniu przez $q$ dzieli się bez reszty przez $p$ (wynika to z: $s=\frac{t \cdot q}{p}$). Możemy przyjąć, że $t=p$, wtedy otrzymamy $s=q$. Czy $s$ jest jednak w tym przypadku najmniejsze możliwe? Nie. Weźmy np. $q=4$ i $p=2$. Wyszłoby nam, że $s=4$ a $t=2$. Najmniejsze $s$ to jednak $2$ przy $t=1$. W $q$ są bowiem czynniki pierwsze, które są również w $p$, i które się skrócą. Wzory na $s$ i $t$ to zatem:

$$s=\frac{q}{NWD(p,q)} \\ t=\frac{p}{NWD(p,q)}$$

Dlaczego napisałem, że możemy przeskoczyć z $X$ na $X2$ w czasie stałym, skoro obliczenie $NWD(p,q)$ wymaga logarytmicznego czasu? Dlatego, że $NWD(p,q)$ obliczyliśmy już dodatkowo w rozszerzonym algorytmie Euklidesa.

Złożoność tej części to $O\left(n \log{n}\right)$ (n testów - dla każdego rozszerzony algorytm Euklidesa).

Mamy już $x$ i $y$. Załóżmy, że już je uporządkowaliśmy i $x<y$. Jak szybciej niż ostatnio dodać $m$ do każdej komórki przedziału $\left<x;y\right>$? Otóż możemy skorzystać z drzewa przedziałowego. Uzupełniamy w czasie logarytmicznym ów przedział $\left<min(x[]);y\right>$ (gdzie $x[]$ oznacza tablicę wszystkich $n$ początków przedziałów, które będziemy uzupełniać) o wartość $m$, a następnie również logarytmicznie uzupełniamy przedział $\left<\min(x[]);x-1\right)$ o $-m$. Pierwsze uzupełnienie dopisze nam do wszystkich komórek od początku do $y$ liczbę $m$, a drugie usunie ją z przedziału od początku do $x-1$, jako że nie chcieliśmy modyfikować tamtych komórek. Odczytujemy dla każdej komórki analogicznie, w takim samym czasie asymptotycznym. Komórek takich może być maksymalnie $2n$.

Złożoność tej części to również $O\left(n \log{n}\right)$, jako że mamy $2n$ insertów oraz $2n$ query działających w czasie logarytmicznym.

Sumaryczna złożoność to zatem również $O\left(n \log{n}\right)$.

Podejście sprytniejsze:

W tym podejściu pierwszy etap się niczym nie różni od tego w poprzednim algorytmie. Skupimy się tylko na drugiej części.

Mamy już zatem $x$ i $y$ ($x<y$). Możemy zauważyć, że odczytujemy wszystkie komórki na raz. Gdybyśmy bowiem odczytywali tylko pojedyncze komórki to musielibyśmy robić to logarytmicznie, a tak możemy zrobić to w czasie stałym (więc łącznie liniowo). Do tablicy też dodajemy w czasie stałym. Robimy po prostu $tab[x] += m; tab[y+1] -=m;$ Wygląda to podobnie do poprzedniego rozwiązania, gdyż tam też dodawaliśmy gdzieś $m$, a gdzieś je odejmowaliśmy. Co nam da uzupełnienie tych dwóch komórek? Otóż przy wypisywaniu skorzystamy z sum prefiksowych. Zaczynamy od komórki $\min(x[])$, która ma jakąś wartość. Następnie idziemy do następnej i dodajemy do niej poprzednią wartość, a następnie ją wypisujemy. To $-m$ niweluje zatem poprzednie $m$, które dodaliśmy. Złożoność tej części to $O(n)$, jako że komórek może być do $2n$.

Asymptotyczna złożoność jest taka sama jak poprzednio, czyli $O\left(n \log{n}\right)$, jednak program działa trochę szybciej, a gdyby $x$ i $y$ były podane od razu, to złożoność by była liniowa.

Ostateczny algorytm:

int n; // n bez wartości oznacza wczytane n
while(n--)
{
    int p, q, m;
    int a = 1, d = 1, b = 0, c = 0, p2 = p, q2 = q, quot, r, new_d, new_c;
    while(q) // rozszerzony algorytm Euklidesa
        r = p%q,
        quot = p/q,
        p = q,
        q = r,
        new_c = a-quot*c,
        new_d = b-quot*d,
        a = c,
        b = d,
        c = new_c,
        d = new_d;
    if(a < 0) // jeśli a nie spełnia warunków
        a += q2/p,
        b -= p2/p;
    if(a < b) c = a, a = b, b = c; // zamiana a i b jeśli a>b
    if(a > max) max = a; // koniec ostatecznego przedziału
    if(b < min) min = b; // początek ostatecznego przedziału
    X[b+1000001] += m; // +1000001, aby na pewno indeks był nieujemny
    X[a+1000002] -= m; // +1000001+1
}
for(int i = min; i <= max; ++i)
    printf("%d ", X[i+1000001] += X[i+1000000]); // najpierw dodajemy a potem wypisujemy komórkę