Omówienie zadania Sprawiedliwy podział (I etap XXXII OI)

W zadaniu rozwiązywać będziemy przypadki szczególne problemu sprawiedliwego podziału (ang. fair division).

Wstępna obserwacja

Zazdrość Bitka wobec Bajtyny występuje, gdy spełniony jest następujący warunek:

Suma wartości wszystkich przedmiotów posiadanych przez Bitka jest ściśle mniejsza (jego zdaniem!) niż suma wartości przedmiotów posiadanych przez Bajtynę po wyłączeniu z tej sumy jednego dowolnego przedmiotu.

Innymi słowy, niezależnie jaki przedmiot zostanie wyłączony, aby Bitek nie zazdrościł Bajtynie, Bitek musi uważać, że suma wartości jego przedmiotów jest nie mniejsza od sumy wartości pozostałych przedmiotów Bajtyny.

Łatwo zauważyć, że można nie sprawdzać tego warunku poprzez wyłączanie wszystkich przedmiotów po kolei, a wystarczy sprawdzić po usunięciu przedmiotu Bajtyny o najmniejszej wartości zdaniem Bitka. To też sugerowała treść zadania.

Analogicznie jest w przypadku zazdrości Bajtyny.

Pierwsze dwa podzadania (\(n \leq 10\); \(n \leq 20\))

Sprawdzenie sprawiedliwości konkretnego podziału można wykonać w czasie \(O(n)\). Zazdrość Bitka i Bajtyny można sprawdzić osobno (w identyczny sposób). Aby sprawdzić, czy Bitek zazdrości, należy patrzeć tylko na wartości, które on przypisuje przedmiotom i zsumować osobno wartości jego przedmiotów i przedmiotów Bajtyny, zapamiętując najmniejszą wartość przedmiotu Bajtyny, aby potem sprawdzić warunek braku zazdrości.

Jeśli \( A, B \) to rozbicie zbioru wszystkich przedmiotów na przedmioty, odpowiednio, Bajtyny i Bitka (reprezentowane przez ich indeksy), to warunek braku zazdrości Bitka jest następujący:

\[\sum_{i \in B} b_i \ge \sum_{i \in A} b_i - \min_{i \in A} b_i\]

Podział nazwiemy sprawiedliwym, jeśli nikt nie zazdrości nikomu. W języku Python funkcja sprawdzająca sprawiedliwość podziału może wyglądać następująco:


def is_fair_split(A, B, a, b):
    # Evaluate from first person's perspective
    sum_a_A = sum(a[i] for i in A)
    sum_a_B = sum(a[i] for i in B)
    min_a_in_B = min((a[i] for i in B), default=float('inf'))

    # Evaluate from second person's perspective
    sum_b_A = sum(b[i] for i in A)
    sum_b_B = sum(b[i] for i in B)
    min_b_in_A = min((b[i] for i in A), default=float('inf'))

    # Check if both consider the split fair
    return sum_a_A >= sum_a_B - min_a_in_B and sum_b_B >= sum_b_A - min_b_in_A

Po zaimplementowaniu funkcji sprawdzającej zazdrość dla danego podziału można łatwo rozwiązać obydwa podzadania, sprawdzając wszystkie możliwe podziały w czasie wykładniczym. Podziałów jest \( 2^n \), każdy potrafimy sprawdzić w czasie liniowym, zatem rozwiązanie ma złożoność \( O(n \cdot 2^n) \). W języku Python można użyć funkcji combinations do generowania kolejnych możliwych rozbić w następujący sposób:


def solve_all_splits(n, a, b):
    # Generate all possible splits
    for split_size in range(n + 1):
        for subset in combinations(range(n), split_size):
            set1 = set(subset)
            set2 = set(range(n)) - set1

            # Check if this split is fair for both players
            if is_fair_split(set1, set2, a, b):
                # Create result array
                result = [0] * n
                for i in set2:
                    result[i] = 1
                print(' '.join(map(str, result)))
                return

Powyższe rozwiązanie bazuje na fakcie, że rozwiązanie istnieje, co wynika bezpośrednio z treści zadania.

