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 \le 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\le 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 \le 1500\):

Żeby przyśpieszyć poprzednie rozwiązanie, można obliczyć tablicę \(max\_len\_to\_left[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ę \(max\_len\_horizontal\_left[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 \(max\_len\_to\_left[x][y]\) dla \(1 \le x \le c, 1 \le y \le 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 \le 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.