Omówienie zadania Przelewy (II etap XXV OI)

W zadaniu tym Bajtazar i jego przyjaciele chcieliby dokonać rozliczenia wydatków za pomocą przelewów bankowych. W tym celu chcieliby skorzystać z dość specyficznej promocji. Promocja polega na tym, że każda z \(n\) osób może wykonać dowolnie wiele operacji przelania jednego bajtalara do wszystkich swoich znajomych w systemie banku. Przyjaciele zdefiniowali zatem sieć znajomości w systemie banku i zrobili to w taki sposób, że ustawili \(n - 1\) znajomości i każde dwie osoby bezpośrednio lub pośrednio są swoimi znajomymi. Nietrudno się domyślić, że taką sieć znajomości możemy traktować jako graf, a ponieważ jest on spójny i ma \(n - 1\) krawędzi, tak więc jest drzewem.

Jeśli więc przeformujemy warunki promocji na język teorii grafów, to dostaniemy, że z każdego wierzchołka możemy przelać jednego bajtalara do wszystkich sąsiadów tego wierzchołka w drzewie. Przyjaciele zastanawiają się, czy mogą rozliczyć się za pomocą jedynie takich operacji i każdy wie, ile ma na koncie bajtalarów i ile chciałby mieć po zakończeniu rozliczenia.

Na początek przeanalizujmy test przykładowy. Od razu możemy dokonać pewnego uproszczenia w tym zadaniu. Tak naprawdę z informacji o saldach interesuje nas tylko dla każdego z przyjaciół, o ile jego saldo ma się zmienić podczas rozliczenia. Wobec tego te dwie liczby saldo początkowe i końcowe możemy zastąpić jedną liczbą mówiącą, o ile saldo początkowe jest większe od końcowego (np. dla przyjaciela \(1\) to będzie \(0\), ponieważ salda są równe, a dla przyjaciela \(3\) to będzie \(-1\), ponieważ saldo początkowe jest o \(1\) mniejsze od salda końcowego). Innymi słowy możemy sobie wyobrażać, że saldo końcowe dla każdego z przyjaciół musi wynieść \(0\). Zauważmy, że takie równoważne spojrzenie na ten problem jest możliwe dzięki temu, że w banku dopuszczalne są ujemne salda.

Spróbujmy w tym przykładzie dokonać teraz rozliczenia za pomocą dostępnych operacji. Możemy zacząć od wierzchołka \(2\), w którym przelejemy do każdego z jego sąsiadów po jednym bajtalarze (wobec tego w wierzchołku \(1\) zwiększymy do \(1\) saldo, a w wierzchołku \(4\) do \(-1\), natomiast saldo w wierzchołku \(3\) zmniejszy się od \(2\) do \(1\)). Zauważmy, że nadal saldo w wierzchołku \(4\) jest ujemne. Jedynie z wierzchołka \(2\) możemy jakieś pieniądze tam przelać, więc jeszcze raz wykonajmy operację na wierzchołku \(2\), co spowoduje, że przelanie pieniędzy do wierzchołka \(1\) i do \(4\). Tym razem saldo w wierzchołku \(2\) wynosi \(-1\).

Dalej możemy przelewać pieniądze z wierzchołka \(1\), bo w nim mamy \(2\). W tym momencie przelejemy zarówno do wierzchołka \(3\), do wierzchołka \(2\), jak i do wierzchołka \(5\) (po tej operacji saldo w wierzchołku \(1\) wynosi \(-1\)). Zauważmy, że to przelanie do wierzchołka \(5\) nie było nam na rękę, ponieważ tam saldo było już równe \(0\), ale możemy cofnąć tę operację, wykonując tym razem przelanie z wierzchołka \(5\) do jego sąsiadów. Jedynym jego sąsiadem jest wierzchołek \(1\), więc taka operacja spowoduje, że teraz w każdym wierzchołku już mamy saldo \(0\). Zatem udało nam się wykonać rozliczenie, korzystając z czterech operacji. Tak więc odpowiedź w tym przykładzie wynosi ,,tak”.

W zadaniu proszą nas również o podanie minimalnej liczby operacji, za pomocą których możemy dokonać rozliczenia. Tutaj udało nam się zrobić przykład z czterema operacjami. To, że rzeczywiście to jest liczba minimalna, pokażemy później.

Warunek konieczny

Warto zastanowić się na początek nad jakimś przykładem, w którym odpowiedź wynosi ,,nie”. Łatwo jest taki przykład pokazać. Może być to graf dwuwierzchołkowy: w wierzchołku \(1\) saldo nie musi się zmienić, natomiast w wierzchołku \(2\) chcielibyśmy zwiększyć saldo o \(1\).

Widać, że w tym przypadku odpowiedź jest ,,nie”. Wynika to z prostego faktu, że początkowa suma pieniędzy w banku wynosi \(0\), natomiast wymagamy, żeby po rozliczeniu całkowita suma pieniędzy w banku wynosiła \(1\). Każda operacja jedynie przesuwa pieniądze pomiędzy wierzchołkami i nie powoduje, że sumaryczna ilość pieniędzy w banku zmienia się. Wobec tego, jeżeli początkowa suma pieniędzy nie równa się końcowej sumie pieniędzy po wszystkich wierzchołkach, no to wtedy od razu możemy powiedzieć, że odpowiedź jest ,,nie”.

Symulacja przelania do jednego sąsiada

Oczywiste pytanie jest, czy są to jedyne takie przypadki, w których stwierdzamy ,,nie”.

W naszym zadaniu musimy wykonywać dość specyficzne rodzaje operacji i niekoniecznie mamy intuicję, jak te operacje ze sobą współdziałają i co możemy tak naprawdę za pomocą tych operacji zrobić. Zauważmy, że gdyby te operacje były bardziej naturalne (na przykład taką naturalną operacją jest przelanie jednego bajtalara z jednego wierzchołka do jego sąsiada), to dzięki takim prostszym operacjom na pewno udałoby nam się dokonać przelewów, o ile tylko początkowe i końcowe salda byłyby takie same. Można więc zapytać, czy bylibyśmy w stanie za pomocą tych naszych operacji z zadania zasymulować taką prostą operację, to znaczy przelanie jednego bajtalara z jednego wierzchołka do drugiego.

Zauważmy, że tak naprawdę takiego rodzaju operacje musimy umieć zrobić, no bo odpowiada ona testowi, w którym mamy drzewo i w każdym wierzchołku mamy zmianę salda równą \(0\), natomiast w jednym wierzchołku chcemy, żeby różnica była \(1\), a w jakimś jego sąsiedzie, żeby różnica wynosiła \(-1\). Jeśli spróbujemy rozwiązać taki przykład, to okaże się, że wszystkie wierzchołki, w których wykonywaliśmy operacje, znajdują się w poddrzewie tego wierzchołka, z którego przelewaliśmy pieniądze. Co więcej, wszystkie wierzchołki z tego poddrzewa miały wykonaną operację i każdy miał wykonaną operację dokładnie raz. Nie jest to przypadek i całkiem łatwo jest udowodnić przez indukcję, że wykonanie operacji we wszystkich wierzchołkach dla tego poddrzewa spowoduje, że prześlemy jednego bajtalara z korzenia tego poddrzewa do jego rodzica.

Jeżeli poddrzewo jest jednowierzchołkowe, czyli tak naprawdę jest liściem, to wykonanie na tym liściu operacji spowoduje po prostu przesłanie jednego bajtalara w górę do rodzica. Czyli to jest baza indukcji, a następnie robimy indukcję po budowie drzewa. Jeżeli mamy jakiś wierzchołek \(v\) i jego dzieci, to z założenia indukcyjnego wiemy, że wykonanie operacji na wszystkich dzieciach spowoduje przesłanie jednego bajtalara w górę każdego drzewa. Wobec tego, jeżeli mamy \(k\) dzieci, to dostaniemy \(+k\) w wierzchołku \(v\).

Wykonujemy teraz operację w wierzchołku \(v\). Powoduje ona, że oddajemy wszystkim dzieciom z powrotem ich bajtalary i przesyłamy jeszcze jednego bajtalara w górę drzewa i powodujemy, że w rodzicu \(v\) bilans jest \(-1\), czyli to, co chcieliśmy uzyskać. Tak więc widzimy, że za pomocą operacji z treści zadania, które przesyłają pieniądze do wszystkich sąsiadów danego wierzchołka, jesteśmy w stanie zasymulować zwykłą operację przesyłu, która przesyła jedynie do jednego sąsiada.

Warunek dostateczny

Dzięki tej symulacji możemy już odpowiedzieć na pytanie, kiedy odpowiedź w treści zadania jest ,,tak”. Ponieważ dzięki zwykłym operacjom jesteśmy w stanie dokonać rozliczenia, o ile suma początkowa pieniędzy jest równa sumie końcowej, tak więc widać, że za pomocą tych operacji z treści zadania również jesteśmy w stanie to wykonać. Wobec tego, jeżeli saldo początkowe i końcowe są równe, to odpowiedź w zadaniu jest ,,tak”.

Dzięki tej naszej symulacji możemy również znaleźć pewien sposób wykonywania operacji, który spowoduje wykonanie rozliczenia. Można sobie wyobrażać, że w tym zadaniu mamy do czynienia z przepływem pieniędzy, w którym wierzchołkami źródłowymi są wierzchołki z dodatnią ilością pieniędzy, a wierzchołkami ujściami są wierzchołki z ujemnym bilansem. Musimy znaleźć jakiś taki najtańszy przepływ w tym drzewie. Tu okazuje się pożyteczne przyjrzenie się, jak taki przepływ będzie wyglądał na ustalonej krawędzi.

Powiedzmy, że wybraliśmy sobie tę pewną krawędź, i ona dzieli nam drzewo na dwa poddrzewa. Powiedzmy, że suma wartości po wszystkich wierzchołkach w jednym poddrzewie wynosi jakieś \(s\). Oznacza to, że w drugim poddrzewie mamy \(-s\), ponieważ suma musi być równa \(0\), jeżeli ma się dać wykonać rozliczenie. Zatem musimy przesłać \(s\) bajtalarów z pierwszego poddrzewa do drugiego. To znaczy, że operację zwykłego przelewu z wierzchołka, który jest korzeniem pierwszego poddrzewa, do wierzchołka, który możemy reprezentować jako korzeń drugiego poddrzewa, musimy wykonać dokładnie \(s\) razy.

Jeżeli chcemy wykonać operację z treści zadania, to musimy dla każdego wierzchołka z pierwszego poddrzewa zwiększyć licznik wykonanych operacji o \(s\). Zauważmy, że wystarczy trzymać licznik tych operacji, bo tak naprawdę nie jest istotne, w jakiej kolejności te operacje będziemy wykonywać; istotne jest tylko dla każdego wierzchołka, ile wykonamy w nim operacji.

Czyli algorytm na znalezienie rozliczenia może wyglądać następująco. Dla każdej krawędzi patrzymy sobie na dwa poddrzewa, które ona łączy i na sumy liczb w tych poddrzewach. Następnie dla poddrzewa, którego suma jest dodatnia i wynosi jakieś \(s\), w każdym wierzchołku tego poddrzewa zwiększamy licznik o \(s\).

Łatwo jest zrealizować taki algorytm w czasie \(O(n^2)\). Dla każdej z \(n - 1\) krawędzi w liniowym czasie jesteśmy w stanie posumować poddrzewa i zaznaczyć wierzchołki.

Algorytm wzorcowy

Można to jednak zrobić szybciej. Ukorzenimy sobie nasze drzewo i wykonamy na nim kilka przebiegów algorytmu DFS. W pierwszym przebiegu policzymy dla każdego węzła, jaka jest suma wartości w poddrzewie zaczepionym w tym węźle. To można zrobić bardzo prostym programowaniem dynamicznym.

Podczas drugiego przejścia DFS będziemy rozważać każdą krawędź drzewa. Dzięki temu będziemy wiedzieli, jakie sumy występują w obu poddrzewach, na które dzieli drzewo ta krawędź. Jeżeli w dolnym poddrzewie mamy sumę \(s\), no to znaczy, że w górnym mamy \(-s\). Teraz chcemy jakoś szybko zaznaczać wszystkie wierzchołki w poddrzewie, więc zrobimy to następująco. Jeżeli suma w dolnym poddrzewie jest dodatnia, to do korzenia tego poddrzewa dodajemy wartość \(s\). Idea jest taka, że to znaczy, że będziemy dodawać tę wartość do wszystkich wierzchołków znajdujących się w tym poddrzewie.

Natomiast jeżeli suma jest ujemna, no to wtedy chcielibyśmy dodać tę wartość do wszystkich wierzchołków poza tym poddrzewem. Więc zrobimy taki trik, że dodamy \(-s\) do całego drzewa (to będzie równoważne temu, że odejmiemy \(s\) od korzenia drzewa), a następnie odejmiemy \(-s\) od korzenia dolnego poddrzewa.

