Prostokąty i obszary

W dzisiejszym prawie-już-wakacyjnym odcinku rozwiążemy dość oryginalne, i co nawet lepsze nieszczególnie trudnie w implementacji, zadanie C z 2 rundy Yandex.Algorithm 2014. Dostajemy w nim (znów! cóż za zbieg okoliczności) planszę, której pola są pomalowane na czarno i biało. Interesuje nas zliczanie spójnych jednokolorowych obszarów, jednak żeby było ciekawiej, nie na oryginalnej planszy, lecz na jej podanych wycinkach. Nie wydaje się to szczególnie łatwe biorąc pod uwagę, że plansza może mieć rozmiar 2000\times 2000, a wycinków, które należy rozważyć, może być nawet 500000, jednak autor postanowił trochę ułatwić nam życie, i jeśli odpowiedź przekracza 2, prosi o wypisanie 0 (niezależnie od tego, czy odpowiedź to 3, 7, czy 65536). Ale jak z tego skorzystać?

Oryginalną treść zadania można zobaczyć tutaj. Co dość dziwne, nikomu nie udało się go rozwiązać w trakcie zawodów!

Zacznijmy może od trochę (ale tylko trochę) bardziej formalnego zdefiniowania problemu. Interesują nas wycinki podanej planszy n\times m. Taki wycinek jest prostokątem o bokach równoległych do boków oryginalnej planszy, to jest [r_1,r_2]\times [c_1,c_2]. Mając dany taki wycinek, interesuje nas liczba spójnych jednokolorowych obszarów w środku. Mówimy, że dwa pola są w tym samym obszarze, jeśli można przejść z jednego do drugiego poruszając się tylko po polach tego samego koloru, no i przechodząc tylko między polami, które mają wspólną krawędź (no i.. nie uciekając poza podany wycinek). Jeśli mielibyśmy odpowiedzieć tylko na jedno takie pytanie, moglibyśmy na przykład skonstruować odpowiedni graf nieskierowany i policzyć jego spójne składowe. Niestety, pytań jest wiele, graf może być całkiem spory, a limit czasu to tylko 3 sekundy. Co zrobić?

Konieczne wydaje się skorzystanie z tego, że jeśli odpowiedź przekracza 2, nie interesuje nas wyznaczenie jej dokładnej wartości. Może dałoby się skonstruować jakąś szybką metodę, która pozwoli nam na stwierdzenie, że odpowiedź jest bardzo duża, i w związku możemy od razu wypisać 0 darując sobie dalsze rozważania?

Zastanówmy się, jak mają się spójne jednokolorowe obszary zawarte w naszym wycinku do spójnych jednokolorowych obszarów na całej planszy. Wygodnie jest patrzeć na to od drugiej strony, to jest wziąć jakiś oryginalny spójny jednokolorowy obszar i wyobrazić sobie, że przycinamy go do naszego wycinka. Takie przycinanie być może niczego nie zmienia, a być może wygeneruje wiele nowych spójnych jednokolorowych obszarów.

prostokaty

Naturalne jest podzielenie wszystkich spójnych jednokolorowych obszarów, które są choćby częściowo widoczne w naszym wycinku, na dwa typy. Brzegiem będziemy nazywać te pola wycinka, które mają mniej niż 4 sąsiadów również znajdujących się w wycinku, a ścisłym wnętrzem te z jego pól, które nie leżą na brzegu. Teraz dwa typy to:

  1. obszary, których choćby jedno pole leży na brzegu wycinka,
  2. obszary, które są całkowicie zawarte w ścisłym wnętrzu wycinka.

Nie ma innej możliwości: jeśli jakiś obszar zawiera pola leżące zarówno wewnątrz, jak i na zewnątrz obszaru, to zawiera choć jedno pole leżące na jego brzegu.

