https://pl.spoj.com/problems/AL_06_05
Skrócony opis problemu:
Dla macierzy $n$x$n$ należy znaleźć największą sumę dowolnej podmacierzy.
Uwaga: Warto zapoznać się najpierw z wersją jednowymiarową opisaną tutaj. Będę na niej bazował. Problem dla wersji jednowymiarowej to znalezienie podłańcucha o największej sumie.
Rozwiązanie naiwne:
Możemy, tak samo jak w wersji jednowymiarowej, dla każdej czwórki reprezentującej podmacierz obliczyć jej sumę i wypisać największą.
Złożoność: $O(n^6)$, bo takich czwórek jest dokładnie $\left(\frac{n(n+1)}{2}\right)^2 = \frac{n^4+2n^3+n^2}{4}$, a dla każdej z nich zliczamy sumę macierzy, która pesymistycznie ma rozmiar $n^2$.
Algorytm:
int main()
{
int n, a, b, c, d, e, f, s, max = -1000000, x, in[n+1][n+1];
get(n);
for(a = 0; a < n; ++a)
for(b = 0; b < n; ++b)
get(in[a][b]);
for(a = 0; a < n; ++a)
for(b = 0; b < n; ++b)
for(c = 0; c < n; ++c)
for(d = 0; d < n; ++d)
{
s = x = 0;
/* x jest wartownikiem; jeśli po zakończeniu pętli x=0 to znaczy, że mieliśmy macierz z kolumnami np. od 5 do 3 zamiast od 3 do 5 i nie policzyliśmy jej wcale;
bez niego dla takiej macierzy mielibyśmy sumę 0, a dla macierzy ze wszystkimi wartościami ujemnymi nie możemy wpisać zera;
poza tym dzięki temu, że pomijamy te macierze o odwrotnych współrzędnych, to przechodzimy "tylko" (n^4+2n^3+n^2)/4 macierzy, a nie n^4 */
for(e = a; e <= b; ++e)
for(f = c; f <= d; x = ++f)
s += in[e][f];
if(x && s > max) // jeśli przeglądnęliśmy macierz
max = s;
}
print(max);
}
Rozwiązanie sprytniejsze:
Możemy sprawdzić wszystkie podmacierze opierając się na wcześniejszych wynikach. Czyli dla każdej komórki $tab[i][j]$ idziemy na maksa w prawo i w dół, i liczymy kolejne sumy, biorąc sumę wszystkich elementów $s$ zaczynając od w danym rzędzie $k$ od $i$ idąc w prawo, i każdej komórce $tab[i][l]$ przypisujemy wartość $s+tab[i-1][l]$. Dzięki temu będziemy sumę całej podmacierzy od $tab[i][j]$ do $tab[k][l]$ dla każdych wartości $i, j, k, l$.
Macierzy $tab$ nie musimy nawet zerować, gdyż zawsze przypisujemy jej wartość bazując na $s$ i poprzednim wierszu. Tylko pierwszy (o indeksie 0) wiersz i kolumna muszą być wyzerowane. Musimy zerować też $s$.
Jeśli ktoś będzie miał trudności ze zrozumieniem poniższego kodu, można zastąpić $tab[h][w]$ - $tab[i][j][h][w]$. Możemy zrezygnować z tych 2 wymiarów, gdyż jeśli dla jakiejś pary $(i;j)$ obliczymy już wszystkie podmacierze, to nie będziemy potrzebować tych wartości, a zerować macierzy nie trzeba (jak wspomniałem wyżej), więc możemy zastępować je nowymi parami. Można się posunąć jeszcze dalej w optymalizacji złożoności pamięciowej i przechowywać tylko 2 ostatnie wiersze macierzy $tab$ i korzystać z nich na przemian.
Złożoność: $O(n^4)$, gdyż dla każdej z $n^2$ komórek przechodzimy przez prostokąty i wszystkich możliwych szerokościach i długościach, których jest pesymistycznie $n^2$. Warto też zauważyć, że złożoność pamięciowa wynosi tutaj $O(n^2)$, w przeciwieństwie, to $O(1)$ w powyższym algorytmie.
Algorytm:
int main()
{
int t, n, i, j, w, h, s, max = -1000000, in[n][n], tab[n+1][n+1];
get(n);
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
get(in[i][j]);
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
for(h = 1; h <= n - i; ++h) // h to długość podmacierzy
for(s = 0, w = 1; w <= n - j; ++w) // w to szerokość podmacierzy
{
s += in[i+h-1][j+w-1];
tab[h][w] = s+tab[h-1][w];
if(tab[h][w] > max)
max = tab[h][w];
}
print(max);
}
Rozwiązanie najsprytniejsze:
Możemy skorzystać z sum prefiksowych. Obliczamy dla każdej pary $(i;j) \wedge i \le j$ obliczamy dla każdej kolumny sumę elementów od wiersza $i$ do wiersza $j$. Takich par będzie nawiasem mówiąc maksymalnie $\frac{n(n+1)}{2}$.
Np. dla $n=3$ i macierzy:
11 -2 3
-7 0 -6
2 8 3
Będziemy mieli takie sumy:
$$S(0,0) = [11, -2, 3] \\ S(0,1) = [4, -2, -3] \\ S(0,2) = [6, 6, 0] \\ S(1,1) = [-7, 0, -6] \\ S(1,2) = [-5, 8, -3] \\ S(2,2) = [2, 8, 3]$$
Co z nimi teraz? Zauważmy, że jeśli weźmiemy sobie kolumny $k$ i $l$ i zliczymy wszystkie liczby od $k$ do $l$ w $S(i,j)$ to będziemy mieli sumę w prostokącie ograniczonym z góry przez $i$, z dołu przez $j$, z lewej przez $k$ i z prawej przez $l$. No tak, ale to byśmy musieli sprawdzać wszystkie pary $(k;l) \wedge k \le l$ dla każdego z $\frac{n(n+1)}{2}$ par $(i;j)$, ergo znów będziemy mieli złożoność $O(n^4)$. Tak, ale nie musimy sprawdzać każdej pary $(k;l)$. Możemy na każdym wierszu pary $(i;j)$ zapuścić omawiany tutaj algorytm liniowy dla wariantu jednowymiarowego. Czemu? Ano temu, że te wiersze już są sumami po wierszach macierzy wejściowej. Pozostanie nam tylko znaleźć dla każdego optymalne $k$ i $l$, a to możemy zrobić w czasie liniowym. Tak naprawdę, to nawet nas nie obchodzą $k$ i $l$, bo od razu dostaniemy optymalną sumę między nimi.
$$S(0,0) = [11, -2, 3] \\ S(0,1) = [4, -2, -3] \\ S(0,2) = [6, 6, 0] \\ S(1,1) = [-7, 0, -6] \\ S(1,2) = [-5, 8, -3] \\ S(2,2) = [2, 8, 3]$$
Co z nimi teraz? Zauważmy, że jeśli weźmiemy sobie kolumny $k$ i $l$ i zliczymy wszystkie liczby od $k$ do $l$ w $S(i,j)$ to będziemy mieli sumę w prostokącie ograniczonym z góry przez $i$, z dołu przez $j$, z lewej przez $k$ i z prawej przez $l$. No tak, ale to byśmy musieli sprawdzać wszystkie pary $(k;l) \wedge k \le l$ dla każdego z $\frac{n(n+1)}{2}$ par $(i;j)$, ergo znów będziemy mieli złożoność $O(n^4)$. Tak, ale nie musimy sprawdzać każdej pary $(k;l)$. Możemy na każdym wierszu pary $(i;j)$ zapuścić omawiany tutaj algorytm liniowy dla wariantu jednowymiarowego. Czemu? Ano temu, że te wiersze już są sumami po wierszach macierzy wejściowej. Pozostanie nam tylko znaleźć dla każdego optymalne $k$ i $l$, a to możemy zrobić w czasie liniowym. Tak naprawdę, to nawet nas nie obchodzą $k$ i $l$, bo od razu dostaniemy optymalną sumę między nimi.
Złożoność: $O(n^3)$, gdyż tworzymy $\frac{n(n+1)}{2}$ wierszy liniowo (każdy element wiersza w czasie stałym za pomocą sum prefiksowych, czyli bazując na wartościach poprzednich elementów), a następnie dla każdego wiersza również liniowo znajdujemy największą sumę w nim. Jako że każdy wiersz jest reprezentantem ciągu wierszy macierzy z wejścia, to przeszukamy wszystkie możliwe podmacierze.
Złożoność pamięciowa wzrosła tu nam do $O(n^3)$.
Ostateczny algorytm:
int main()
{
int n, i, j, k, s, s1, s2 = -1000000, tab[n+1][n+1][n+1], in[n+1][n+1];
get(n);
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
get(in[i][j]);
for(i = 1; i <= n; ++i) // dla każdego i
{
for(j = i; j <= n; ++j) // i każdego j
for(k = 1; k <= n; ++k)
tab[i][j][k] = tab[i][j-1][k]+in[i][k]; // tworzymy sumę bazując na poprzednim wierszu
for(j = i-1; j > 0; --j) // musimy uwzględnić j również w poprzednich sumach
for(k = 1; k <= n; ++k)
tab[j][i][k] = tab[j][i-1][k]+in[i][k];
}
for(i = 1; i <= n; ++i) // dla każdej pary (i;j)
for(j = i; j <= n; ++j)
{
s = 0; s1 = -1000000; // szukamy w wierszu S(i,j) największej sumy
for(k = 1; k <= n; ++k)
{
if(s > 0)
s += tab[i][j][k];
else
s = tab[i][j][k];
if(s > s1)
s1 = s;
}
if(s1 > s2)
s2 = s1;
}
print(s2);
}
Optymalizacja:
Możemy zmniejszyć złożoność pamięciową do kwadratowej oraz przyspieszyć program czy zachowaniu takiej samej złożoności czasowej, lepiej wykorzystując sumy prefiksowe.
Mianowicie, jeśli mamy sobie wiersz: $S(4,5)$ to wystarczy, że obliczymy tylko (dla $n=6$) wiersze: $S(0,0), S(0,1), S(0,2), S(0,3), S(0,4), S(0,5)$. Wiersz $S(4,5)$ otrzymamy odejmując $S(0,3)$ od $S(0,5)$. Musimy więc obliczyć jedynie $n$ wierszy $S(0;i)$ w czasie liniowym. Pierwszy etap zajmie nam zatem jedynie $O(n^2)$ czasu zamiast $O(n^3)$. Zaoszczędzimy również na pamięci, gdyż ilość wierszy zmniejszyła nam się z kwadratowej na liniową, a musieliśmy wszystkie pamiętać.
W głównej części programu korzystamy po prostu zamiast $tab[i][j][k]$ z $tab[j][k]-tab[i-1][k]$ i tyle.
Możemy też optymalizować przypadki szczególne, jak macierz złożona z samych liczb ujemnych, z samych liczb nieujemnych lub z jedną liczbą nieujemną. Złożoność dla każdego z tych przypadków to $O(n^2)$, bo musimy tylko wczytać dane. Nie będę jednak ich uwzględniał w poniższym kodzie.
Ostateczny, ulepszony algorytm:
int main()
{
int n, i, j, k, s, s1, s2 = -1000000, tab[n+1][n+1];
get(n);
for(i = 1; i <= n; ++i)
for(j = 1; j <= n; ++j)
{
get(k); // możemy na bieżąco obliczać sumy prefiksowe; nie musimy zapamiętywać macierzy z wejścia, gdyż nie będzie nam potem już do niczego potrzebna
tab[i][j] = k+tab[i-1][j];
}
for(i = 1; i <= n; ++i)
for(j = i; j <= n; ++j)
{
s = 0; s1 = -1000000;
for(k = 1; k <= n; ++k)
{
if(s > 0)
s += tab[j][k]-tab[i-1][k];
else
s = tab[j][k]-tab[i-1][k];
if(s > s1)
s1 = s;
}
if(s1 > s2)
s2 = s1;
}
print(s2);
}
Brak komentarzy:
Prześlij komentarz