Jak przepatrzymy już wszystkie krawędzie, to wykonujemy ostatnie przejście algorytmem DFS, w którym będziemy propagować wartości zapisane w węzłach do wszystkich dzieci. To znaczy, że jeżeli w jakimś węźle mamy zapisaną wartość \(x\), to znaczy, że robimy w nim \(x\) operacji, to dodamy tego \(x\) do wartości we wszystkich dzieciach, a następnie odpalimy się rekurencyjnie dla tych dzieci.

Dzięki temu za pomocą trzech przejść algorytmu DFS w czasie liniowym jesteśmy w stanie wyznaczyć liczbę operacji w każdym węźle.

Minimalność rozwiązania

Pytanie, czy uzyskane rozwiązanie, które generuje poprawne rozliczenie, jest minimalne, to znaczy używa minimalnej liczby operacji. Niestety nie musi tak być. Żeby się o tym przekonać, zobaczmy na naszym teście przykładowym, jakie rozwiązanie jest generowane przez nasz algorytm.

Jeżeli rozważymy krawędź \(3-1\), to ona dzieli nam nasze drzewo na dwa poddrzewa, z czego jedno ma sumę \(-1\) i jeden wierzchołek, a drugie sumę \(1\) i cztery wierzchołki (i dla nich wykonujemy po jednej operacji).

Dla krawędzi \(5-4\) nic nie musimy robić, ponieważ ona dzieli na poddrzewa o sumie \(0\). Krawędź \(1-2\) dzieli na sumę \(-1\) i \(1\) (dwa wierzchołki po jednej operacji). Ostatnia krawędź dzieli na dwa zbiory o sumie \(-2\) i \(2\) (cztery wierzchołki po dwie operacje).

Widać, że w sumie zużyjemy aż \(14\) operacji, żeby wykonać rozliczenie. To jest dużo więcej niż cztery operacje podane w rozliczeniu wyżej. Widać w szczególności, że rozwiązanie wcale nie musi być wyznaczone jednoznacznie.

Ale gdy przyjrzymy się tym dwóm rozwiązaniom, obu generującym poprawne rozliczenie, i porównamy liczbę operacji wykonywanych w każdym wierzchołku, to okaże się, że to dolne rozwiązanie w każdym wierzchołku wykonuje dokładnie o \(2\) operacje więcej niż górne rozwiązanie. Tę obserwację można uogólnić: okazuje się, że jeżeli mamy poprawne rozwiązanie i do każdego wierzchołka dodamy stałą liczbę operacji, to nadal to rozwiązanie będzie generowało takie samo rozliczenie. Wynika to z faktu, że jeżeli wykonamy po jednej operacji w każdym wierzchołku naszego drzewa, to wrócimy do sytuacji początkowej.

To jest całkiem łatwo uzasadnić, ponieważ jeżeli mamy jakiś liść oraz całą resztę drzewa, to wykonanie operacji we wszystkich wierzchołkach reszty drzewa powoduje przesłanie jednego bajtalara do liścia, no i wykonanie jeszcze operacji w liściu powoduje wysłanie tego bajtalara z powrotem (czyli cofnięcie operacji). Tak więc możemy znaleźć wierzchołek z minimalną liczbą operacji \(p\) i od każdego wierzchołka odjąć po \(p\) tych operacji.

Pytanie, czy teraz jest to już rozwiązanie optymalne? W tym przypadku to jest prawda, ale też w ogólnym przypadku taki algorytm zadziała i zwróci prawidłową odpowiedź. Wynika to z obserwacji, że rzeczywiście możemy wziąć dowolne rozwiązanie i dodać stałą liczbę operacji do każdego wierzchołka i wtedy uzyskamy inne poprawne rozwiązanie. Jednakże obserwacja ta działa również w drugą stronę. To znaczy wszystkie poprawne rozwiązania różnią się o stałą.

Aby to uzasadnić, popatrzmy jeszcze raz na pewną krawędź, która łączy dwa poddrzewa. Na podstawie sum w tych poddrzewach my wiemy, ile bajtalarów musimy przesłać tą krawędzią. Kwestia jest tylko taka, że aby przesłać te bajtalary, my musimy wykonać operację w korzeniu poddrzewa o dodatniej sumie. Wszelkie operacje na innych węzłach tego poddrzewa jedynie przywracają nam bilans w tym poddrzewie.

