Wyszła mi mini powieść, ale akurat Haft to takie zadanie, które trudno krótko opisać 
Jeżeli coś jest niejasne piszcie.
Optymalna strategia odwzorowania haftu jest prosta, z każdej komórki staramy się wykonać operację wyszywania o jak największym r. Wartość r dla każdego pola wyznaczamy analizując haft Małgosi. Sprawdzamy ile gwiazdek odchodzi od danej komórki w każdym z czterech kierunków (góra, dół, lewo, prawo) i wybieramy najmniejszą z tych wartości. Jak już znamy wartość r dla każdej komórki to wyszywamy nasz haft i po zakończeniu sprawdzamy czy pokrywa się z haftem Małgosi.
Dojście do takiego rozwiązania na pewno nie jest trudne, większym problemem jest odpowiednia implementacja.
Rozwiązanie naiwne to oczywiście zakodowanie powyższej strategii, czyli 3 zagnieżdżone pętle. Dwie zewnętrzne wybierają komórkę, dla której wyznaczamy r. Trzecia najbardziej wewnętrzna pętla wyznacza r, oddalając się coraz bardziej od komórki i sprawdzając czy w każdym z czterech kierunków dalej występują gwiazdki. Jak już wyznaczymy r dla komórki to haftujemy. Złożoność algorytmu to O(n^3).
Uwaga! Zakładam, że wszystkie tablice, które tworzę są wyzerowane przed ich użyciem.
Można to jednak rozwiązać szybciej. Stwórzmy sobie 4 tablice U, D, L, R o rozmiarze odpowiadającym rozmiarowi tkaniny. Każda z tych tablic przechowuje informacje ile gwiazdek odchodzi od danej komórki w jednym z 4 kierunków. Kluczowe jest to żeby zauważyć, że te tablice możemy wyznaczyć w czasie O(n^2), a nie O(n^3).
Pokaże to na przykładzie tablicy L, która przechowuje informacje ile gwiazdek odchodzi od każdej komórki w lewą stronę. Przechodzimy haft Małgosi (tablicę M) wiersz po wierszu. Załóżmy, że jesteśmy w wierszu y. Jeżeli haft Małgosi w pierwszej kolumnie wiersza y ma gwiazdkę (M[y][0] == *) to w komórce L[y][0] zapisujemy wartość 1, w przeciwnym wypadku wartość 0. Teraz przechodzimy wiersz y od drugiej kolumny aż do samego końca. Załóżmy, że jesteśmy w kolumnie x. Jeżeli haft Małgosi w kolumnie x wiersza y ma kropkę (M[y][x] == .) to do komórki L[y][x] zapisujemy wartość 0. Jeżeli jednak haft Małgosi w kolumnie x wiersza y ma gwiazdkę (M[y][x] == *) to zapisujemy do kolumny L[y][x] wartość 1 + liczba gwiazdek, które stoją w wierszu y przed kolumną x. Skąd mamy wziąć tę liczbę? Otóż policzyliśmy ją jeden obrót pętli wcześniej i zapisaliśmy w polu L[y][x - 1]! Podsumowując pseudokod wyznaczający tablicę L prezentuje się tak:
for y = 0 to m - 1 do
if M[y][0] == * then
L[y][0] = 1
else
L[y][0] = 0
for x = 1 to n - 1 do
if M[y][x] == * then
L[y][x] = L[y][x - 1] + 1
else
L[y][x] = 0
Analogicznie wyznaczamy tablice U, D i R. Po ich wyznaczeniu wartość r dla każdej komórki możemy policzyć w czasie stałym r = min(U[y][x] - 1, D[y][x] - 1, L[y][x] - 1, R[y][x] - 1). Jeżeli wartość r wyszła < 1 to oznacza, że z tej komórki nie możemy nic wyszyć.
Wiemy już jak wyznaczyć wszystkie operacje w złożoności O(n^2). Teraz musimy je wykonać żeby sprawdzić czy uzyskaliśmy taki sam haft jak Małgosia. Jak wynika z opisu rozwiązania naiwnego operacja haftowania też będzie miała złożoność O(n^3). Tutaj też dążymy do tego żeby uzyskać złożoność O(n^2). W tym celu wykorzystamy pewien trick.
Wyobraźcie sobie takie zadanie. Macie prostą na której trzeba narysować bardzo dużą liczbę odcinków, które mogą się nakładać na siebie. Żeby nie odbiegać za bardzo od naszego zadania, niech to będzie wiersz tabeli, w którym macie zapisywać odcinki gwiazdek. Rozwiązanie naiwne to oczywiście zapisywanie tych gwiazdek dla każdego wczytanego odcinka. Sprytniejsze rozwiązanie wygląda tak. Dla każdego wczytanego odcinka zwiększamy wartość w komórce, w której się on zaczyna o 1, zaś w pierwszej komórce za końcem odcinka zmniejszamy wartość o 1. Po wczytaniu wszystkich odcinków liczymy sumy prefiksowe dla tego wiersza. Jak łatwo zauważyć po policzeniu sum prefiksowych każda komórka będzie trzymała liczbę odcinków, które ją pokrywają.
Przykład:
Mamy nanieść 2 odcinki 1-3 i 2-4 w tablicy 6-elementowej.
0 1 2 3 4 5 <- Indeksy tablicy
0 0 0 0 0 0 <- Wartości początkowe
0 1 0 0 -1 0 <- Po dodaniu odcinka 1-3
0 1 1 0 -1 -1 <- Po dodaniu odcinka 2-4
0 1 2 2 1 0 <- Po policzeniu sum prefiksowych
Teraz wystarczy, że przejdziemy liniowo tę tablicę i wypiszemy gwiazdkę tam gdzie wartość w komórce jest dodatnia.
Jak to wykorzystać do haftowania? Bardzo prosto, każda operacja to tak naprawdę narysowanie dwóch odcinków, jednego poziomego i jednego pionowego. Utwórzmy zatem kolejne 2 tablice H i V, o rozmiarze o 1 większym w poziomie i pionie od rozmiaru tkaniny. W tablicy H będziemy oznaczać poziome odcinki gwiazdek do narysowania, zaś w tablicy V pionowe. Załóżmy, że mam do wykonania operację x y r czyli z komórki x, y powinienem narysować pionowy odcinek od pola x, y - r do pola x, y + r oraz poziomy odcinek z pola x - r, y do pola x + r, y. Korzystając z tego co napisałem powyżej wykonam poniższe operacje:
H[y][x - r] += 1
H[y][x + r + 1] -= 1
V[y - r][x] += 1
V[y + r + 1][x] -= 1
Po przejściu wszystkich operacji liczę sumy prefiksowe dla każdego wiersza w tablicy H i dla każdej kolumny w tablicy V i na ich podstawie zapisuję gwiazdki. Całość ma złożoność O(n^2).
W ten sposób można uzyskać rozwiązanie o złożoności O(n^2) zamiast O(n^3). Moje rozwiązanie wzorcowe wykonuje się w 0,2s dla najbardziej złośliwego testu. Zastanawiałem się czy nie zmniejszyć limitu czasu do 0,5s, ale uznałem, że jeżeli komuś uda się wcisnąć O(n^3) w 1s to też będzie świadczyło o bardzo dobrych umiejętnościach programistycznych 
