Omówienie zadania Porządki (II etap XXXII OI)

Zadanie jest zadaniem interaktywnym, w którym celem uczestnika jest posortowanie rosnąco permutacji \( n \) różnych liczb \( (1, 2,\dots, n) \) przy pomocy możliwie małej liczby zamian. Jedyną operacją, jaką może wykonać zawodnik, jest zamienienie dwóch elementów permutacji na pozycjach \(a\) i \(b\) podanych przez niego. Zasadniczą trudnością zadania jest to, że zawodnik nie ma dostępu do permutacji. Zna jej rozmiar (czyli liczbę \( n \)) oraz po każdej zamianie poznaje liczbę inwersji w permutacji.

W zadaniu uczestnicy mieli wybór między komunikacją z programem sprawdzającym poprzez biblioteczkę lub poprzez standardowe wejście i wyjście. Było to pierwsze w historii Olimpiady zadanie z interaktywną komunikacją przez wejście/wyjście.

Czym jest liczba inwersji?

Liczba inwersji to liczba takich par elementów, że element większy znajduje się przed elementem mniejszym. Na przykład w permutacji \( (3, 1, 2) \) są dwie inwersje, obydwie stworzone przez pierwszy element \( (3 > 1 \wedge 3 > 2) \), a w ciągu rosnącym nie ma żadnej inwersji.

Wstępne obserwacje

Warunek końca: zgodnie z podpowiedzią w treści, permutacja jest posortowana, gdy liczba inwersji wynosi zero. Zgadza się to z obserwacją z poprzedniego punktu, że w ciągu rosnącym nie ma inwersji.
Początkowa liczba inwersji: ponieważ zadanie dopuszcza \( a = b \), aby sprawdzić początkową liczbę inwersji w ciągu, wystarczy na przykład zamienić pierwszy element z samym sobą. Nie zmienia to permutacji, zwraca jedynie liczbę inwersji, a pierwszy element zawsze istnieje.

Rozwiązanie brutalne (5 punktów)

Najbardziej naiwne rozwiązanie wykładnicze to zamienianie losowych elementów ze sobą, aż uzyskamy ciąg rosnący.

n = DajN()

while True:
    # Pick two random indices (1-based)
    i, j = random.sample(range(1, n + 1), 2)

    swap_two_elements(i, j)

W powyższym rozwiązaniu została użyta pomocnicza funkcja swap_two_elements zamieniająca dwa elementy na wskazanych pozycjach i zwracająca liczbę inwersji po tej zamianie lub kończąca działanie programu jeśli ciąg został posortowany. W tym wypadku zwracana wartość nie jest używana, ale będziemy korzystali z tej funkcji w kolejnych rozwiązaniach.

def swap_two_elements(i, j):
    """Perform a swap and return the number of inversions."""
    inversions = Zamien(i, j)
    if inversions == 0:
        sys.exit(0)
    return inversions

Niestety przy tym rozwiązaniu możemy się spodziewać, że potrzebne będzie \( n! \) operacji, a \(n! = 6! = 720 > 200 = m\). Punkty za to podzadanie mogło natomiast uzyskać rozwiązanie randomizowane, które zamienia ze sobą losowe elementy, ale cofa tę zamianę jeśli wzrosła liczba inwersji.

n = DajN()
current_inversions = swap_two_elements(1, 1)

while True:
    # Pick two random indices (1-based)
    i, j = random.sample(range(1, n + 1), 2)

    new_inversions = swap_two_elements(i, j)

    if new_inversions > current_inversions:
        swap_two_elements(i, j)
    else:
        current_inversions = new_inversions

Rozwiązanie sortowaniem bąbelkowym \( O(n^2) \) (14 punktów)

Obserwacja: jeśli ciąg nie jest posortowany, to istnieją dwa sąsiadujące elementy takie, że większy znajduje się przed mniejszym.
Obserwacja 2: jeśli zamienimy dwa sąsiadujące elementy, to liczba inwersji wzrośnie albo zmaleje o dokładnie jeden. Wynika to z tego, że względna pozycja elementów (wcześniej/dalej) zmieniła się tylko dla tych dwóch elementów.
Obserwacja 3: dokonując zamiany sąsiednich elementów, liczba inwersji wzrasta o 1 wtedy i tylko wtedy, gdy przed zamianą element mniejszy występował przed elementem większym. W przeciwnym przypadku wartość ta maleje o 1.

