Runda 1: Puzzle (rozwiązanie)

Autor zadania: Marcin Dublański

Przede wszystkim zauważmy, że dla każdej poprawnej układanki dane zadania wystarczają do jednoznacznego jej ułożenia. Wynika to z poniższej konstrukcji. Puzzle będziemy układać rzędami, od górnego do dolnego, a w obrębie rzędu kolumnami.

Załóżmy, że mamy ułożone już całe i-1 rzędów, a w rzędzie i-tym j-1 kolumn. Chcemy zatem dowiedzieć się, który kawałek postawić w i-tym rzędzie i j-tej kolumnie, czyli na pozycji (i,j). Ułożyliśmy poprawnie już dwóch jego sąsiadów: tych na pozycji (i,j-1) oraz (i-1,j). Istnieją tylko dwa kawałki, które mogą mieć te oba kawałki za sąsiadów. Jeden z nich to kawałek o pozycji (i-1,j-1), którego już z założenia położyliśmy, drugi z nich to szukany kawałek (i,j).

Widać więc, że wystarczy pamiętać numery wszystkich kawałków jeszcze niewykorzystanych i dla każdego z nich sprawdzić, czy jest on jednocześnie sąsiadem kawałka (i,j-1) oraz (i-1,j). W pseudokodzie wygląda to mniej więcej tak:

S = zbiór jeszcze nieułożonych kawałków
for i=1 to n do
    for j=1 to m do
        for e <- S
            if(e jest sąsiadem (i,j-1) oraz (i-1,j))
            U[i][j] = e;
            usuń e z S;
        endfor
    endfor
endfor

Widać, że czas działania jest kwadratowy ze względu na ilość kawałków układanki. Ze względu na niewielkie limity (n*m <= 1000) algorytm ten wystarczał do zdobycia 10 punktów. Mając go nietrudno jednak wymyślić algorytm działający liniowo, co zostawiam jako ćwiczenie.