Tak więc jeżeli oznaczymy sobie przez \(a\) liczbę operacji wykonanych w korzeniu jednego drzewa, a przez \(b\) liczbę operacji wykonanych w korzeniu drugiego poddrzewa, to wiemy, że te liczby muszą spełniać równanie \(a - b = s\). Takie równanie możemy zapisać dla każdej krawędzi.

Wobec tego, jeżeli ustalimy, ile operacji wykonamy w choć jednym wierzchołku naszego drzewa, to w ten sposób jednoznacznie wyznaczymy, ile operacji będziemy wykonywać w każdym innym wierzchołku.

Rozwiązanie alternatywne

Z rozumowania, które przed chwilą przeprowadziliśmy, wynika jeszcze jedna ciekawa rzecz, a mianowicie jeszcze prostszy algorytm rozwiązujący nasze zadanie. Zauważmy, że możemy ustalić liczbę operacji w jakimś wierzchołku. Powiedzmy w korzeniu drzewa ustalmy, że mamy \(0\) operacji, a następnie przejdziemy sobie algorytmem DFS i dla każdej krawędzi będziemy znając liczbę \(s\) oraz liczbę operacji, które mamy wykonane w rodzicu, czyli w górnym węźle tej krawędzi będziemy w stanie wyznaczyć, ile operacji musimy wykonać w dziecku.

W ten sposób będziemy w stanie w czasie liniowym za pomocą jednego przejścia algorytmu DFS wyznaczyć pewne rozwiązanie. W tym rozwiązaniu możemy mieć taką sytuację, że w jakimś wierzchołku wyznaczymy ujemną liczbę operacji, no ale tak jak w poprzednim rozwiązaniu braliśmy sobie na końcu od wszystkich wierzchołków odejmowaliśmy minimum, minimalną liczbę operacji, która występowała wśród wierzchołków drzewa, tak tutaj również odejmiemy minimalną liczbę operacji. No więc jeżeli jakiś wierzchołek z minimalną liczbą operacji ma ich ujemną liczbę, no to wtedy to odejmowanie spowoduje, że dodamy tę liczbę operacji do wszystkich wierzchołków, dzięki czemu na końcu wierzchołki będą miały nieujemną liczbę operacji.

Oszacowanie wielkości wyniku

Pozostała jeszcze do omówienia jedna pułapka, która czyhała na zawodników w tym zadaniu, a mianowicie można było nie zauważyć, że wynik w tym zadaniu może być naprawdę duży. Rozważmy sobie taki przykład, w którym drzewo jest długą ścieżką zawierającą \(n - 1\) krawędzi. Pierwszy wierzchołek tego drzewa będzie miał tutaj wagę \(w\), a ostatni \(-w\). Pozostałe będą miały \(0\). Pytanie, ile potrzebują operacji, żeby przenieść te wszystkie \(w\) bajtalarów z pierwszego wierzchołka do ostatniego.

Każda krawędź będzie nam dzieliła tę ścieżkę na dwie ścieżki i będziemy musieli wykonać \(w\) operacji w każdym wierzchołku lewej ścieżki. Czyli widać, że sumarycznie będziemy musieli wykonać od \(O(n^2)\) takich paczek operacji, a w każdej paczce będziemy mieli \(w\) operacji. Czyli wynik może wynosić nawet \(n^2 \cdot w\). Ten test można wzmocnić, dodając jeszcze więcej wierzchołków z niezerowymi wagami.

Na początku ścieżki \(\frac{n}{2}\) wierzchołków o wadze \(w\) i na końcu \(\frac{n}{2}\) wierzchołków o wadze \(-w\). To spowoduje, że liczba operacji wzrośnie nam aż do \(n^3 \cdot w\). Ponieważ \(n\) było ograniczone przez \(10^6\), a \(w\) przez \(10^9\), to widać, że ten wynik będzie mógł być nawet rzędu \(10^{27}\), więc nie zmieści się ani w typie int, ani w typie 64-bitowym long long. Będzie wymagał albo użycia typu 128-bitowego, albo zaimplementowania własnej arytmetyki. Na szczęście do reprezentowania liczb we własnej arytmetyce wystarczą dwie zmienne long long, więc operacje na tych liczbach będą wykonywane w czasie stałym. Nie wpłynie to więc na ogólną złożoność czasową naszego rozwiązania, które pozostaje liniowe.