Tomasz ŚmigielskiMarcin MuchaMarcin Mucha
Treść zadaniaOpracowanieProgram wzorcowy


Mapa gęstości


Dane są:

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:

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
5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
poprawną odpowiedzią jest plik wyjściowy map.out
3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2

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:

S[i,j] = sum_(1 le x...

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(n2). 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(n2). 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(n2 r2) 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:

W[i,j]=W[i,j-1]+sum_...
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 r2). Na poprawki O(n2 r). Łącznie O(n2 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(n2 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(n2), a ``poprawiający'' tylko w poziomie w czasie O(n3), 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(n2 r), przejdzie większość testów (być może nawet wszystkie). Oto charakterystyki poszczególnych testów: