15281. Odległość [AL_08_05]

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

Skrócony opis problemu:

Dla dwóch permutacji $a$ i $b$ ciągu o długości $n$ oblicz odległość między nimi. Odległością nazywamy ilość przekształceń z jednej permutacji w drugą.

Np. odległością między permutacjami 1987 i 7891 (dla ciągu ${1, 7, 8, 9}$ o długości $n=4$) jest 4, gdyż kolejne przekształcenia to:

0 1987

1 7189

2 7198

3 7819

4 7891

Pierwsza permutacja ma numer 0, gdyż nie musieliśmy wykonywać żadnego przekształcenia. Przekształcenie to zatem zamiana jednej permutacji w następną leksykograficznie.

Cyfry w ciągu nie powtarzają się.

Rozwiązanie naiwne:

Możemy obliczać następne permutacje aż do uzyskania permutacji $b$.

Złożoność: $O(n \cdot n!)$, gdyż $a$ może być pierwszą możliwą permutacją a $b$ ostatnią. Ilość permutacji o długości $n$ to $n!$. Następną permutację można natomiast obliczyć w czasie liniowym, a następnie również w czasie $O(n)$ można sprawdzić czy owa permutacja równa jest $b$.

Rozwiązanie sprytne:
Wypiszmy dla powyższego przykładu wszystkie permutacje:

1789          7189          8179          9178

1798          7198          8197          9187

1879          7819          8719          9718

1897          7891          8791          9781

1978          7918          8917          9817

1987          7981          8971          9871

Widzimy coś? Otóż przejście z wiersza jednej kolumny, do tego samego wiersza sąsiedniej kolumny to zamiana miejscami pierwszych elementów tych kolumn. Czyli jeśli chcemy np. przejść z kolumny nr 3 do kolumny nr 4 dla ciągu 8791 to zamieniamy miejscami 8 i 9: 9781. Przejście takie możemy wykonać w czasie stałym - jednak z sąsiedniej kolumny do sąsiedniej. Jeśli zatem chcemy przejść z 1-szej kolumny do 3-ciej, to wykonujemy 2 operacje takich zamian. Przy każdej zamianie dodajemy do sumarycznej odległości silnię z $n-1-i$, gdzie $i$ to pozycja, którą rozpatrujemy (indeksując od 0). Możemy zatem, wykonując maksymalnie $n-1$ operacji, przejść z jednej permutacji w drugą, tak, żeby zgadzały się pierwsze cyfry.

Np. mamy sobie permutacje 1897 i 9718. Zamieniamy 1 i 7 miejscami i dodajemy do wyniku 6 (czyli silnia z 3, które jest ilością cyfr po pozycji, którą rozpatrujemy). Mamy 7891. Następnie zamieniamy 7 i 8 miejscami i znów dodajemy 6. 8791. Zamieniamy w końcu miejscami 8 i 9 i po raz ostatni dodajemy 6. Mamy 9781. Pozycja pierwsza (o indeksie 0) z głowy, przy wyniku 18. Okazuje się, że druga pozycja również się zgadza. Cóż, możemy sobie zatem ją odpuścić. Bierzemy się za 3-cią. Tutaj widzimy, że chcemy zamienić 8 na 1. Czyli większą cyfrę na mniejszą. Poprzednio szliśmy w przód - teraz zaszliśmy za daleko. Problem? Nie. Teraz zamiast dodawać będziemy po prostu odejmować od wyniku. Zamieniamy zatem 8 na 7... Ale chwila! Przecież 7 już zostało zużyte. Musimy więc pamiętać, które liczby zostały zużyte i brać mniejszą, ale w zaktualizowanej kolejności. Tak więc nie zamieniamy 8 na 7, tylko na 1 (po sprawdzeniu, że nie zostało zużyte). Otrzymujemy zatem 9718, a od wyniku odejmujemy $1!=1$. Zwróćmy uwagę, że po dopasowaniu przedostatniej cyfry mamy już odpowiednią permutację. Ostatnia cyfra musi być przecież na właściwym miejscu, bo zostało już tylko jedno. Tak więc tu kończymy pracę z wynikiem $18-1=17$. Gdybyśmy nie pominęli drugiej cyfry, to na tamtym etapie dodawalibyśmy lub odejmowalibyśmy $2!=2$.

Należy tutaj zauważyć, że jeśli $a>b$ to wyjdzie nam ujemny wynik, gdyż będziemy najpierw odejmować większe silnie, a potem dodawać mniejsze. Na szczęście wystarczy tylko wziąć z wyniku wartość bezwzględną i wszyscy będą żyli długo i szczęśliwie.

Wiemy już co nasz program ma robić. Pomyślmy więc teraz jak ma to robić, żeby było szybko. Czego potrzebujemy? Dla każdej cyfry użytej w ciągu musimy znaleźć jej następnika (czyli minimalną cyfrę większą od rozpatrywanej przez nas), który nie został już zużyty. Musimy znać również pozycję tego następnika, żeby móc w czasie stałym zamienić te cyfry miejscami. Skoro cyfry nie mogą się powtarzać, to możemy po prostu przejść $a$ i dla każdego znaku zaktualizować tablicę $index[a_i]$, w której będziemy dla każdej cyfry trzymać jej pozycję. Aby znaleźć następnika danej cyfry możemy dla każdej z nich trzymać jej numer porządkowy (czyli dla $a=1879$ dla 7 będziemy trzymać 2, gdyż jest to 2-ga najmniejsza liczba). Tak więc przechodzimy tablicę $index$ od 0 do 9 i jeśli jakaś komórka nie jest równa -1 (na początku wszystkie są równe -1), to dodajemy tę cyfrę do tablicy $order$ w ten sposób, że $order[2]=7$ (dla wspomnianego przykładu) oraz do tablicy $position$ w ten sposób, że $position[7]=2$. Po co nam to? Powiedzmy, że chcemy następnika 7-mki. No więc najpierw sprawdzamy, która jest 7-mka: $position[7]$, a następnie szukamy liczby, która jest następna. Czyli: $order[position[7]+1]$. Mamy następnika 7-mki i musimy już tylko zamienić je miejscami w tablicy $index$. Jak sprawdzić czy na pewno następnik nie jest usunięty? Wystarczy sprawdzić jego pozycję. Jeśli będzie ona mniejsza oprócz indeksu, w którym jesteśmy, to znaczy, że już ją wykorzystaliśmy. Czyli np. mamy sobie 7189 i jesteśmy przy 1-nce. Następnikiem 1-nki jest 7, ale sprawdzamy jej pozycję i jest przed 1-nką, więc szukamy następnika 7-mki.

Złożoność: $O(n^3)$, bo dla każdej z $n-1$ pozycji przechodzimy maksymalnie $n-1$ cyfr (czyli np. z 1 na 7, z 7 na 8 i z 8 na 9) i dla każdego przejścia szukamy następnika w czasie liniowym.

Algorytm:

int main()
{
    int dl, i, j, k, x, index[19], position[19], order[19], fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}, q, p;
    char a[19], b[19];

    get(a, b);
    dl = strlen(a);
    for(i = 0; i < 10; ++i)
        position[i] = 0;
    for(i = 0; i < dl; ++i)
        position[a[i]-'0'] = 1,
        index[a[i]-'0'] = i;
    for(x = i = 0; i < 10; ++i)
        if(y[i])
            position[i] = ++x,
            order[x] = i;
    for(x = i = 0; i < dl-1; ++i)
        while(a[i] != b[i])
            if(a[i] < b[i])
            {
                x += fact[dl-1-i], // zwiększ odległość
                q = a[i]-'0'; // zamiana znaku na liczbę (cyfrę)
                j = position[q]+1; //
                while(index[order[j]] < i) // szukamy nieusuniętego następnika
                    ++j;
                // wymiana znaków w tablicy a
                p = order[j];
                a[i] = p+'0';
                a[index[p]] = q+'0';
                // wymiana pozycji znaków w tablicy index
                j = index[p];
                index[p] = index[q];
                index[q] = j;
            }
            else
            {
                x -= fact[dl-1-i], // zmniejsz odległość
                q = a[i]-'0';
                j = position[q]-1;
                while(index[order[j]] < i) // szukamy nieusuniętego poprzednika
                    --j;
                p = order[j];
                a[i] = p+'0',
                a[index[p]] = q+'0';
                j = index[p];
                index[p] = index[q];
                index[q] = j;
            }
    print(abs(x)); // wypisujemy wartość bezwzględną wyniku
}

Rozwiązanie sprytniejsze:

