Omówienie zadania Budowa Lotniska (I etap XXXI OI)

Rozwiązanie $m = 1$ :

W tym podzadaniu mamy zaplanować tylko jeden pas startowy. Ten pas będzie albo zorientowany poziomo, albo pionowo, więc dla tych dwóch orientacji oddzielnie obliczymy wynik i wybierzemy ten większy. Spróbujmy więc znaleźć najdłuższy poziomy pas - dla pionowego można postąpić podobnie. Aby wyznaczyć wynik, dla każdego wiersza wejścia sprawdzamy, jaki jest najdłuższy spójny ciąg składający się z kropek. Najdłuższy pas znajdzie się po lewej stronie pierwszego znaku X w danym wierszu, albo po prawej stronie ostatniego znaku X w wierszu, albo między dwoma kolejnymi znakami X. Jeśli nie ma znaku X to pas zajmuje cały wiersz.

Trzeba jeszcze pamiętać o przypadku brzegowym - jeżeli nie ma żadnej kropki, to wynik wynosi $0$ . Rozwiązanie działa w złożoności $O (n^{2})$ , czyli liniowo od wielkości wejścia.

Rozwiązanie $m = 2$ :

W rozwiązaniu wzorcowym występują dwa przypadki.

Szukane pasy są równoległe:

Do szukania dwóch równoległych nieprzecinających się pasów startowych możemy ulepszyć rozwiązanie dla $m = 1$ .

Zamiast szukać najdłuższego pasa, będziemy szukać najdłuższego oraz drugiego najdłuższego pasa. Można utrzymywać oba w kolejnych krokach algorytmu dla $m = 1$ - gdy znajdujemy nowego kandydata, porównujemy z dotychczas najdłuższym znalezionym pasem. Jeżeli jest dłuższy, to znaleźliśmy właśnie nowy najdłuższy pas startowy, a jako drugi najdłuższy przypisujemy poprzedni najdłuższy. Jeżeli nie jest dłuższy, to wystarczy go porównać z drugim najdłuższym i zaktualizować drugi najdłuższy, jeżeli okazał się krótszy.

Być może najdłuższy znaleziony pas jest bardzo długi - dłuższy niż dwukrotność długości drugiego najdłuższego pasa. Wtedy opłaca się rozbić najdłuższy pas na dwa. W przeciwnym przypadku wynikiem będzie długość drugiego najdłuższego pasa.

Szukane pasy są prostopadłe, $n \leq 300$ :

Jeżeli szukana para najdłuższych pasów jest prostopadła, to na pewno zachodzi jeden z czterech przypadków:

poziomy pas znajduje się w całości na lewo od pionowego (tzn. jeżeli $x$ to numer kolumny, w której znajduje się pionowy pas, to poziomy pas musi w całości znajdować się w pierwszych $x - 1$ kolumnach),
albo poziomy pas znajduje się w całości na prawo od pionowego,
albo pionowy pas znajduje się w całości nad poziomym,
albo pionowy pas znajduje się w całości poniżej poziomego.

Wystarczy dla każdego przypadku oddzielnie obliczyć wynik. Można to osiągnąć ładnym trickiem implementacyjnym:

liczymy wynik przy założeniu, że poziomy pas znajduje się w całości na lewo od pionowego,
obracamy płaszczyznę o 90 stopni, na przykład korzystając z przekształcenia $(x, y) \to (y, n - 1 - x)$ dla $0 \leq x, y < n$ ,
powtarzamy powyższe kroki łącznie cztery razy i wypisujemy największy uzyskany wynik.

Żeby obliczyć wynik przy założeniu, że poziomy pas znajduje się w całości na lewo od pionowego, można przeiterować się po każdej kolumnie, w której miałby być pionowy pas, i postąpić analogicznie do algorytmu dla $m = 1$ aby wyznaczyć najdłuższy poziomy pas w konkretnym obszarze lotniska oraz najdłuższy pionowy w określonej kolumnie. Daje to rozwiązanie w złożoności $O (n^{3})$ .

Szukane pasy są prostopadłe, $n \leq 1500$ :

Żeby przyśpieszyć poprzednie rozwiązanie, można obliczyć tablicę $m a x_l e n_t o_l e f t [x] [y]$ - jaka jest największa długość poziomego pasa, która mieści się na lotnisku i kończy się dokładnie na polu $(x, y)$ (jeżeli nie da się żadnego pasa tak zaplanować, to tablica będzie przechowywać wartość $0$ ). Jeżeli pole $(x, y)$ jest wolne, to najdłuższy poziomy pas kończący się na polu $(x, y)$ jest albo najdłuższym poziomym pasem kończącym się na polu $(x - 1, y)$ przedłużonym o jedno pole, albo jest pasem długości $1$ . Tym sposobem tablicę można obliczyć w czasie $O (n^{2})$ .

Korzystając z tej tablicy, można w czasie $O (n^{2})$ wyznaczyć tablicę $m a x_l e n_h o r i z o n t a l_l e f t [c]$ - jaka jest największa długość poziomego pasa, który w całości mieści się w prostokącie o przeciwległych rogach $(1, 1)$ i $(c, n)$ . Jest to po prostu największa z wartości $m a x_l e n_t o_l e f t [x] [y]$ dla $1 \leq x \leq c, 1 \leq y \leq n$ .

Gdy rozpatrujemy pionowy pas w $x$ -tej kolumnie, możemy skorzystać z powyższej tablicy aby w czasie $O (1)$ znaleźć najdłuższy poziomy pas znajdujący się na lewo od tego pionowego pasa. Daje to rozwiązanie w sumarycznej złożoności $O (n^{2})$ .

Szukane pasy są prostopadłe, $n \leq 1500$ , rozwiązanie alternatywne:

Zacznijmy od oddzielnego znalezienia najdłuższego poziomego pasa oraz najdłuższego pionowego pasa. Jeżeli się nie przecinają na lotnisku, to poznaliśmy wynik (tzn. długość krótszego z nich). Jeżeli się przecinają, to okazuje się, że wystarczy skrócić te dwa pasy o minimalną liczbę pól tak, aby się już nie przecinały.

Dlaczego nie istnieje lepsza para pasów? Otóż jeżeli optymalne rozwiązanie składa się z dwóch pasów długości $k$ o różnych orientacjach i nie da się umieścić dwóch pasów długości $k$ w jednej orientacji, to jest tylko jeden pas pionowy długości co najmniej $k$ i tylko jeden pas poziomy długości co najmniej $k$ . Muszą to w szczególności być najdłuższe pasy o danych orientacjach.