W zadaniu Wyspa z IX Olimpiady Informatycznej danych było n miast ułożonych na okręgu oraz odległości między dwoma sąsiednimi miastami. Należało znaleźć największą odległość między dwoma miastami, przy czym odległość między dwoma miastami definiujemy jako mniejszy z dystansów: zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara.
Na rysunku powyżej widzimy przykładową wyspę. Największa odległość między dwoma miastami wynosi 7. Są to miasta dolne prawe oraz górne lewe. Dystans między nimi, idąc zgodnie z ruchem wskazówek zegara wynosi 2 + 1 + 5 = 8. Natomiast idąc przeciwnie wynosi 3 + 4 = 7. Zatem odległość między tymi miastami wynosi 7 i jest to największa odległość pomiędzy wszystkimi miastami na wyspie.
Zacznijmy od czegoś bardzo prostego. Mając odległości między sąsiednimi miastami, policzmy odległość między miastem i oraz j.
int odleglosc(const vector<int>& wyspa, int i, int j)
{
int zgodnie = 0;
int przeciwnie = 0;
for (int k = 0; k < wyspa.size(); k++)
if (i <= k and k < j)
zgodnie += wyspa[k];
else
przeciwnie += wyspa[k];
if (zgodnie < przeciwnie)
return zgodnie;
return przeciwnie;
}W pętli for funkcja przechodzi po wszystkich elementach tablicy. Jeśli indeks elementu znajduje się w przedziale [i, j) to odległość dodajemy do zmiennej zgodnie, w przeciwnym przypadku dodajemy ją do zmiennej przeciwnie. Na końcu sprawdzamy, która z tych dwóch zmiennych jest mniejszą i tą zwracamy jako wynik.
Mając tę funkcję, możemy napisać program rozwiązujący nasze zadanie.
int rozwiazanie(const vector<int>& wyspa)
{
int maksymalna = 0;
for (int i = 0; i < wyspa.size(); i++)
for (int j = i + 1; j <= wyspa.size(); j++)
{
int obecna = odleglosc(wyspa, i, j);
if (obecna > maksymalna)
maksymalna = obecna;
}
return maksymalna;
}Funkcja przechodzi po wszystkich możliwych parach miast i oraz j, liczy odległość między tymi miastami i znajduje spośród nich największą. Ponieważ program sprawdza wszystkie możliwe pary miast, a jest ich O(n^2) i dla każdej z nich uruchamia funkcję odległość, która działa w czasie O(n) to cały algorytm działa w czasie O(n^3). Nie jest to najlepsza złożoność, ale takie rozwiązanie gwarantowało 40 punktów na Olimpiadzie (na 100 możliwych). W jaki sposób możemy zmniejszyć złożoność naszego algorytmu?
Metoda I: nie licz dwa razy tych samych rzeczy
Jeżeli nasz algorytm policzył coś to nierozsądne byłoby mu kazać liczyć to drugi raz. Zwłaszcza jeśli policzenie tego czegoś zajęło mu sporo czasu. Sprawdźmy w którym miejscu nasz algorytm liczy ponownie te same rzeczy.
Przyjrzyjmy się w jaki sposób liczona jest zmienna zgodnie. Jeśli i = 2 oraz j = 7, zmienna zgodnie jest liczona zgodnie ze wzorem:
wyspa[2] + wyspa[3] + wyspa[4] + wyspa[5] + wyspa[6]
Ale za chwilę będziemy liczyć odległości dla miast i = 2 oraz j = 8:
wyspa[2] + wyspa[3] + wyspa[4] + wyspa[5] + wyspa[6] + wyspa[7]
I cała ta suma zostanie obliczona od początku. Mimo tego, że duża część tej sumy była już wcześniej policzona. Gdybyśmy zapamiętali tę sumę, wystarczyłoby do niej dodać wyspa[7] i w ten sposób obliczylibyśmy nową sumę używając jedynie jednego dodawania (a nie pięciu!). Podobnie moglibyśmy poczynić ze zmienną przeciwnie. Jednak dla uproszczenia zrobimy inaczej. Zauważmy, że zachodzi następująca równość:
przeciwnie = suma – zgodnie
Gdzie suma to suma wszystkich elementów tablicy wyspa. Możemy ją obliczyć na początku programu i używać jej później w dalszej części algorytmu. Nasz program wygląda teraz następująco:
int rozwiazanie(const vector<int>& wyspa)
{
int maksymalna = 0;
int suma = 0;
int zgodnie, przeciwnie, odleglosc;
for (int i = 0; i < wyspa.size(); i++)
suma += wyspa[i];
for (int i = 0; i < wyspa.size(); i++)
{
zgodnie = 0;
for (int j = i + 1; j <= wyspa.size(); j++)
{
zgodnie += wyspa[j - 1];
przeciwnie = suma - zgodnie;
if (zgodnie < przeciwnie)
odleglosc = zgodnie;
else
odleglosc = przeciwnie;
if (odleglosc > maksymalna)
maksymalna = odleglosc;
}
}
return maksymalna;
}Przez to, że nie powtarzamy teraz obliczania tych samych wartości wielokrotnie, zredukowaliśmy czas działania naszego algorytmu do O(n^2). Takie rozwiązanie na olimpiadzie dawało 60 punktów.
Metoda II: nie licz rzeczy, które są bez sensu
Jeżeli wiemy, że pewne obliczenia w naszym algorytmie nie kontrybuują do ostatecznego wyniku, to po co je wykonywać? Usunięcie takich obliczeń prawie zawsze przyśpieszy działanie naszego algorytmu, a czasami nawet zmniejszy złożoność naszego algorytmu.
Co takiego liczymy bez sensu w naszym algorytmie. Odpowiedzi na to udzieli następujący lemat:
Lemat 1. Jeżeli dla miast i oraz j dystans zgodny z ruchem wskazówek zegara jest większy niż dystans przeciwny do ruchu wskazówek zegara, to miasta i oraz k dla każdego k spełniającego j < k <= n nie mają szansy być parą miast o największej odległości.
Aby lepiej zrozumieć ten lemat, rozpiszmy sobie go dokładnie. Dystans zgodny z ruchem wskazówek zegara jest równy:
zgodnie = wyspa[i] + wyspa[i+1] + … + wyspa[j-1]
Dystans w stronę przeciwną to suma pozostałych elementów, czyli:
przeciwnie = suma – zgodnie
Ponadto wiemy, że:
zgodnie > przeciwnie
Zatem:
odleglosc = przeciwnie
Weźmy teraz dowolne k spełniające j < k <= n. Policzmy odpowiadającą mu wartość zgodnie.
zgodnie’ = wyspa[i] + wyspa[i+1] + … + wyspa[j-1] + wyspa[j] + … + wyspa[k-1]
Ponieważ odległości między sąsiadującymi wyspami są dodatnie, wartość zgodnie’ jest większa od wartości zgodnie. Z drugiej zaś strony wartość przeciwnie’ jest mniejsza od wartości przeciwnie:
przeciwnie’ = suma – zgodnie’ < suma – zgodnie = przeciwnie
Łatwo wywnioskować, że przeciwnie’ musi być mniejsze od zgodnie’ (choćby dlatego, że zgodnie’ > zgodnie > przeciwnie > przeciwnie’) zatem:
odleglosc’ = przeciwnie’
A co za tym idzie:
odleglosc’ = przeciwnie’ < przeciwnie = odleglosc
Zatem każda odległość między miastem i-tym a k-tym (gdzie j < k <= n) jest mniejsza niż odległość między miastami i oraz j (jeżeli dla miast i oraz j zachodzi zgodnie > przeciwnie). Wystarczy więc policzyć odległość między miastami i oraz j. Odległości między miastami i oraz k liczyć nie musimy.
Wiem, że rączki już świerzbią, aby wprowadzić zmiany do naszego algorytmu. Ale zanim to nastąpi, przyjrzyjmy się bliźniaczo podobnemu lematowi drugiemu.
Lemat 2. Jeżeli dla miast i oraz j dystans zgodny z ruchem wskazówek zegara jest mniejszy niż dystans przeciwny do ruchu wskazówek zegara, to miasta k oraz j dla każdego k spełniającego i < k < j nie mają szansy być parą miast o największej odległości.
Dowód lematu jest analogiczny jak dowód lematu 1. Możemy przystąpić do pisania naszego algorytmu.
void aktualizuj(int& maksymalna, int zgodnie, int przeciwnie)
{
int odleglosc;
if (zgodnie < przeciwnie)
odleglosc = zgodnie;
else
odleglosc = przeciwnie;
if (odleglosc > maksymalna)
maksymalna = odleglosc;
}
int rozwiazanie(const vector<int>& wyspa)
{
int maksymalna = 0;
int suma = 0;
int zgodnie, przeciwnie;
for (int i = 0; i < wyspa.size(); i++)
suma += wyspa[i];
int j = 0;
zgodnie = 0;
przeciwnie = suma;
for (int i = 0; i < wyspa.size(); i++)
{
while (zgodnie < przeciwnie and j < wyspa.size())
{
zgodnie += wyspa[j];
przeciwnie -= wyspa[j];
if (zgodnie == przeciwnie)
return zgodnie;
aktualizuj(maksymalna, zgodnie, przeciwnie);
j++;
}
zgodnie -= wyspa[i];
przeciwnie += wyspa[i];
aktualizuj(maksymalna, zgodnie, przeciwnie);
}
return maksymalna;
}Pętla while w której zwiększamy wartość zmiennej j zatrzymuje się teraz gdy tylko zmienna zgodnie stanie się większa od przeciwnie (lemat 1). Ponadto teraz nigdy nie musimy zmniejszać zmiennej j (lemat 2). Ponieważ zmienną maksymalna musimy teraz aktualizować w dwóch miejscach – wydzieliliśmy kod do funkcji aktualizuj.
Wprawdzie w pętli for znajduje się pętla while, ale pętla while zwiększa zmienną j. Nigdzie w kodzie zmienna j nie zostaje zmniejszona, a ponadto zmienna j nie może być większa nigdy niż wyspa.size(). Oznacza to, że wnętrze pętli while nie wykona się więcej niż n razy. Zatem nasz algorytm działa w czasie O(n) i uzyskałby 100 punktów na olimpiadzie informatycznej.
Przedstawiłem w tej notce dwie wydaje się łatwe metody na zbicie złożoności obliczeniowej. Jak widać na przykładzie zadania wyspa, użycie ich może okazać się bardzo skuteczne. Polecam pamiętać o tych metodach zwłaszcza na początku swojej przygody z programowaniem.
