[naglowek]

wersja PS     wersja PS.ZIP
Wstęp
Sprawozdanie z przebiegu VII OI
Regulamin
Zasady organizacji zawodów
Informacja o IOI'99
Etap I
Etap II
Etap III
 
Lollobrygida
Jajka
Po-łamana
Agenci
Powtórzenia
Promocja
IOI
Literatura

Spis treści
O wersji online

Niebieskie książeczki
 
Olimpiada Informatyczna
Kącik zadań
Archiwum zadań
CEOI'97
 
   Tomasz Waleń (treść, opracowanie)    Marcin Mucha (program wzorcowy)

Agenci

W związku z ostatnimi wpadkami swoich agentów, Urząd Ochrony Bajtocji postanowił usprawnić działalność.

Największym dotychczasowym problemem było bezpieczne urządzanie spotkań agentów. Twój program ma pomóc w rozwiązaniu tego problemu. Dla podanego opisu sieci dróg Bajtocji oraz początkowej pozycji dwóch agentów, powinien stwierdzać, czy możliwe jest bezpieczne spotkanie tych agentów.


Żeby spotkanie uznać za bezpieczne agenci muszą przestrzegać następujących reguł:

  • agenci poruszają się w dzień, natomiast spotkania odbywają się wieczorami,
  • każdego dnia agent musi zmienić miejsce pobytu,
  • agenci mogą poruszać się jedynie po drogach łączących miasta (niestety dodatkowym utrudnieniem jest fakt, iż w Bajtocji drogi są jednokierunkowe),
  • agent nie może jednak poruszać się zbyt szybko (mogło by to wzbudzać niepotrzebne zainteresowanie) - jednego dnia nie może przemieścić się dalej niż do sąsiedniego miasta,
  • odległość między dwoma miastami połączonymi drogą jest na tyle mała, że agent wyruszający z pierwszego miasta zawsze dotrze do drugiego miasta przed wieczorem,
  • spotkanie uznaje się za odbyte w momencie, gdy dwaj agenci znajdą się tego samego wieczora w tym samym mieście.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego AGE.IN liczbę miast i opis sieci dróg Bajtocji, oraz pozycje początkowe dwóch agentów,
  • stwierdzi, czy możliwe jest ich bezpieczne spotkanie, a jeśli tak, to po ilu dniach,
  • zapisze wynik w pliku tekstowym AGE.OUT.

Wejście

W pierwszym wierszu pliku tekstowego AGE.IN znajdują się dwie liczby całkowite n i m, oddzielone pojedynczym odstępem, gdzie 1 leq n leq 250, 0 leq m leq ncdot(n-1).

W drugim wierszu znajdują się dwie liczby całkowite a1 i a2 oddzielone pojedynczym odstępem, 1 leq a_1, a_2 leq n oraz a_1 neq a_2, oznaczające, odpowiednio, początkowe pozycje agentów nr 1 i nr 2.

W m następnych wierszach znajdują się pary liczb naturalnych a i b oddzielone pojedynczymi odstępami, 1 leq a,b leq n oraz a ne b, oznaczające istnienie drogi z miasta a do miasta b.

Wyjście

Plik tekstowy AGE.OUT powinien zawierać dokładnie 1 wiersz zawierający:

  • dokładnie jedną dodatnią liczbę całkowitą t, oznaczającą minimalny czas (w dniach) potrzebny do zorganizowania bezpiecznego spotkania dwóch agentów - jeżeli do takiego spotkania można doprowadzić,
  • słowo NIE, gdy nie można doprowadzić do bezpiecznego spotkania.

Przykład

Dla pliku wejściowego AGE.IN
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
poprawną odpowiedzią jest plik wyjściowy AGE.OUT
3

Rozwiązanie

Sieć dróg Bajtocji reprezentujemy przez graf G o n wierzchołkach (miastach) i m krawędziach (drogach). Pierwszym, najbardziej narzucającym się rozwiązaniem, jest symulacja poruszania się obu agentów. Oznaczmy przez s=(i,j) stan obliczeń oznaczający, iż w tym samym czasie pierwszy agent może znajdować się w mieście o numerze i, a drugi w mieście o numerze j. Teraz rozważmy graf G' zbudowany na stanach s, ma on n2 wierzchołków i m2 krawędzi. W przypadku posługiwania się grafem G' problem sprowadza się do znalezienia najkrótszej ścieżki z wyróżnionego wierzchołka s_0=(a_1,a_2) do dowolnego wierzchołka postaci (i,i). Ponieważ wszystkie krawędzie mają wagę 1, więc wystarczy przejść graf G' wszerz. Nie trzeba konstruować grafu G' wprost, można także, jak w poniższym przykładzie, dynamicznie generować jego krawędzie.

1Q:={a_1,a_2};
2{ początkowo, dla dowolnego i, j: v[i,j]=0 }
3v[a_1,a_2]:=1;
4t:=0;
5while not Q.pusta do begin
6    Q2:=pusta_kolejka;
7    while not Q.pusta do begin
8        (u,v):=Q.PobierzElement;
9        if (u=v) then
10              ``Znaleziono rozwiązanie - t''
11              STOP;
12        for iin{k:(u,k) {rm; jest; krawŚdzi... do
13            for jin{k:(v,k) {rm; jest; krawŚdzi... do
14                if v[i,j]=0 then begin
15                    v[i,j]:=1;
16                    Q2.Dodaj(i,j);
17                end
18    end;
19    t:=t+1;
20    Q:=Q2;
21end;
22``Brak rozwiązania''

Schemat algorytmu (Q i Q2 oznaczają kolejki typu "pierwszy wchodzi-pierwszy wychodzi", czyli FIFO):

Teraz zastanówmy się jaką złożoność ma powyższy algorytm. Oznaczmy przez K(i,j) koszt jaki trzeba ponieść aby wygenerować następniki stanu (i,j). Wówczas K(i,j)=d_icdot d_j, gdzie dl oznacza liczbę krawędzi wychodzących z wierzchołka l. Ponieważ w pesymistycznym przypadku trzeba będzie rozpatrzyć wszystkie stany, całkowity koszt może wynosić:

n^2 + sum_i = 1..n sum_j = ...

   = n^2 + sum_i = 1..n left...

Łączny koszt to O(n^2+m^2).


Rozwiązanie wzorcowe polega na pewnym ulepszeniu poprzedniego rozwiązania. W poprzednim rozwiązaniu jedna faza algorytmu polegała na wykonaniu ruchu oboma agentami. Tym razem podzielimy tą fazę na dwie części: ruch pierwszym agentem i ruch drugim agentem. Co prawda takie rozwiązanie dwukrotnie powiększa przestrzeń stanów: s=(i,j) (ten sam stan co w poprzednim rozwiązaniu), oraz dochodzą nowe stany s'=(i',j'), oznaczające, że pierwszy agent wykonał już swój ruch i znajduje się na pozycji i', natomiast drugi powinien teraz wykonać ruch, a na razie znajduje się na pozycji j'. Jednak dzięki tej metodzie znajdowanie następników stanów jest nieco mniej kosztowne, dla stanów s=(i,j) potrzeba di operacji, natomiast dla stanów s'=(i',j') potrzeba d_j' operacji. Tak jak w poprzednim algorytmie, dotarcie do stanu s=(i,i) oznacza, że agenci mogą zorganizować bezpieczne spotkanie.

1Q:={a_1,a_2};
2{ początkowo, dla dowolnego i, j: v[i,j]=0, oraz v'[i,j]=0 }
3v[a_1,a_2]:=1;
4t:=0;
5while not Q.pusta do begin
6    Q2:=pusta_kolejka;
7
8    {ruch pierwszego agenta}
9    while not Q.pusta do begin
10        (u,v):=Q.PobierzElement;
11        if (u=v) then
12              ``Znaleziono rozwiązanie - t''
13              STOP;
14        for iin{k:(u,k) {rm; jest; krawŚdzi... do
15            if v'[i,v]=0 then begin
16                v'[i,v]:=1;
17                Q2.Dodaj(i,v)
18            end
19    end;
20
21    {ruch drugiego agenta}
22    while not Q2.pusta do begin
23        (u,v):=Q2.PobierzElement;
24        for iin{k:(v,k) {rm; jest; krawŚdzi... do
25            if v[u,i]=0 then begin
26                v[u,i]:=1;
27                Q.Dodaj(i,v)
28            end
29    end;
30
31    t:=t+1
32end;
33``Brak rozwiązania''

Teraz już możemy naszkicować schemat algorytmu (Q i Q2 oznaczają kolejki typu "pierwszy wchodzi-pierwszy wychodzi", czyli FIFO):

Analiza złożoności

Niech K(i,j) oznacza koszt poniesiony na znalezienie następników stanu s=(i,j). Tak więc K(i,j)=d_i. Analogicznie K'(i,j) oznacza koszt dla stanów typu s'=(i',j'), a zatem K'(i,j)=d_j. W pesymistycznym przypadku łączny koszt całego algorytmu wynosi:

2 n^2 + sum_i = 1..n sum_j ...

   = 2 n^2 + sum_i = 1..n n ...

Więc to rozwiązanie ma złożoność O(nm), co daje w pesymistycznym przypadku (dla grafów mających O(n^2) krawędzi) O(n^3) operacji.

Inne rozwiązania

Innym rozwiązaniem, mającym złożoność O(dm), gdzie d oznacza minimalny czas potrzebny do zorganizowania bezpiecznego spotkania (lub n2, jeśli takiego spotkania nie można zorganizować), jest obliczanie do jakich miast mogą dojść w i-tym kroku agenci nr 1 i 2. Jeśli te dwa zbiory mają część wspólną, oznacza to możliwość spotkania w i-tym dniu.

Niestety w niektórych przypadkach czas potrzebny do zoorganizowania spotkania może być bardzo duży, nawet rzędu n2. Tak więc w pesymistycznych przypadkach to rozwiązanie jest równie wolne jak pierwsze.

1V1:={a_1};
2V2:={a_2};
3dl:=0;
4while (not V1.pusty and not V2.pusty and dl<n^2) do
5begin
6    dl:=dl+1;
7    jeśli istnieje wierzchołek v należący do V1 i V2
8          to ``Znaleziono rozwiązanie'';
9    V1:=wierzchołki v takie, że istnieje wierzchołek u in V1
10              i (u,v) należy do G;
11    V2:=wierzchołki v takie, że istnieje wierzchołek u in V2
12              i (u,v) należy do G
13end;
14``Brak rozwiązania''

(Zmienne V1 i V2 oznaczają zbiory)

Testy

Do sprawdzania rozwiązań zawodników użyto 16 testów:

Testy oznaczone K_2(b_1,b_2,n) oznaczają testy składające się z dwóch pełnych grafów skierowanych (o rozmiarach b1, b2) połączonych ścieżką długości n

Testy oznaczone E(n_1,n_2,b_1,b_2) oznaczają testy składające się z dwóch pełnych grafów skierowanych (o rozmiarach b1, b2) połączone dwoma ścieżkami o wspólnym końcu, różniącymi się długością o 1. Na ścieżkach tych występują dodatkowo cykle długości n1, n2.

  • AGE0.IN - test z treści zadania,
  • AGE1.IN - mały graf z odpowiedzią negatywną,
  • AGE2.IN - mały graf z odpowiedzią pozytywną,
  • AGE3.IN - K_2(30,30,10),
  • AGE4.IN - K_2(50,50,50),
  • AGE5.IN - K_2(100,100,50),
  • AGE6.IN - K_2(75,75,100),
  • AGE7.IN - K_2(50,50,150),
  • AGE8.IN - E(51,61,134,0),
  • AGE9.IN - E(53,59,124,10),
  • AGE10.IN - E(51,59,109,20),
  • AGE11.IN - E(53,64,80,30),
  • AGE12.IN - duży graf dwudzielny, n=180, z odpowiedzią negatywną,
  • AGE13.IN - duży graf dwudzielny, n=250, agenci znajdują się w tej samej części grafu,
  • AGE14.IN - duży graf dwudzielny, n=150, dołączone przejście gwarantujące rozwiązanie,
  • AGE15.IN - duży graf dwudzielny, n=250, z odpowiedzią negatywną.

    Testy 11 i 12 oraz 14 i 15 zostały zgrupowane.