Z powyższych obserwacji wynika, że do posortowania permutacji można użyć sortowania bąbelkowego. W sortowaniu bąbelkowym porównywane są sąsiadujące elementy i zamieniane jeśli większy znajduje się przed mniejszym. Nie jesteśmy w stanie po prostu porównać dwóch elementów, ale jesteśmy w stanie zamienić dwa sąsiadujące elementy i dowiedzieć się który był mniejszy. Należy zatem zamieniać sąsiadujące elementy, a następnie cofać zamianę jeśli nie zmniejszyła ona liczby inwersji w permutacji.

W tym rozwiązaniu trzeba cały czas pamiętać liczbę inwersji, aby móc sprawdzić czy wartość wzrosła czy zmalała.

current_inversions = swap_two_elements(1, 1)

while True:
    # Iterate over adjacent pairs (1-based indices)
    for i in range(1, n):
        new_inversions = swap_two_elements(i, i + 1)

        if new_inversions >= current_inversions:
            # Cancel the swap if it didn't reduce inversions
            swap_two_elements(i, i + 1) # Ignore the inversion count since it's back to the same
        else:
            # Update the current inversion count
            current_inversions = new_inversions

Rozwiązanie dziel i zwyciężaj (quick-sort) \( O(n \log n) \) (37 punktów)

Obserwacja: jesteśmy w stanie porównać nie tylko sąsiadujące, ale dowolne dwa elementy zamieniając je. Jeśli mniejszy z tych dwóch elementów występował wcześniej przed zamianą, to liczba inwersji wzrosła. W przeciwnym wypadku zmalała.

Zaimplementować możemy zatem algorytm quick-sort, który bazuje na idei dziel i zwyciężaj.
- Z ciągu wybierany jest losowy element (zwany pivotem).
- Ustawiany jest on na poprawnej pozycji w ten sposób, że wszystkie elementy mniejsze znajdują przed nim, a wszystkie większe po nim.
- Ten sam algorytm jest wykonywany rekurencyjnie na spójnym podciągu przed pivotem oraz tym po nim.

def q_sort(p, q):
    if p >= q:
        return

    # Choose a random pivot and swap it with the first element in the interval
    pivot_position = random.randint(p + 1, q)
    current_inversions = swap_two_elements(p, pivot_position)

    # Partition: Move smaller elements to the left, larger to the right
    pivot_position = p
    for i in range(p + 1, q + 1):
        inversions = swap_two_elements(pivot_position, i)

        if inversions > current_inversions:  # Element is larger, keep it in place
            swap_two_elements(pivot_position, i)
            continue
        else:
            pivot_position += 1
            if pivot_position < i:
                current_inversions = swap_two_elements(i, pivot_position)
            else:
                current_inversions = inversions

    # Recursively sort left and right partitions
    q_sort(p, pivot_position - 1)
    q_sort(pivot_position + 1, q)


def main():
    # Read the size of the permutation
    n = DajN()

    # Sort the entire array
    q_sort(1, n)

Oczekiwana złożoność takiego sortowania jest liniowo logarytmiczna.

W powyższym algorytmie można jeszcze poprawić stałą, rezygnując z trzymania elementu pivot cały czas możliwie wcześnie w ciągu i ustawiając go na docelowej pozycji dopiero po przeanalizowaniu całego ciągu. Taka optymalizacja nie była jednak wymagana do otrzymania pełnej liczby punktów za to podzadanie.

Analogicznie można zaimplementować inne algorytmy sortujące w miejscu.

Pierwsze rozwiązanie liniowe (58 punktów)

Wcześniejsze podzadania opierały się na algorytmach sortowania przez porównanie, a porównanie dwóch elementów wymaga użycia jednej operacji. Znany jest fakt, że takie algorytmy mają złożoność przynajmniej \( \Omega(n \log n) \), zatem, aby uzyskać maksymalną liczbę punktów, należało użyć dodatkowych informacji, jakie daje nam znajomość liczby inwersji, i nie bazować na standardowych algorytmach sortowania.
Istnieje rozwiązanie modelowe przechodzące czwarte podzadanie wykonujące \( 3n - 2 \) operacji, ale limit został ustawiony na \( 3n + 10 \) aby dopuścić nadmiarowe zamiany, które upraszczają implementację.

Obserwacja: jeśli znamy permutację, to jesteśmy w stanie posortować ciąg przy pomocy maksymalnie \( n - 1 \) operacji, ustawiając kolejne elementy na ich docelowe pozycje (po ustawieniu \( n - 1 \) elementów, wiemy że ostatni znajduje się na właściwym miejscu).

for i in range(1, n + 1):
    while permutation[i] != i:  # While the current position is incorrect
        a, b = i, permutation[i]
        swap_two_elements(a, b)
        permutation[a], permutation[b] = permutation[b], permutation[a]

