Runda 3: Moda na zwycięstwo (rozwiązanie)

Autor zadania: Jarosław Gomułka

Na początku zastanówmy się nad najprostszą poprawną metodą rozwiązania tego problemu. Możemy przeiterować się po wszystkich możliwych okresach czasu.

Następnie sprawdzić które osoby były ze sobą w związku w choć jednym odcinku w tym okresie, dodać do grafu G krawędzie pomiędzy osobami z każdego z tych związków. Sprawdzenie czy okres spełnia warunek z treści zadania to przeiterowanie się po synach każdej osoby i sprawdzenie, czy istnieje ścieżka pomiędzy numerami tych osób w grafie G

int ans = nieskończoność;
for(int start=1; start<=1000000000; start++)
	for(int koniec=start; koniec<=1000000000; koniec++)
		G = inicjuj_pusty_multigraf
		dla kazdego zwiazku Z sprawdź
			jeśli czas trwania Z ma niepustą cześć wspólną z okresem [start,koniec] to
				dodaj krawedz pomiedzy osobami ze zwiazku Z do multigrafu G
		dla kazdej pary (A,B) //A = osoba, B = rodzic tej osoby):
			jesli istnieje sciezka z A do B w grafie G to
				ans = min(ans, koniec-start+1)
return ans

Jeśli zwrócona wartość wynosi nieskończoność to należy wypisać NIE. Czas działania tego algorytmu jest zdecydowanie za duży nawet dla najmniejszych danych. Możemy go jednak poprawić poprzez zauważenie pewnej prawidłowości:

Niech C oznacza zbiór numerów odcinków w których zaczynał się lub kończył się jakiś związek. Czas startu i końca, conajmniej jednego najkrótszego szukanego okresu należy do zbioru C. Dowód. Jeśli start nie należy do C to możemy zwiększyć start o 1 i nie musimy usuwać z G żadnego związku. Jeśli koniec nie należy do C to możemy zmniejszyć koniec o 1 i nie musimy usuwać z G żadnego związku.

Udało się zoptymalizować rozwiązanie do takiej formy:

int ans = nieskończoność;
for(int i=0; i<C.size(); i++)
	for(int j=i; j<C.size(); j++)
		start = C[i]
		koniec = C[j]
		
		G = inicjuj_multigraf_pusty
		dla kazdego zwiazku Z sprawdz
			jeśli czas trwania Z ma niepustą cześć wspólną z [start,koniec] to
				dodaj krawedź pomiędzy osobami ze związku Z do multigrafu G
		dla kazdej pary (A,B) //A = osoba, B= rodzic tej osoby):
			jesli istnieje sciezka z A do B w grafie G to
				ans = min(ans, koniec-start+1)
return ans

Złożoność tego algorytmu to O(m^2 * (m +n*(n+m))) = O(m^2 *n * (n+m))  Jest to algorytm lepszy ale nadal daleki od optymalnego. Optymalizujmy go dalej!

Założmy, że mamy obliczony graf G dla okresu czasu [C[i],C[j]]. Chcemy obliczyć graf G' dla okresu czasu [C[i],C[j+1]]. Zauważmy, że nie musimy od nowa budować całego grafu G', wystarczy dodać te związki do grafu G które zaczynają się w momencie C[j+1]

Dodatkowo zauważmy że jeśli okres [C[i],C[j]] nie jest rozwiązaniem to nie ma sensu sprawdzać co się dzieje dla okresu [C[i],C[j+1]] gdyż wyniku i tak nie poprawimy.

Algorytm wygląda teraz tak:

int ans = nieskończoność;
for(int i=0; i<C.size(); i++){
	start = C[i]
	G = inicjuj_pusty_multigraf
	dodaj do G wszystkie zwiazki które trwają w odcinku o numerze start
	
	for(int j=i; j<C.size(); j++){
		koniec = C[j]
		znajdz wszystkie zwiazki Z które zaczynają się w momencie C[j+1]
			dodaj krawedz pomiedzy osobami ze zwiazku Z do G
		dla kazdej pary (A,B) //A = osoba, B= rodzic tej osoby):
			jesli istnieje sciezka z A do B w grafie G to
				ans = min(ans, koniec-start+1)
				goto end_loop;
	}
	endloop:;
}
return ans

Złożoność tego algorytmu to O(m^2 * n * (n+m) ). W złożoności nic nie poprawiliśmy jednak w praktyce ten algorytm będzie działał dużo szybciej od poprzedniego algorytmu.

Szukajmy dalszych optymalizacji! Załóżmy, że mamy obliczony graf G dla okresu czasu [C[i],C[j]], w tym momencie nastąpił BREAK, mamy obliczyć graf [C[i+1],C[i+2]] Zauważmy że ponieważ dla start=C[i], BREAK nastąpił dopiero dla końca równego C[j] więc nie znajdziemy okresu o szukanej własności w żadnym okresie czasu spośród [C[i+1],C[k]] gdzie k<j.

Obliczymy więc odrazu graf G' dla okresu [C[i+1],C[j]]. Możemy to zrobić poprzez usunięcie z G tych krawędzi, które reprezentują związki zakończone w odcinku o numerze C[i]. Algorytm wygląda tak:

