10348. Taksówka na Manhattanie 4 [TAXIMAN4]

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

Skrócony opis problemu:

Dla danych $n$ ($n \le 10^5$) punktów z przestrzeni $d$-wymiarowej (mających $d < 17$ współrzędnych) wypisać odległość w metryce Manhattan między dwoma najdalszymi punktami.

Rozwiązanie naiwne:

Dla każdej pary punktów obliczyć odległość między nimi i wybrać największą z nich.

Złożoność: $O(n^2 \cdot d)$, jako że par punktów jest $\frac{n(n-1)}{2}$, a odległość między każdą parą obliczamy w czasie $\Theta(d)$ (przechodząc wszystkie $d$ współrzędnych).

Rozwiązanie sprytniejsze:

Najpierw opiszę rozwiązanie dla $d=2$ a potem je uogólnię.

Chcemy znaleźć najdalszą parę punktów w 2D. Określmy odległość każdego punktu od $(0;0)$. Jest to $|y_i|+|x_i|$. Mając 2 punkty możemy obliczyć odległość między nimi za pomocą ich odległości od $(0;0)$. Np. dla $(1;2)$ i $(6;7)$ wartości to odpowiednio 3 i 13. Odległość między nimi to zatem $|3-13|=10$. ALE dla punktów $(1;7)$, $(6;-1)$ to nie działa. Dlaczego? Bo dla pierwszej pary odcinek wygląda jak / a dla drugiej jak \ . W pierwszym przypadku jest dobrze, bo odległość między pierwszym punktem i $(0;0)$ ma wspólny początek z odległością między drugim punktem i $(0;0)$, a w drugim przypadku niekoniecznie. Jak możemy to naprawić? Obracając układ współrzędnych albo, konkretniej, oś OX, zamieniając znaki wszystkim x. Dla punktów $(1;7)$, $(6;-1)$ obliczamy zatem dwie wartości: $y_i+x_i$ (8 dla pierwszego punktu i 5 dla drugiego) oraz $y_i-x_i$ (6 dla pierwszego punktu i -7 dla drugiego). Z ich pomocą możemy obliczyć ich odległość - jest to większa z $|8-5|=3$ i $|6+7|=13$, a więc 13. Możemy więc znaleźć $min$ i $max$ dla $y_i+x_i$ oraz $min2$ i $max2$ dla $y_i-x_i$ w czasie liniowym. Co z tym robimy? Porównujemy $|max-min|$ oraz $|max2-min2|$ i wybieramy większe z nich. Jest to nasz wynik (największa odległość między dwoma punktami w 2D).

Możemy to teraz uogólnić dla $d > 2$. Na początku, nie znajdujemy jedynie $y_i+x_i$ i $y_i-x_i$, ale wszystkie kombinacje znaków (znaku + i znaku -). Na przykład dla: 1 2 3 4 musimy sprawdzić sumy: $1+2+3+4$, $1+2+3-4$, $1+2-3+4$, $1+2-3-4$, $1-2+3+4$, $1-2+3-4$, $1-2-3+4$ i $1-2-3-4$. Dlaczego nie $-1+2+3+4$? Bo jest to ciąg $1-2-3-4$ z przeciwnym znakiem (a interesuje nas wartość bezwzględna odległości). Tak więc trzymamy maxy i miny dla każdej takiej kombinacji znaków. Będzie $2^{d-1}$ maxów i $2^{d-1}$ minów. Po wczytaniu wszystkich punktów po prostu znajdujemy maksymalną wartość $|max_i-min_i|$ dla $i \in \left<0;2^{d-1}\right>$ (indeksując od 0).

Warto tutaj zaznaczyć, że sprawdzamy wszystkie kombinacje znaków +, - poruszając się w systemie binarnym. Tak więc np. dla $d=4$ zaczynamy od 0000, 0001, 0010, itd. 0 na danej pozycji oznacza znak +, a 1 znak - (albo odwrotnie - jest to obojętne, bo i tak bierzemy moduł, czyli wartość bezwzględną, wyniku).

Złożoność: $O(n \cdot d \cdot 2^d)$, bo dla każdego z $n$ punktów obliczamy każdą z $2^{d-1}$ kombinacji znaków w czasie stałym (możemy zamienić 0000 na 0001 dodając do inta 1) i obliczamy jej sumę (dodając do wyniku przy 0 i odejmując przy 1, a na końcu biorąc moduł) w czasie $\Theta(d)$.

Algorytm:

int main()
{
    int n, d, i, j, k, m, coord[d];
    long long x, min[m], max[m];
    
    get(d, n);
    m = 1<<(d-1); // kombinacji będzie 2^(d-1)
    for(i = 0; i < m; ++i) // inicjalizacja minów i maxów
        min[i] = 1e15,
        max[i] = -1e15;
    while(n--) // dla każdego punktu
    {
        for(j = 0; j < d; ++j) // pobierz jego współrzędne
            get(coord[j]);
        for(j = 0; j < m; ++j) // dla każdej kombinacji
        {
            x = 0;
            for(k = 0; k < d; ++k) // oblicz sumę opierając się na reprezentacji binarnej kolejnych intów i dodając jeśli na jakiejś pozycji jest 1 i odejmując dla 0 (albo odwrotnie)
                x += coord[k] * (j&(1<<k) ? 1 : -1);
            if(x < min[j]) // aktualizuj min dla danej kombinacji
                min[j] = x;
            if(x > max[j]) // aktualizuj max dla danej kombinacji
                max[j] = x;
        }
    }
    x = -1;
    for(i = 0; i < m; ++i) // weź maxa z modułów max-min
        if(llabs(max[i]-min[i]) > x)
            x = llabs(max[i]-min[i]);
    print(x);
}

