Omówienie zadania Powódź (I etap XXV OI)

Wstęp

W zadaniu mamy daną planszę o podzieloną \(n \times m\) kwadratowych pól o jednakowym rozmiarze. Pomiędzy każdą parą sąsiadujących ze sobą pól istnieje bariera o wysokości od \(1\) do \(H\) milimetrów. Planszę nawiedzi niedługo powódź i wiemy, że dla każdej pary sąsiednich pól pomiędzy którymi wybudowano tamę o wysokości \(h\) milimetrów, poziomy wody znajdujące się na nich są równe lub oba nie większe niż \(h\). Chcemy dowiedzieć się ile jest różnych możliwych scenariuszy powodzi.

Najprostsze rozwiązanie

Zastanówmy się najpierw w jaki sposób skonstruować najprostsze rozwiązanie. W tego typu zadaniach kombinatorycznych sprowadza się ono do wygenerowania każdego możliwego przypadku oraz sprawdzenia, czy spełnia on założenia. Wszystkich możliwych rozmieszczeń wody jest \((H+1)^{mn}\), ponieważ mamy \(mn\) pól do dyspozycji oraz na każde z nich możemy wstawić \(H+1\) wartości. Następnie, warunek z treści zadania jesteśmy w stanie sprawdzić w czasie \(O(mn)\). Skonstruowaliśmy więc rozwiązanie, które osiąga złożoność czasową \(O(mn \cdot (H+1)^{mn})\).

Nieco uproszczony problem

Spróbujmy rozważyć najpierw prostszy problem, który pojawił się z resztą w 4. podzadaniu. Mianowicie, założymy, że nasze pole jest w istocie ciągiem, w którym mamy zależności jedynie pomiędzy kolejnymi elementami. Często prościej myśli się o takim przypadku, gdzie mamy tylko jeden wymiar. Spójrzmy więc na dowolną barykadę i oznaczmy jej wysokość przez \(h\). Nietrudno jest dostrzec, że gdy po którejś stronie barykady poziom wody przekroczy \(h\), to możemy oba pola traktować jako jedno, ponieważ ich wartość jest taka sama.

Spróbujmy wysunąć dalsze wnioski z tego faktu. Widzimy, że takie połączone pola stanowią swego rodzaju przedział w naszym ciągu. Gdybyśmy założyli, że poziom wody w każdym z pól jest jednakowy i równy \(x\), to zauważymy, że niektóre bariery zostały już "przekroczone", a te, których wysokość jest nie mniejsza niż \(x\), dzielą nam ciąg właśnie na przedziały. Zastanówmy się teraz, w jaki sposób możemy odzyskać wynik, w sytuacji, gdy maksymalny poziom wody to \(x\)? Zauważmy, możemy policzyć go z osobna dla każdej ze spójnych, a następnie wziąć iloczyn tych wszystkich wyników.

Jak możemy z tego skorzystać?

Co by się stało, gdybyśmy zwiększyli \(x\) o \(1\)? Wtedy potencjalnie jakieś bariery zostałyby zalane, a przedziały, które one oddzielały, złączyłyby się. W jaki sposób zmienia się wtedy wynik dla poszczególnych przedziałów?

• Gdy dany przedział nie ulega modyfikacji, jego wynik zwiększa się jedynie o \(1\), gdyż doliczamy przypadek, gdy wszystkie jego elementy się równe \(x+1\).
• Gdy zaś dany przedział ulega modyfikacji, czyli powstaje nowy przedział będący złączeniem innych jego wynik jest iloczynem wyników przedziałów składowych plus \(1\), gdyż znowu doliczamy przypadek, gdy wszystkie elementy są równe \(x+1\).

A co gdy \(x\) jest równe \(H+1\)? Wtedy pozostał nam już tylko jeden przedział, a wynik dla niego, to wynik dla całego zadania powiększony o \(1\) (musimy odliczyć przypadek, gdy wszystkie pola mają wartość \(x+1\)).

Powrót do pierwotnego wyzwania

W ogólnym rozrachunku mamy jednak do czynienia nie z ciągiem, lecz z planszą. Jednak czy zmienia to wiele w kontekście naszego rozwiązania? Okazuje się, że bardzo niewiele, ponieważ zamiast zwykłych przedziałów, występują tutaj po prostu spójne obszary pól.

W jaki sposób wygodnie oraz z niedużym kosztem możemy trzymać w pamięci nasze obszary? Możemy wykorzystać do tego technikę Find and Union. Teraz, przy każdym usunięciu bariery, będziemy łączyć spójne pól znajdujących się po obydwu jej stronach i ustawiać wynik dla nowopowstałej spójnej. Na koniec możemy jeszcze zauważyć, że nie musimy sprawdzać każdej wartości x z przedziału od \(1\) do \(H\). Możemy zaś ograniczyć się jedynie do sprawdzania tylko tych wartości \(x\), dla której istnieje bariera o tej wysokości. Osiągnęliśmy więc złożoność czasową \(O(mn \log (mn))\) oraz pamięciową \(O(mn)\).