Omówienie zadania Układ scalony (I etap XXVII OI)

Mamy \(n\cdot m\) punktów ułożonych w \(n\) rzędach i \(m\) kolumnach. Należy połączyć je używając \(nm-1\) krawędzi poziomych lub pionowych, tak by między każdymi dwoma punktami istniała ścieżka i żeby najdłuższa ścieżka miała dokładnie \(k\) krawędzi.

Używając terminologii grafowej, mamy skonstruować drzewo rozpinające, którego średnica wynosi \(k\).

Jaki jest zakres sensownych wartości średnicy?

Ustalmy wielkość kratki \(n\times m\) i zastanówmy się jakie są minimalne i maksymalne wartości \(k\), dla których istnieje drzewo.

Na pewno musi zachodzić \(k \leq nm-1\), bo na dłuższą średnicę po prostu zabraknie nam krawędzi. To, że istnieje drzewo dla \(k=nm-1\), pokazuje prosty przykład zygzaka:

*--*--*--*--*
|
*--*--*--*--*
            |
*--*--*--*--*

Na pewno musi zachodzić \(k \ge n+m-2\), gdyż drzewo musi zawierać jakąś ścieżkę pomiędzy dwoma naprzeciwległymi rogami. Okazuje się, że jeżeli choć jeden wymiar \(n\) lub \(m\) jest nieparzysty, to wtedy istnieje drzewo spełniające \(k=n+m-2\):

*--*--*--*--*
      |
*--*--*--*--*
      |
*--*--*--*--*
      |
*--*--*--*--*

Jednak gdy oba wymiary są parzyste, to \(k=n+m-2\) nie będzie wystarczać, co pokazuje argument z parzystością. Załóżmy wbrew tezie, że istnieje drzewo realizujące \(k=n+m-2\) i rozważmy drzewo indukowane przez rogi kratki. Narysujmy ścieżki pomiędzy przeciwległymi rogami, na rysunku są to ścieżki \(a-c-e\) oraz \(b-c-d\), przy czym \(c\) jest kawałkiem (być może pustym), w którym te ścieżki się pokrywają:

*-----*-----*
  a   |   b
      |c
  d   |   e
*-----*-----*

Obie z nich muszą być średnicami, zatem mamy \(a+c+e=n+m-2=b+c+d\). Ale skoro \(a+c+e\) jest średnicą, to \(a+c+d \leq a+c+e\), zatem \(d \leq e\). Ale symetrycznie \(b+c+d\) jest średnicą, więc \(b+c+e \leq b+c+d\), zatem \(e \leq d\). Z tego wynika, że \(d=e\).

Symetryczny argument pokazuje, że \(a=b\). Ale odległość pomiędzy każdą parą rogów na jednym boku jest nieparzysta, więc ścieżka \(a-b\) ma nieparzystą długość, więc nie może być podzielone na dwa kawałki \(a\) i \(b\) o równej długości – sprzeczność.

Jednak drzewo spełniające \(k=n+m-1\) będzie już istniało. Wystarczy zastosować podobną konstrukcję, co w przypadku, gdy któryś wymiar był nieparzysty:

*--*--*--*
      |
*--*--*--*
      |
*--*--*--*
      |
*--*--*--*

Co z wartościami pomiędzy?

Okazuje się, że każda wartość średnicy pomiędzy minimalną a maksymalną jest możliwa do zrealizowania. Konstrukcja może być następująca: zaczynamy od rozwiązania dla minimalnego \(k\) i w kolejnych krokach zwiększamy średnicę o 1, stopniowo wydłużając zygzak najpierw po lewej, a potem po prawej stronie, aż uzyskamy maksymalne \(k\):

Krok 0:          Krok 1:          Krok 2:          Krok 6:          Krok 11:         Krok 12:

*--*--*--*--*    *--*--*--*--*    *--*--*--*--*    *--*--*--*--*    *--*--*  *--*    *--*--*  *--*
      |          |     |          |     |          |     |          |     |  |  |    |     |  |  |
*--*--*--*--*    *  *--*--*--*    *  *--*--*--*    *  *  *--*--*    *  *  *  *  *    *  *  *  *  *
      |                |          |     |          |  |  |          |  |  |     |    |  |  |  |  |
*--*--*--*--*    *--*--*--*--*    *  *--*--*--*    *  *  *--*--*    *  *  *--*  *    *  *  *  *  *
      |                |                |          |  |  |          |  |  |     |    |  |  |     |
*--*--*--*--*    *--*--*--*--*    *--*--*--*--*    *--*  *--*--*    *--*  *--*--*    *--*  *--*--*

Warto zwrócić uwagę na to, że w przypadku obu wymiarów parzystych zygzaka należy zacząć robić najpierw w ,,większej połówce”, bo inaczej pierwszy krok nie zwiększy nam średnicy.

Pełny algorytm

Na początek sprawdzamy, czy \(k\) zawiera się między minimalną a maksymalną wartością. Jeśli nie, to odpowiadamy ,,nie”. W przeciwnym wypadku zaczynamy od konstrukcji minimalnej, a następnie robimy tyle kroków, ile potrzeba dla szukanego \(k\) (każdy krok robimy w czasie stałym). Złożoność czasowa to \(O(nm)\).

Podzadanie 1

Algorytmy wykładnicze będą zbyt wolne nawet dla małych kratek. Ale w podzadaniu 1 mamy jedynie \(6\cdot6=36\) możliwych kratek, a uwzględniając sensowne wartości \(k\), jedynie 261 możliwych testów. Można zatem wygenerować odpowiedzi dla nich wszystkich i wkleić je do kodu.

Podzadanie 2

Warunek \(n\leq 3\) daje możliwość łatwiejszego rozrysowania rozwiązań.

Podzadanie 3

Z powyższej analizy wynika, że przypadek obu boków parzystych jest istotnie trudniejszy. Drugi potencjalny błąd można popełnić, jeśli się zapomni odwrócić współrzędne dla boków o różnej parzystości. Obie te sytuacje nie występują w podzadaniu 3 (liczba punktów jest nieparzysta).