Możemy przyspieszyć powyższy algorytm lepiej pamiętając następników każdej z cyfr. Możemy np. posortować w osobnej tablicy $temp$ cyfry, a następnie dla każdej z nich (oprócz ostatniej, która nie ma następnika) zapisać $next[temp[i]] = temp[i+1]$ oraz w analogiczny sposób stworzyć tablicę $prev$ poprzedników. Gdy będziemy chcieli usunąć jakąś liczbę $r$ z tablic $next$ i $prev$ to przypiszemy poprzednikowi $r$ jego następnika oraz następnikowi $r$ jego poprzednika. Czyli dokładnie to samo jakbyśmy usuwali z listy, ale na indeksach, a nie wskaźnikach.

Złożoność: $O(n^2)$, gdyż znajdujemy następnika w czasie stałym.

Rozwiązanie sprytniejsze nr 2:

Autorem tego rozwiązania jest Adam Bąk.

Możemy podejść do problemu od innej strony. Mianowicie, możemy obliczyć dla obu wyrazów, którą są permutacją w porządku leksykograficznym, a następnie wziąć wartość bezwzględną różnicy tych wartości.

Np. 1798 jest 2. permutacją, a 8179 jest 13. permutacją. Odległość między nimi to zatem 11.

Jak obliczyć numer porządkowy permutacji? Przypomnę permutacje ciągu 1789, aby było łatwiej to zauważyć.

1789          7189          8179          9178

1798          7198          8197          9187

1879          7819          8719          9718

1897          7891          8791          9781

1978          7918          8917          9817

1987          7981          8971          9871

A zatem jeśli widzimy, że nasza permutacja zaczyna się od 7 (czyli drugiej najmniejszej liczby), to wiemy, że będzie z przedziału $\left<7;12\right>$. Sprawdzamy więc, którą z kolei liczbą jest cyfra na pozycji przez nas rozpatrywanej i dodajemy do wyniku (który jest początkowo równy 1, jako że numerujemy od 1) $(n-1-i)! \cdot (l-1)$, gdzie $i$ to pozycja przez nas rozpatrywana (początkowo 0), a $l$ wskazuje, którą liczbą od początku jest ta na pozycji $i$. $i-1$, bo dla 1-nki nie chcemy nic dodawać, gdyż jest to początek.

Np. mamy sobie 8917. Widzimy, że 8-mka jest 3. najmniejszą liczbą więc wynik to $1+(4-1-0)! \cdot (3-1) = 13$. Przechodzimy dalej. 9 jest 3. najmniejszą liczbą, więc... Zaraz, zaraz! Przecież to 8 jest 3. najmniejszą liczbą, 9 jest 4. Nie, 8 już przerobiliśmy i usuwamy ją z naszego ciągu. To tak jakbyśmy rozważali po prostu ciąg 179 zamiast 1789. Jesteśmy w 3ciej kolumnie, gdzie nie potrzebujemy 8-mki, gdyż jest już na właściwym miejscu. Tak więc dla 9-tki dodajemy do wyniku $(4-1-1)! \cdot (3-1) = 4$, a wynik to $13+4=17$. Dalej, 1 jest ewidentnie najmniejszą liczbą. Wynik to zatem $17+(4-1-2)! \cdot (1-1) = 17$. Nic się nie zmieniło. Dlaczego? Bo skoro 1-nka jest pierwsza to mając już ustawione 8 i 9 pozostały nam tylko 2 możliwe ciągi: 17 oraz 71, a dla 1-nki już jesteśmy we właściwym z nich. Ostatniej cyfry nie musimy sprawdzać, gdyż jeśli $n-1$ cyfr jest na właściwym miejscu, to i ostatnia musi być. Tak więc wychodzi nam, że permutacja 8917 jest 17-stą permutacją, co można sprawdzić powyżej.

Zaletą tego algorytmu jest jego prostota (w porównaniu do mojego) oraz przenośność. Mamy sobie funkcję, która może nam się przydać w różnych algorytmach i możemy ją po prostu wklejać, nie martwiąc się, że pisząc ją od nowa popełnimy błąd.

Wadą wszystkich algorytmów w tym artykule jest obliczanie silni. Dla większych długości rzędu jedynie kilkudziesięciu cyfr będziemy już mieli problemy z obliczeniem tak dużych silni i trzeba by zaimplementować arytmetykę dużych liczb.