Obydwa podzadania miały to samo rozwiązanie, ale pierwsze podzadanie dopuszczało istotnie większą stałą lub np. rozważanie wszystkich permutacji przedmiotów. Jednym z rozwiązań przechodzących obydwa podzadania było rozwiązanie randomizowane, które zamiast sprawdzać wszystkie podziały w określonej kolejności, losowało je z powtórzeniami.

Trzecie podzadanie, przypadek szczególny (\(a_i = b_i\))

W tym podzadaniu przedmioty mają tę samą wartość dla Bitka i Bajtyny, co pozwala na rozwiązanie go prostym algorytmem zachłannym. Należy posortować wszystkie przedmioty od najbardziej wartościowego do najmniej wartościowego, a następnie przypisywać przedmioty po kolei do osoby, której przedmioty mają w danym momencie sumarycznie mniejszą wartość (rozstrzygając remisy w dowolny sposób).

Poprawność tego algorytmu udowodnimy indukcyjnie. Wykażemy mianowicie, że po dodaniu każdego przedmiotu warunek braku zazdrości jest zawsze spełniony. Kluczową obserwacją jest, że ze względu na kolejność, w jakiej dodajemy przedmioty, dodawany przedmiot jest zawsze najmniej warty (być może na równi z innym), dlatego to jego będziemy wykluczać przy sprawdzaniu warunku braku zazdrości.

W zerowym kroku wartość przedmiotów otrzymanych przez Bitka i Bajtynę jest równa zero, ponieważ nie przydzieliliśmy jeszcze żadnego przedmiotu. Zatem zazdrość nie występuje.

Na początku każdego kroku, zanim przydzielimy przedmiot, nikt nie zazdrości nikomu. Po przydzieleniu nowego przedmiotu osobie o mniejszej sumie, dalej nikt nie ma powodów do zazdrości, ponieważ:

Osoba, która otrzymała przedmiot, ma bardziej wartościowy zbiór przedmiotów niż przed przydzieleniem, więc nie zaczyna zazdrościć.
Osoba, która nie otrzymała przedmiotu (miała większą wartość przedmiotów przed jego dodaniem), również nie zaczyna zazdrościć, ponieważ przedmiot przypisaliśmy osobie o mniejszej sumie wartości przedmiotów, a wiemy, że nowy przedmiot ma najmniejszą wartość spośród przypisanych. Zbiór przedmiotów osoby z nowym przedmiotem po odjęciu tego o najmniejszej wartości jest zbiorem sprzed przypisania, co oznacza, że jego suma wartości jest mniejsza (nie większa), bo właśnie osobie z takim zbiorem dodawaliśmy przedmiot.

Po posortowaniu przedmiotów, ten algorytm jest algorytmem liniowym. Dlatego rozwiązanie tego podzadania ma taką złożoność jak sortowanie \( O(n\log n) \).

Czwarte i piąte podzadanie, rozwiązanie ogólne (\(n \leq 1000\); \(n \leq 500\,000\))

Zauważmy że w szczególnym przypadku z trzeciego podzadania, Bitek i Bajtyna mogą zamienić się otrzymanymi zbiorami przedmiotów i nie będą sobie zazdrościć. Jest to kluczowa obserwacja aby zrozumieć rozwiązanie ogólne – Bitek nie będzie zazdrościł niezależnie od tego, który z powstałych zbiorów otrzyma.

Algorytm wzorcowy zaczyna od rozdzielenia przedmiotów na dwie grupy tak jakby Bajtyna przypisywała przedmiotom takie same wartości jak Bitek (przypadek z podzadania trzeciego). Przy tak powstałych dwóch zbiorach przedmiotów, Bitek nie będzie zazdrościł Bajtynie niezależnie od tego, który z nich otrzyma. Dlatego Bajtyna może wybrać ten zbiór, który jej zdaniem ma większą wartość. I właśnie to robi rozwiązanie wzorcowe – daje Bajtynie bardziej wartościowy zbiór (zdaniem Bajtyny) z tych dwóch, a Bitek jest zadowolony z pozostałego.

To rozwiązanie również ma złożoność \(O(n \log n)\).

Dwa ostatnie podzadzania mają ponownie to samo rozwiązanie, ale podzadanie czwarte dopuszczało znacznie większą stałą lub rozwiązania o złożoności kwadratowej, np. z powodu jakiegoś błędu implementacyjnego.