int ans = nieskończoność;
int i=0,j=0;
G = inicjuj_pusty_multigraf

while(i<C.size()){
	start = C[i]
	
	while(true){
		koniec = C[j]
		dla kazdej pary (A,B) //A = osoba, B= rodzic tej osoby):
			jesli istnieje sciezka z A do B w grafie G to
				ans = min(ans, koniec-start+1)
				goto end_loop;
		
		if (j==C.size())
			return ans; //nie znajdziemy już szukanych okresów.
		
		do G dodaj związki rozpoczynające się w czasie C[j]
		j++;
	}
	endloop:;
	
	usun z G wszystkie zwiazki które kończą sie w odcinku o numerze C[i]
	i++;
}
return ans 

Ten algorytm na pierwszy rzut oka może wyglądać na optymalny. Każdy zwiazek jest dodawany i usuwany conajwyżej raz podczas całego algorytmu. Ilość sprawdzań czy okres spełnia warunek jest rzędu O(m). Złożoność to O(m*n*(n+m)) Jednak sprawdzanie czy istnieje ścieżka w grafie nadal jest za wolne.

Pierwszym pomysłem jak to poprawić jest zastosowanie algorytmu Floyda-Warshala. Złożoność wyniesie wówczas O(m*n^3). Drugim pomysłem jest policzenie spójnych składowych grafu. Sprawdzenie czy istnieje ścieżka będzie wymagało sprawdzenia czy 2 wierzchołki należa do tej samej spójnej składowej. Złożoność wyniesie wówczas O(m*(n+m)). Obliczenie spójnych składowych zajmie O(n+m) ponieważ graf może być bardzo gęsty, pesymistycznie może zawierać m krawędzi.

Dobrym pomysłem byłoby zastanowić się czy krawędzi może być mniej. Otóż może być! A więc chcemy mieć mniejszy graf G'. Bądźmy ambitniejsi! Chcemy by miał mniej niż n krawędzi! Niech istnieje_ścieżka(G,a,b) odpowiada na pytanie czy w grafie G istnieje ścieżka pomiedzy wierzchołkami a i b.

Musimy się zastanowić jakie niezmienniki musi spełniać nasz graf. W końcu nie chcemy sprawić by algorym był niepoprawny.Interesuje nas istnienie ścieżek pomiędzy wierzchołkami, dokładniej dla każdego a i b musi zachodzić:

• istnieje_ścieżka(G,a,b) <=> istnieje_ścieżka(G',a,b).

Założmy że graf G ma conajmniej n krawędzi. Ponieważ mamy n wierzchołków i >=n krawędzi w G istnieje cykl. Jeśli usuniemy jedną dowolną krawędz z tego cyklu niezmiennik istnienia ścieżek zostanie zachowany. Jednak nie możemy usunąć dowolnej krawędzi. W dalszej cześci algorytmu może zostać usunięta kolejna krawędź z cyklu co popsuje nam niezmiennik istnienia ścieżek. Usuńmy więc z cyklu tą krawędź która zostanie usunięta jako pierwsza!

W ten sposób możemy pozbyć się wszystkich cykli. Graf bez cykli jest lasem. Las o n wierzchołkach ma mniej niż n krawędzi więc osiągneliśmy nasz cel! Precyzując, dodając krawędź do G nadajemy jej wage = numer odcinka w którym skończył sie związek reprezentowany przez tą krawędź. Przy każdym dodaniu krawędzi musimy sprawdzić czy nie pojawił się cykl i jeśli tak to usunąć najlżejszą krawędź należącą do tego cyklu.

Wszystkie te operacje da się zrobić w O(n).

Otrzymany algorytm powinien wyglądać następująco:

int ans = nieskończoność;
int i=0,j=0;
G = inicjuj_pusty_graf

while(i<C.size()){
	start = C[i]
	
	while(true){
		koniec = C[j]
		policz spojne skladowe G
		dla kazdej pary (A,B) //A = osoba, B= rodzic tej osoby):
			jesli numer spójnej składowej wierzchołka A = numer spójnej składowej wierzchołka B{
				ans = min(ans, koniec-start+1)
				goto end_loop;
			}
		
			if (j==C.size())
				return ans; //nie znajdziemy już szukanych okresów.
		
			do G dodaj związki rozpoczynające się w czasie C[j], po dodaniu każdej 
                           krawędzi sprawdź czy nie powstał cykl i jeśli tak to usuń 
                           najlżejszą krawędź z tego cyklu.
			j++;
	}
	endloop:;
	
	usun z G wszystkie zwiazki które kończą sie w odcinku C[i] 
          ( o ile zwiazki te nie zostały już wcześniej usunięta)
	i++;
}
return ans 

Jest to algorytm wzorcowy. Analiza złożoności: Mamy m krawędzi każda zostanie dodana i usunięta conajwyżej raz. Conajwyzej m razy obliczone zostaną spójne składowe G. Operacje dodania, usunięcia krawędzi, obliczania spójnych składowych zostaną obliczone w O(n). Złożoność sumaryczna O(n*m). W praktyce da się uzyskać złożoność O(n*logm), przy pomocy nieco bardziej skomplikowanych narzędzi niż te, które omówiliśmy.