Rozwiązanie jeszcze sprytniejsze:
Możemy zmodyfikować powyższy algorytm obliczając sumy kolejnych permutacji w czasie stałym.
Możemy zauważyć, że możemy obliczyć początkową sumę w czasie $\Theta(d)$, a kolejne moglibyśmy obliczać w czasie stałym, gdyby... zmieniała się tylko jedna pozycja. Możemy to zagwarantować korzystając z kodu Graya zamiast kodu binarnego. Kod Graya ma bowiem to do siebie, że kolejny wyraz różni się od poprzedniego dokładnie jednym bitem. Ale jak przejść z jednej "liczby Graya" na następną? Ano za pomocą tego wzoru:
$$\text{Gray}(x) = x \oplus \left\lfloor\frac{x}{2}\right\rfloor$$
...który oblicza $x$-tą liczbę Graya ($\oplus$ oznacza operację XOR). Ale jak dostać pozycję, która uległa zmianie? Ano możemy obliczyć $\text{Gray}(x) \oplus \text{Gray}(x+1)$ (która zwróci nam potęgę 2, a więc w reprezentacji binarnej będziemy mieli ...000001000...) i w czasie $O(d)$ znaleźć pozycję tej jedynej jedynki. Ale będziemy mieli taką samą złożoność, jak ostatnio! Tak, dla każdej z $n$ liczb mamy nadal $2^{d-1}$ kombinacji znaków + i - i dla każdej obliczamy sumę w czasie stałym, ale przechodzimy teraz z jednej na drugą w czasie $O(d)$. Możemy jednak to zauważyć, że te wszystkie pozycje muszą być obliczone tylko raz. Ergo, możemy obliczyć dla każdej liczby z przedziału $\left<1;2^{d-1}\right)$ (kombinacji znaków) w czasie $O(d)$, a później sprawdzić ją w czasie stałym (dla 0 nie obliczamy, bo nie ma od niej wcześniejszej liczby Graya, z której pozycja by się zmieniła). Musimy też pamiętać czy na danej pozycji 0 zmieniło się w 1 czy na odwrót. Dla zamiany 1 na 0 ja będę po prostu dawał znak '-' przed liczbą.

Złożoność: $O(d \cdot 2^d + n \cdot (d + 2^d) + 2^d) \approx O(n \cdot 2^d)$. Maksymalne $d$ jest tak małe, że jeśli nie było w wykładniku, to uznałem je za stałą.

Algorytm:

int main()
{
    int n, d, i, j, k, m, a, b, coord[d], pos[m];
    long long x, min[m], max[m];
    
    get(d, n);
    m = 1<<(d-1); // 2^(d-1)
    for(i = 0; i < m; ++i) // preprocessing; obliczanie wszystkich pozycji, na których zmieniają się bity liczby Graya
    {
        min[i] = 1e15;
        max[i] = -1e15;
        if(i)
        {
            pos[i] = 1; a = i^(i>>1); b = (i-1)^((i-1)>>1); k = a^b; // wzory na n-tą i (n-1)-tą liczbę Graya, a następnie ich XOR
            while(k%2 == 0) // dla potęgi 2 oblicza jej wykładnik w pesymistycznym czasie O(d)
                ++pos[i],
                k >>= 1;
            if(b < a) // zrób liczbę ujemną jeśli bit 1 zmienił się w 0
                pos[i] = -pos[i];
        }
    }
    while(n--)
    {
        for(j = 0; j < d; ++j)
            get(coord[j]);
        for(x = k = 0; k < d; ++k) // oblicz pierwszą sumę
            x += coord[k];
        if(x < min[0])
            min[0] = x;
        if(x > max[0])
            max[0] = x;
        for(j = 1; j < m; ++j) // sprawdź wszystkie kombinacje znaków
        {
            x += 2L*coord[llabs(pos[j])-1]*(pos[j] > 0 ? 1L : -1L); // dodaj lub odejmij jeden element (2 razy, bo jeśli wcześniej był na + to żeby był na minusie to musimy go odjąć 2 razy)
            if(x < min[j])
                min[j] = x;
            if(x > max[j])
                max[j] = x;
        }
    }
    for(x = -1, i = 0; i < m; ++i)
        if(llabs(max[i]-min[i]) > x)
            x = llabs(max[i]-min[i]);
    print(x);
}

Optymalizacja: Można również stablicować wszystkie potęgi 2. Dzięki temu będziemy otrzymywać wykładni w czasie stałym, zamiast w $O(d)$. Złożoność asymptotyczna będzie jednak taka sama.

Rozwiązanie najsprytniejsze:
Rozwiązanie to to nic innego jak połączenie pierwszego i trzeciego algorytmu w zależności od wartości $n$ i $d$.
Jeśli $n^2 \cdot d < n \cdot 2^d$ to korzystamy z pierwszego algorytmu, w przeciwnym razie z trzeciego.

Uwaga: Aby zaliczyć to zadanie warto zamienić funkcję llabs na własną funkcję obliczającą moduł liczby.