Powyższy kod bazuje na założeniu, że lista permutation zawiera poprawną permutację od początku. Podczas sortowania utrzymujemy niezmiennik, iż permutacja w programie sprawdzającym oraz w naszej liście są identyczne.
W dalszej części tego opisu przyjmujemy, że \( (a_i) \) to początkowa permutacja.

Ponieważ jesteśmy w stanie posortować ciąg wykorzystując \( n - 1 \) operacji, to musimy być w stanie odgadnąć permutację w maksymalnie \( 2n + 11 \) operacji. Aby to zrobić, zdefiniujemy ciąg \( (x_i) \) tak, że \( x_1 \) to liczba inwersji w początkowej permutacji, a \( x_i \) to liczba inwersji w permutacji, w której zamieniliśmy pierwszy element z \(i\)-tym elementem. Sprawdzenie wartości \( x_1 \) to jedna operacja, a wyliczenie każdej następnej wartości \( x_i \) wymaga dwóch operacji (trzeba zamienić pierwszy oraz \(i\)-ty element, a następnie cofnąć tę zamianę).

Po uzyskaniu ciągu \( (x_i) \) jesteśmy w stanie obliczyć różnicę między pierwszym elementem permutacji a ostatnim. Różnica \( x_n - x_1 \) informuje nas o tym, ile inwersji tworzy się/znika w permutacji, jeśli zamieniamy pierwszy element z ostatnim.

\[ a_n - a_1 = \frac{x_n - x_1 + (1 ~~ \texttt{if} ~~ x_n > x_1 ~~ \texttt{else} ~~ -1))}{2} \]

Wynika to z tego, że po zamianie pierwszego i ostatniego elementu pierwszy element stworzy inwersję ze wszystkimi, z którymi nie tworzył wcześniej (większymi od niego) i przestanie tworzyć z tymi, z którymi wcześniej tworzył (mniejszymi od niego). Analogiczna zmiana jest prawdziwa dla ostatniego elementu.
Względna pozycja (wcześniej/później) wszystkich innych elementów jest niezmienna, dlatego \( x_n - x_1 \) zeruje inwersje pomiędzy wszystkimi parami nie zawierającymi \(x_1\) lub \(x_n\).
\( \pm 1 \) wynika z tego, że nie możemy liczyć dwa razy zamiany pierwszego i ostatniego elementu.

Nie znamy wartości ani \( a_1 \) ani \( a_n \) ale znamy różnicę ich wartości, a zatem jesteśmy w stanie ustalić ich względną pozycję w ciągu posortowanym. Dla tych dwóch elementów ich odległość w ciągu posortowanym oraz różnica wartości jest tym samym, ale myślenie tylko o ich odległości pomoże w zrozumieniu dalszej części rozwiązania.

Analogiczna zasada działa dla każdego prefiksu \( (a_1, a_2, \dots, a_k) \) permutacji \((a_i)\). Jesteśmy w stanie obliczyć, ile elementów przed/za elementem \(a_1\) występuje element \( a_k \) w prefiksie danej permutacji po jego posortowaniu.
Uwaga: prefiks \( (a_1, a_2, \dots, a_k) \) nie musi być permutacją liczb \((1,2,\dots,k)\).

# Step 1: Calculate the initial number of inversions
    initial_inversions = swap_two_elements(1, 1)  # 1 swap

    # Step 2: Calculate relative position of a_k
    c, x = [0] * (n + 1), [0] * (n + 1)

    x[1] = initial_inversions
    for i in range(2, n + 1):
        inversions_after_swap = what_would_be(1, i)  # 2 swaps
        x[i] = inversions_after_swap
        c[i] = (x[i] - x[1] + (1 if x[i] > x[1] else -1)) // 2  # relative position to put at

    # Step 3: reconstruct permutation locally (does not swap)
    permutation = reconstruct(c)

    # Step 4: sort permutation optimally (n - 1 swaps)
    solve(permutation)

W powyższym kodzie użyta została funkcja what_would_be, która zwraca liczbę inwersji po zamianie pierwszego oraz \(i\)-tego elementu, ale nie zmienia permutacji (używa dwóch zamian).

Wyznaczywszy relatywne pozycje względem \( a_1 \), możemy odtworzyć permutację. Najprostszym sposobem jest po prostu wstawienie pierwszego elementu do tablicy (oznaczmy go \( 1 \)), pamiętanie gdzie się znajduje (w zmiennej \( p \)) i wstawianie kolejnych elementów względem niego. Wartość \( c_i = -1 \) znaczy tuż przed nim, \( c_i = 1 \) tuż po nim, \( c_i = 2 \) dwa elementy po nim itd.

def reconstruct(c):
    positions = [0, 1]  # 0 is dummy
    p = 1  # position of the first element (a_1)

    for i in range(2, len(c)):
        put_at = p + c[i] + (0 if c[i] > 0 else 1)  # c[i] may be negative
        positions.insert(put_at, i)
        if c[i] < 0:
            p += 1  # a_1 moved to the right

    # Get permutation from positions
    permutation = [0] * len(c)
    for i in range(len(positions)):
        permutation[positions[i]] = i

    return permutation

Łatwo policzyć, że to rozwiązanie wymaga maksymalnie \( 3n - 2 \) zamian, ale jego złożoność czasowa jest kwadratowa (wstawianie elementu do listy jest liniowe, a wstawiamy ich \(n\)). Ponieważ jednak nie było to zasadniczą trudnością zadania i nie było wymagane w tym podzadaniu, nie będziemy skupiali się tutaj na implementacji optymalnego rozwiązania tego problemu. Istnieje wiele możliwości zaimplementowania listy z wstawianiem na k-tej pozycji w czasie logarytmicznym. W rozwiązaniu wzorcowym złożoność czasowa to \( O(n \log n) \) dzięki użyciu drzew przedziałowych.

Rozwiązanie wzorcowe \( 2n - 1 \) operacji (100 punktów)

Aby zmniejszyć liczbę operacji do \( 2n - 1 \), musimy być w stanie odgadnąć początkową permutację, używając maksymalnie \( n \) operacji. Aby to zrobić, nie możemy cofać naszych zamian. Zdefiniujmy więc \( x_1 \) jak wcześniej, a \( x_i \) jako liczbę inwersji gdyby element \(i\) był na pierwszej pozycji, czyli permutacji \(a_i, a_1, ..., a_{i-1}, a_{i+1}, ..., a_n\). Aby obliczyć \(x_i\) wystarczy zamienić pierwszy oraz \(i\)-ty element, taka operacja wstawi \(i\)-ty element na początek a \(i-1\)-wszy element zajmie jego miejsce.

for i in range(1, n + 1):
    x[i] = swap_two_elements(1, i)  # 1 swap

Tak zdefiniowany ciąg \( x_i \) wyliczany jest przy użyciu dokładnie \( n \) operacji. Przyjrzyjmy się teraz inwersjom w \(x_1\) oraz \(x_i\). Możemy zauważyć, że różnią się tylko liczbą inwersji, które tworzy \(i\)-ty element, w dodatku tylko z elementami od 1 do \(i-1\). Odejmując je od siebie, poznamy różnicę liczby elementów większych i mniejszych od \(a_i\), które są przed nim. Znając tę różnicę i liczbę elementów, która jest sumą większych i mniejszych, możemy łatwo określić, ile jest elementów mniejszych od \(a_i\), które występują przed tym elementem.

for i in range(1, n + 1):
    smaller_before[i] = ((i - 1) - (x[1] - x[i])) // 2

Znając dla każdego elementu, ile jest elementów mniejszych od niego przed nim, możemy określić wartości tych elementów, idąc od końca. Dla ostatniego elementu będzie to smaller_before[n] + 1, a dla \(i\)-tego elementu będzie to element na pozycji smaller_before[i] + 1 pośród elementów, których jeszcze nie użyliśmy (posortowanych w kolejności rosnącej). Dośc prosto jest to obliczyć w czasie kwadratowym, jednak da się także w \( O(n \log n) \), dzięki użyciu drzew przedziałowych.

def compute_original_permutation():
    seg_tree = SegmentTree(n)
    permutation = [0] * (n + 1)  # 1-based indexing
    for i in range(n, 0, -1):
        permutation[i] = seg_tree.query(smaller_before[i] + 1)
        seg_tree.update(permutation[i])  # Add 1
    return permutation

Należy jeszcze tylko zwrócić uwagę, że uzyskaliśmy początkową permutację \((a_i)\), a w tej chwili permutacja jest już inna, bo jest to \((a_n, a_1, a_2, \dots, a_{n-1})\). Aby uzyskać aktualną permutację wystarczy przestawić ostatni element oryginalnej permutacji na początek. A następnie posortować jak wcześniej.

Tak zaimplementowane rozwiązanie jest rozwiązaniem wzorcowym, działa w pamięci liniowej, czasie logarytmicznie-liniowym oraz wykonuje co najwyżej \( 2n - 1 \) zapytań. Otrzymuje więc maksymalną liczbę punktów.