Tomasz Śmigielski Marcin Mucha Marcin Mucha
Treść zadania Opracowanie Program wzorcowy

Mapa gęstości

Dane są:

liczby naturalne ,
F - tabelka wypełniona liczbami ze zbioru ; kolumny i wiersze tabelki są ponumerowane od 1 do n; liczbę znajdującą się w i-tej kolumnie i j-tym wierszu tabelki oznaczamy przez F[i, j].

Jeśli [i, j] i [i', j'] są dwoma miejscami w tabelce F, to odległością między nimi nazywamy liczbę max left( left|i - ...

Należy obliczyć tabelkę W, n times n (do elementów tej tabelki odwołujemy się tak samo, jak do elementów tabelki F) taką, że W[i, j] jest sumą wszystkich liczb z tabelki F leżących w odległości co najwyżej r od [i,j].

Zadanie

Napisz program, który:

wczyta z pliku tekstowego map.in liczby n, r oraz tabelkę F,
obliczy tabelkę W,
zapisze ją do pliku tekstowego map.out.

Wejście

W pierwszym wierszu pliku tekstowego map.in znajdują się dwie dodatnie liczby całkowite oddzielone pojedynczą spacją: n i r, gdzie 0 leq r < n leq 250

W kolejnych n wierszach znajduje się opis tabelki F. Każdy z tych wierszy zawiera n liczb ze zbioru (0,1) , pooddzielanych pojedynczymi odstępami, i-ta liczba zapisana w j+1-szym wierszu to F[i,j].

Wyjście

Plik tekstowy map.out powinien zawierać dokładnie n wierszy, w i-tym wierszu powinny być zapisane kolejno wartości W [1,i] ... W[n,i] pooddzielane pojedynczymi odstępami.

Przykład

Dla pliku wejściowego map.in

poprawną odpowiedzią jest plik wyjściowy map.out

Rozwiązanie

W całym opracowaniu (które jest jednak nieco bardziej teoretyczne od programu) będziemy zakładali, że funkcja F jest określona na całym zbiorze Z times Z , przy czym poza rozważanym kwadratem się zeruje. To pozwoli na nieco swobodniejsze posługiwanie się sumami, a rozważenie przypadków brzegowych w programie jest dość proste (jeśli przypadki brzegowe będą w którymś momencie istotne, to zostanie to odnotowane).

Rozwiązanie optymalne polega na dynamicznym policzeniu sum:

Poszukiwane wartości wyrażają się przez S[i,j] następująco:

W[i,j] = S[i,j] - S[i-r-1,j] - S[i,j-r-1] + S[i-r-1,j-r-1]. Obliczanie sum S[i,j] można wykonać w naturalny sposób w miejscu (tzn. w tablicy F) w czasie O(n²). Wyliczanie każdego W[i,j] odbywa się już potem w czasie stałym. Tak więc cały algorytm ma złożoność O(n²). Program implementujący ten algorytm znajduje się w pliku map.pas.

Inne rozwiązania

Zawsze można W[i,j] obliczyć przy pomocy czterech zagnieżdżonych pętli, czyli po prostu z definicji. Taki algorytm ma złożoność O(n² r²) i nie należy do najszybszych. Jego implementacja znajduje się w pliku map1.pas.

Chwila zastanowienia wystarcza na znalezienie następującej sprytnej formuły:

Innymi słowy: jeśli przesuwamy kwadracik o jedno pole w prawo, to musimy jedną kolumnę odjąć, a drugą dodać. Wystarczy więc ``faktycznie'' policzyć W[i,j] dla j=1, a dalej możemy już w czasie 2r korzystać z powyższej formuły. Jaki jest łączny czas działania takiego algorytmu? Na ``faktyczne obliczenia'' - O(n r²). Na poprawki O(n² r). Łącznie O(n² r). Program implementujący ten algorytm znajduje się w pliku map2.pas.

Oczywiście analogiczną formułę można zastosować, aby policzyć W[i,1] przy pomocy W[i-1,1]. Wtedy musielibyśmy ``faktycznie'' policzyć tylko W[1,1]. Wydaje się to jednak bezcelową komplikacją, skoro i tak program będzie miał złożoność O(n² r). Nie jest to jednak takie proste. Poprawka bowiem nie zawsze wymaga czasu 2r. Czasami dodawana lub odejmowana kolumna jest poza zakresem i wtedy nic nie trzeba robić. Im większe r, tym częściej się to zdarza. W szczególności, jeśli r jest bardzo duże (np. r=n-1), to program ``poprawiający'' w pionie i w poziomie będzie działał w czasie O(n²), a ``poprawiający'' tylko w poziomie w czasie O(n³), z tego prostego powodu, że będzie musiał policzyć wszystkie W[i,1]. W związku z powyższym program ``poprawiający'' i w pionie i w poziomie można uznać za oddzielne rozwiązanie, a jego implementacja znajduje się w pliku map3.pas (choć pesymistycznie nie jest on szybszy od programu ``poprawiającego'' tylko w poziomie).

Testy

Wszystkie testy są losowe (nie bardzo widać, co mogłoby być lepsze). Różnią się rozmiarami, wartością r (z treści opracowania wynika, że generalnie najtrudniejsze testy to takie, dla których rapprox n/2 ) i czasem gęstością jedynek. Testy 1-4 to testy poprawnościowe. W szczególności test 1 sprawdza odporność na r=0, a test 3 na r bardzo duże. Dalej idą coraz trudniejsze testy wydajnościowe. Testy 11-13 to najtrudniejsze testy jakie udało się wymyśleć. Po drodze jest test 8, który może przejść nawet słaby algorytm, o ile przypadek małej liczby jedynek rozważa oddzielnie. Test 10 jest z kolei celowo dobrany pod algorytm poprawiający w obu kierunkach (tak naprawdę na testach 11-13 ten algorytm też radzi sobie nieco lepiej).

Wydaje się, że świetnie napisany i zoptymalizowany algorytm, działający w czasie O(n² r), przejdzie większość testów (być może nawet wszystkie). Oto charakterystyki poszczególnych testów:

map0.in - test z treści zadania;
map1.in - n=5,r=0;
map2.in - n=10, r=5;
map3.in n=20, r=19;
map4.in n=50, r=3;
map5.in n=100, r=50;
map6.in n=150, r=50;
map7.in n=200, r=100;
map8.in n=250, r=10, rzadka macierz;
map9.in n=250, r=50;
map10.in n=250, r=249;
map11.in n=250, r=125;
map12.in n=250, r=125;
map13.in n=250, r=125.

Tomasz Śmigielski	Marcin Mucha	Marcin Mucha
Treść zadania	Opracowanie	Program wzorcowy