Może dałoby się szybko policzyć obszary któregoś typu? Najbardziej obiecujący wydaje się tutaj ten drugi, gdyż tak naprawdę wystarczyłoby dla każdego obszaru zapamiętać najmniejszy obejmujący go prostokąt, a następnie policzyć, ile z zapamiętanych prostokątów jest zawartych w [r_1+1,r_2-1]\times [c_1+1,c_2-1]. To zaś pewnie dałoby się… jakoś tam zrobić. Ale nie wiadomo czy w czasie stałym, więc może trzeba inaczej.

Wyobraźmy sobie sytuację na brzegu. Dokładniej, wyobraźmy sobie, że obchodzimy brzeg zgodnie z ruchem wskazówek zegara. Czy umielibyśmy jakoś sprytnie wygenerować wszystkie obszary, których pola odwiedzamy? Na pewno istotne są tylko te momenty, w których zmienia się kolor aktualnego pola, nazwijmy to przeskokiem. Teraz okazuje się, że liczba przeskoków daje nam sporą wiedzę na temat różnych obszarów.

Lemat. Jeśli na brzegu są przynajmniej 4 przeskoki, to w naszym wycinku są przynajmniej 3 różne obszary.

Dowód. Zacznijmy może od tego, że liczba przeskoków jest zawsze parzysta. Jest tak dlatego, że każdy przeskok zmienia aktualny kolor, no i prędzej lub później wracamy do punktu startu. Lemat mówi więc tyle, że jedyne „ciekawe” liczby przeskoków to 0 i 2. Czemu? Wyobraźmy sobie 4 kolejne przeskoki. Bez istotnej straty ogólności sytuacja wygląda tak jak poniżej.

prostokaty1

Teraz mamy dwie możliwości. Obszary oznaczone jako A i C mogą faktycznie być dwoma różnymi obszarami. Obszar oznaczony jako B ma inny kolor, więc daje nam to w sumie przynajmniej 3 różne obszary. Jeśli A i C to tak naprawdę ten sam obszar, oddziela on wszystkie pola obszaru B od pozostałej (niepustej) części wycinka, co znów daje nam przynajmniej 3 różne obszary.

Otrzymaliśmy więc dość prosty test, który czasami pozwala na szybkie wykrycie, że należy wypisać 0. No, prosty jak prosty: czy na pewno możemy szybko policzyć przeskoki na brzegu? Tak! Wystarczy bowiem dla każdego pola zapamiętać najbliższy przeskok (czyli pole innego koloru) na prawo i w dół. Bardziej formalnie, dla każdego (i,j) pamiętamy najmniejsze i'\geq i, dla którego kolor pola (i',j) jest inny niż kolor pola (i,j), oraz najmniejsze j' \geq j, dla którego kolor pola (i,j') jest inny niż kolor pola (i,j). Pozwala to na wygenerowanie wszystkich przeskoków na dowolnym odcinku poziomym i dowolnym odcinku pionowym w czasie proporcjonalnym do liczby wygenerowanych przeskoków „skacząc” do kolejnego przeskoku. A przecież brzeg dowolnego odcinka możemy przedstawić jako dwa odcinki poziome i dwa odcinki pionowe! Oczywiście musimy pamiętać o tym, że gdy tylko wygenerujemy przynajmniej 4 przeskoki, możemy ze spokojnym sumieniem zakończyć pracę. Pozwala to na zaimplementowanie całego testu w czasie stałym (zakładając preprocessing proporcjonalny do rozmiaru planszy).

Fajnie, ale nijak nie załatwia to kwestii obszarów drugiego typu. Pozwala jednak na policzenie obszarów pierwszego typu. Teraz potrzebna jest jeszcze jedna sztuczka!