Złożoność: $O(n^2)$, gdyż przechodzimy $n-1$ pierwszych cyfr i dla każdej liniowo ($O(n)$) sprawdzamy, którą liczbą od początku jest (czyli zliczamy liniowo ilość nieusuniętych liczb przed daną liczbą).

Algorytm:

int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

int ord(char *num)
{
    int l, z, n = 0, i, acc = 1, digits[10];

    for(i = 0; i < 10; ++i) // wyczyść tablicę wystąpień
        digits[i] = 0;
    for(i = 0; num[i]; ++i) // zapisz, które cyfry są w ciągu
        digits[num[i]-'0'] = 1,
        ++n; // w n po zakończeniu pętli będzie długość ciągu
    for(i = 0; i < n-1; ++i)
    {
        for(z = l = 0; z < num[i]-'0'; ++z) // zliczamy ilość cyfr mniejszych od rozpatrywanej przez nas
            l += digits[z]; // jeśli jakiejś cyfry nie ma to dodajemy 0, więc nic się nie psuje
        acc += fact[n-i-1]*l;
        digits[num[i]-'0'] = 0; // usuwamy rozpatrywaną cyfrę, gdyż już ją przetworzyliśmy
    }
    return acc;
}

int main()
{
    char num1[15], num2[15];

    scanf("%s %s", num1, num2);
    printf("%d\n", abs(ord(num2)-ord(num1)));
}

Rozwiązanie najsprytniejsze:

Autorem tego rozwiązania jest Jakub Podeszwik.

Możemy przyspieszyć powyższy algorytm znajdując ilość mniejszych cyfr od danej w czasie logarytmicznym.

Skorzystamy z drzewa Fenwicka, którego bardzo dobry opis znajduje się tu. Można to również zrobić na zwykłym drzewie przedziałowym. Niestety nie można skorzystać z STLa, gdyż set nie pozwala pobrać odległości iteratora (który zwraca funkcja lower_bound) od początku seta. Można oczywiście napisać swoje własne drzewo zrównoważone, ale jako że drzewo przedziałowe jest łatwiejsze (w tym drzewo Fenwicka), to skupimy się na nim.

A zatem, na początku tworzymy sobie puste drzewo. Następnie każdą cyfrę z naszego ciągu, powiększoną o 1, dodajemy do drzewa. Powiększamy ją o 1, gdyż w drzewie Fenwicka wartości zaczynają się od 1. Gdy chcemy zliczyć ilość cyfr mniejszych od danej cyfry $x$, to po prostu zliczamy sumę wyrazów od 1 do $x-1$, jako że chcemy wszystkie cyfry mniejsze od $x$ ($x$ również powiększamy o 1, więc wyjdzie od 1 do $x$). Na koniec usuwamy $x$ z drzewa.

Złożoność: $O(n \log n)$, jako że dodajemy do drzewa $n$ cyfr w czasie logarytmicznym ($O(\log n)$), zliczamy $n-1$ sum w czasie logarytmicznym, oraz usuwamy $n-1$ cyfr w czasie logarytmicznym.

Ostateczny algorytm:

int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}, tree[19];

void update(int x, int v) // v = 1 dla dodania, v = -1 dla usunięcia; aktualizuje drzewo
{
    for(; x < 11; x += x&-x)
        tree[x] += v;
}

int sum(int x) // zlicza ilość cyfr w przedziale 1..x
{
    int y = 0;
    do y += tree[x];
    while(x -= x&-x);
    return y;
}

int ord(char *num)
{
    int n = 0, acc = 0, i;

    for(i = 0; i < 11; ++i) // zerujemy drzewo Fenwicka
        tree[i] = 0;
    for(i = 0; num[i]; ++i)
    {
        num[i] -= '0'-1; // zmieniamy chara na inta i przedział 0..9 na 1..10 (bo drzewo Fenwicka ma wartości od 1)
        update(num[i], 1); // dodajemy cyfrę
        ++n; // w n będzie długość ciągu
    }
    for(i = 0; i < n-1; ++i)
    {
        acc += fact[n-i-1]*sum(num[i]-1); // mnożymy silnię przez ilość mniejszych cyfr od num[i]
        update(num[i], -1); // usuwamy cyfrę
    }
    return acc;
}

int main()
{
    int r;
    char num1[15], num2[15];

    scanf("%s %s", num1, num2);
    r = ord(num2)-ord(num1);
    print(abs(r));
}