Wybierzmy w każdym obszarze (na całej planszy) jedno pole i nazwijmy je jego reprezentantem. Zliczenie obszarów drugiego typu w naszym wycinku sprowadza się do zliczenia reprezentantów, którzy leżą w tymże wycinku. No, prawie: może bowiem być tak, że reprezentant obszaru pierwszego typu także znajduje się w wycinku. Przypomnijmy jednak, że wiemy już, że jest tylko jeden lub dwa obszar pierwszego typu. Co więcej, opisana wyżej metoda pozwala tak naprawdę na wygenerowanie ich nazw, a co za tym idzie także dobranie się do ich reprezentantów. Moglibyśmy więc najpierw zliczyć reprezentantów, którzy leżą w wycinku, a następnie odjąć od wyniku liczbę reprezentantów obszarów pierwszego typu, które zostali niesłusznie policzeni. (Tutaj trzeba trochę uważać: ten sam obszar pierwszego typu może zostać wygenerowany nawet czterokrotnie, trzeba wziąć to pod uwagę.) To „naprawianie” zajmie tylko czas stały. Ale jak zliczyć reprezentantów?

Prosto. Jeśli w każdym polu zapiszemy 1 lub 0 w zależności od tego, czy jest ono reprezentantem jakiegoś obszaru, musimy tylko umieć szybko policzyć sumę pól w danym prostokącie. A to jest już zupełnie standardowe: wystarczy zapamiętać dla każdego (i,j) sumę wszystkich pól (i',j'), gdzie i'\geq j, j'\geq j. Taki preprocessing wymaga czasu i pamięci proporcjonalnej do rozmiaru planszy, a później pozwala na policzenie sumy w dowolnym prostokącie w czasie stałym.

Daje to rozwiązanie działające w sumarycznym czasie \mathcal{O}(nm+q). Jako ciekawe ćwiczenie na słoneczne popołudnie proponuję zaś następujące pytanie: jeśli w lemacie zamienimy 3 na k, to na co powinniśmy zamienić 4?

Reklamy

5 myśli nt. „Prostokąty i obszary

  1. Na Yandexie jest 100 minut na 6 zadań, więc nie powinno dziwić, że zadanie „Dodaj 2 liczby” mogłoby tam być nieruszone :P. Tym bardziej jak nikt go do tej pory nie rozwiązał, a inne wydają się łatwiejsze, ale nie aż na tyle, aby zdążyć z wszystkimi w tyle czasu :P.

  2. Hm, poczyniłem zbyt duży skrót myślowy :P. Miałem na myśli coś w stylu „Tym bardziej z perspektywy zawodnika nie ma sensu się za nie zabierać, jak nikt go do tej pory nie rozwiązał (…)” :P. A na conteście aktualnie zerowa liczba akceptów powoduje, że nikt go nie robi i cały czas liczba akceptów zostaje zerowa itd. i spirala „nienaruszoności” się nakręca :D.

  3. Tak się zastanawiam nad zadaniem bez tego sztucznego limitu : powiedzmy, że mam sobie takiego czarnego kleska i obchodze go zgodnie z ruchem wskazówek zegara mierząc na liczniku ile przejechałem. Dla każdego punktu na obwodzie mogę sobie więc zapamiętać pewną liczbę (ów dystans mierzony od jakiegoś tam wyróżnionego punktu). Mogę sobie potem dla każdego „przeskoku” jaki znajdę na ramcę opisać go dwiema liczbami: (kleks_id,ccw_distance). I teraz chyba powinienem móc ustalić który przeskok z który innym przeskokiem jest połączony brzegiem kleksa: chyba wystarczy sprawdzić czy ten przeskok jest z bieli do czerni czy czerni do bieli i czy w związku z tym do jego „kolegi” idziemy zgodnie czy przeciwnie do ruchu wskazówek zegara i czy zatem interesuje nas maximum czy minimum z ccw_distance innych przeskoków o tym samym kleks_id. Wydaje mi się więc, że powinienem móc sobie stworzyć taki „uproszczony model topologii” – nie wiem co dokładnie jest narysowane wewnątrz ramki, ale wiem mniej więcej ile mam spójnych składowych kleksów. Dobrze kombinuję?

  4. Jeśli „dotkniesz” każdego obszary na brzegu, to pewnie możesz. Natomiast nie widzę jak można rozwiązać to zadanie wersji „sprawdź, czy odpowiedź jest <=k" szybciej niż w O(k).

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s