Omówienie zadania Spotkanie na Bajhattanie (II etap XXXIII OI)

Dane jest \(n\) punktów o współrzędnych całkowitych. Dla każdego \(1 \leq k \leq n\) chcemy znaleźć punkt o współrzędnych całkowitych, od którego dokładnie \(k\) punktów wejściowych znajduje się w maksymalnej odległości manhattańskiej, lub stwierdzić, że taki punkt nie istnieje.

Rozwiązanie brutalne – podzadanie 1

W pierwszym podzadaniu mamy \(n, |x_i|, |y_i| \leq 50\). Możemy sprawdzić wszystkie punkty \((x, y)\) z najmniejszego prostokąta o bokach równoległych do osi, który zawiera wszystkie punkty wejściowe. Dla każdego kandydata obliczamy odległości manhattańskie do wszystkich punktów i zliczamy, ile z nich jest w odległości maksymalnej.

Dlaczego wystarczy szukać wewnątrz tego prostokąta? Załóżmy, że pewien punkt \((x, y)\) leżący na lewo od prostokąta (tzn. \(x \lt x_\text{min}\)) jest rozwiązaniem dla pewnego \(k\). Przesuwając go o jedną jednostkę w prawo, zmniejszamy odległość do każdego punktu wejściowego o dokładnie 1 (bo wszystkie punkty leżą na prawo od nas). Zatem zbiór punktów najdalszych nie zmienia się. Powtarzając ten krok, dochodzimy do punktu \((x_\text{min}, y)\), który też jest rozwiązaniem dla tego samego \(k\). Powtarzając analogiczne rozumowanie dla pozostałych trzech kierunków, zawsze możemy dojść w ten sposób do punktu na brzegu prostokąta, dla którego zbiór punktów najdalszych jest taki sam, jak dla \((x, y)\), co kończy dowód.

Złożoność tego rozwiązania to \(O(n \cdot M^2)\), gdzie \(M\) jest największą wartością bezwzględną współrzędnej na wejściu.

Kluczowa obserwacja – obrót układu współrzędnych

Ustalmy punkt \((x, y)\) i niech \(d\) będzie maksymalną odległością manhattańską od \((x, y)\) do punktów wejściowych. Punkty w odległości dokładnie \(d\) leżą na brzegu „diamentu" – kwadratu obróconego o \(45^{\circ}\), o przekątnej \(2d\), o środku w \((x, y)\).

Aby uprościć analizę, zastosujemy standardowy trik, którego dokładniejszy opis można znaleźć na przykład w omówieniu zadania Magazyn z XIII OI. Przekształcamy współrzędne punktów na wejściu według wzoru \[(x, y) \rightarrow (x - y,\; x + y).\] To przekształcenie sprawia, że możemy myśleć o zmodyfikowanej wersji zadania, gdzie odległości między punktami nie są mierzone w metryce manhattańskiej, ale w metryce maksimum. W tej metryce odległość między dowolnymi punktami \((x_1, y_1)\) i \((x_2, y_2)\) nie jest już równa \[|x_1 - x_2| + |y_1 - y_2|\] tylko \[\max(|x_1 - x_2|, |y_1 - y_2|).\]

Ponownie ustalmy punkt \((x, y)\) i niech \(d\) będzie maksymalną odległością w metryce maksimum od \((x, y)\) do punktów wejściowych. Punkty w odległości dokładnie \(d\) leżą na brzegu (tym razem nieobróconego) kwadratu o boku \(2d\) i środku w \((x, y)\).

Zwróćmy uwagę, że przekształcenie odwrotne do naszego obrotu to \[(x, y) \rightarrow \left(\frac{x+y}{2},\; \frac{y-x}{2}\right).\] Pozwoli nam ono przekładać rozwiązania znalezione w przekształconym układzie współrzędnych z powrotem na rozwiązania w oryginalnym układzie współrzędnych.

Od tej pory w reszcie rozwiązania będziemy więc zakładać, że pracujemy z metryką maksimum.

Rozważmy teraz najmniejszy prostokąt o bokach równoległych do osi, który zawiera wszystkie punkty wejściowe. Pokażemy następujący fakt: punkty z wejścia, które znajdują się wewnątrz tego prostokąta, a nie na jego brzegu, nigdy nie mogą być najdalsze od żadnego punktu na płaszczyźnie.

Dlaczego jest to prawdą? Niech \((x_{\text{min}}, x_\text{max})\) i \((y_\text{min}, y_\text{max})\) będą zakresami współrzędnych rozważanego prostokąta. Weźmy pewien punkt \((x, y)\) i załóżmy, że jest on najdalej od pewnego punktu \((x_i, y_i)\), który leży wewnątrz prostokąta. Skoro \((x_i, y_i)\) jest wewnątrz, to \(x_{\text{min}} \lt x_i \lt x_\text{max}\) i \(y_{\text{min}} \lt y_i \lt y_\text{max}\). Dla ustalenia uwagi załóżmy, że \(x \leq x_i\) oraz \(y \leq y_i\), czyli że punkt \((x, y)\) leży na lewo i poniżej punktu \((x_i, y_i)\). Wówczas mamy \[ |x - x_i| = x_i - x \lt x_\text{max} - x = |x - x_\text{max}| \] oraz \[ |y - y_i| = y_i - y \lt y_\text{max} - y = |y - y_\text{max}|. \] W związku z czym istnieje pewien punkt na brzegu prostokąta (którego wspołrzędna \(x\) to \(x_\text{max}\) lub jego współrzędna \(y\) to \(y_\text{max}\)), który znajduje się dalej od \((x, y)\) niż \((x_i, y_i)\) według metryki maksimum.

Możemy powtórzyć bardzo podobne rozumowanie dla pozostałych trzech przypadków zależnie od wzajemnej relacji \(x\) i \(x_i\) oraz \(y\) i \(y_i\). W każdym z nich, podobnie jak w tym już rozważonym, będziemy w stanie znaleźć pewnien punkt na brzegu prostokąta, który jest dalej od \((x, y)\) niż \((x_i, y_i)\).

W związku z tym, jeśli punkt \((x, y)\) ma być najdalej od pewnego punktu wejściowego, to ten punkt wejściowy musi leżeć na brzegu rozważanego prostokąta.

Szybsze rozwiązanie brutalne - podzadanie 2

Powyższa obserwacja pozwala przyspieszyć rozwiązanie brutalne. Skoro tylko punkty na brzegu prostokąta ograniczającego mogą być najdalsze, to podczas szukania punktów najdalszych od ustalonego \((x, y)\) wystarczy rozważyć tylko punkty z brzegu tego prostokąta. Wszystkie te punkty możemy ponadto zdeduplikować tak, aby otrzymać zbiór parami różnych punktów z wagami odpowiadającymi liczbie punktów wejściowych równych danemu punktowi. W ten sposób otrzymujemy zbiór \(O(M)\) punktów z wagami (jeden punkt reprezentuje wiele punktów wejściowych, jeśli mają takie same współrzędne), dzięki czemu sprawdzenie wyniku dla danego \((x, y)\) zajmuje czas \(O(M)\), a nie \(O(n)\).

Takie rozwiązanie daje nam więc złożoność \(O(M^3)\), bo mamy \(O(M^2)\) kandydatów \((x, y)\) i każdego sprawdzamy w \(O(M)\).

Rozwiązanie wzorcowe – analiza przypadków

Podobnie jak wyżej nadal będziemy zakładać, że pracujemy z wersją zadania z odległościami w metryce maksimum.

Przejdźmy do kolejnej kluczowej obserwacji. Ustalmy punkt \((x, y)\) i załóżmy, że pewien punkt \((x_i, y_i)\) na brzegu prostokąta ograniczającego jest od niego najdalej. Ponadto załóżmy, że \(|x - x_i| \gt |y - y_i|\), czyli w szczególności odległość w metryce maksimum między tymi punktami jest równa dokładnie \(|x - x_i|\).

Wówczas punkt \((x_i, y_i)\) musi leżeć na lewym lub prawym boku prostokąta ograniczającego. Gdyby bowiem leżał na górnym lub dolnym boku, to mielibyśmy punkt na lewym lub prawym boku, który jest jeszcze dalej we współrzędnych \(x\) od \((x, y)\), co jest sprzeczne z założeniem, że \((x_i, y_i)\) jest najdalej od \((x, y)\).

Rozważmy więc bok prostokąta (lewy lub prawy), na którym leży punkt \((x_i, y_i)\) oraz dowolny inny punkt \((x_j, y_j)\) na tym boku. Oczywiście mamy \(x_i=x_j\), gdyż punkty leżą na tym samym boku, a zatem \(|x - x_i| = |x - x_j|\). Z założenia, że \((x_i, y_i)\) jest najdalej od \((x, y)\) oraz tego, że \(|x - x_i| \gt |y - y_i|\), wynika też, że \(|y-y_j| \leq |x-x_i|\). W związku z tym punkt \((x_j, y_j)\) jest również najdalej od \((x, y)\).

Analogicznie jeśli mamy \(|y - y_i| \gt |x - x_i|\), to punkt \((x_i, y_i)\) musi leżeć na górnym lub dolnym boku prostokąta i wówczas wszystkie punkty na tym boku są również najdalej od \((x, y)\).

Pozostaje zastanowić się, co dzieje się gdy \(|x - x_i| = |y - y_i|\). Korzystając z tego, że \((x_i, y_i)\) jest najdalej od \((x, y)\), można pokazać, że musi on leżeć w rogu prostokąta ograniczającego (gdyby tak nie było, możemy wskazać inny punkt na brzegu, który jest jeszcze dalej od \((x, y)\)).

 

Nietrudno widzieć, że wówczas wszystkie punkty na obu bokach przyległych do rogu prostokąta ograniczającego, na którym leży \((x_i, y_i)\), są najdalej od \((x, y)\).

Nasze obserwacje możemy podsumować następująco: jeśli punkt \((x_i, y_i)\) leżący na brzegu prostokąta ograniczającego jest najdalej od \((x, y)\), to

• jeśli \((x_i, y_i)\) nie leży w rogu tego prostokąta, to wszystkie punkty na tym samym boku prostokąta co \((x_i, y_i)\) także są najdalej od \((x, y)\),
• jeśli \((x_i, y_i)\) leży w rogu tego prostokąta, to wszystkie punkty na pierwszym z dwóch boków przyległych do tego rogu są najdalej od \((x, y)\) lub wszystkie punkty na drugim z tych boków są najdalej od \((x, y)\).

Zwracamy przy tym uwagę na użycie „lub" w drugim punkcie – może być tak, że oba te zbiory punktów są najdalej od \((x, y)\), ale nie musi.

Powyższe rozumowanie pokazuje, że odpowiedź różną od NIE możemy otrzymać tylko dla co najwyżej 15 różnych wartości \(k\). Jest tak dlatego, że mamy dokładnie 15 niepustych podzbiorów zbioru 4 boków prostokąta ograniczającego i wiemy już, że jeśli za najdalszy weźmiemy punkt na jakimś boku, to wszystkie punkty na tym boku też będą najdalej (zakładając, że punkty na rogach możemy traktować raz jako należące do jednego boku, a raz do drugiego).

Rozważmy więc każdy z 15 niepustych podzbiorów boków oddzielnie. Dla każdego spróbujemy znaleźć punkt \((x, y)\), dla którego najdalej od niego leżą dokładnie punkty na wybranych bokach (a nie na żadnych innych). Ze względu na symetrię prostokąta te 15 podzbiorów można pogrupować w 5 typów – wystarczy rozwiązać każdy typ dla jednej orientacji, a pozostałe uzyskać przez obroty (patrz sekcja „Implementacja").

W poniższych przypadkach boki prostokąta oznaczamy jako: L (lewy, \(x = x_\text{min}\)), R (prawy, \(x = x_\text{max}\)), D (dolny, \(y = y_\text{min}\)), G (górny, \(y = y_\text{max}\)).

(a) Jeden bok – np. {L}

Chcemy, by bok L był najdalej, a boki R, D, G bliżej. Wystarczy wybrać punkt wystarczająco daleko na prawo od prostokąta, np. \((D, 0)\) dla dużego \(D\). Jeśli dobierzemy \(D\) tak, aby wszystkie punkty na wejściu miały współrzędne dużo mniejsze niż \(D\) (np. \(D = 10^{12}\)), to odległość do L będzie największa pośród odległości do wszystkich boków.

(b) Dwa sąsiednie boki – np. {L, D}

Chcemy, by boki L i D były jednakowo odległe i dalej niż R i G. Równość odległości do L i D daje nam, że punkt musi leżeć na półprostej o nachyleniu \(45^{\circ}\) wychodzącej z lewego dolnego rogu prostokąta. Wybieramy punkt daleko wzdłuż tej półprostej, np. \((x_\text{min} + D,\; y_\text{min} + D)\). Przy dostatecznie dużym \(D\) odległość do R i G jest mniejsza niż odległość do L i D.

(c) Dwa przeciwległe boki – np. {L, R}

Chcemy, by boki L i R były jednakowo odległe, a boki D i G bliżej. Równość odległości do L i R wymusza \[x = \frac{x_\text{min} + x_\text{max}}{2}.\] Odległość od tego \(x\) do L (i R) wynosi \(d_x = (x_\text{max} - x_\text{min}) / 2\). Musimy jeszcze zapewnić, że odległość do D i G nie przekracza \(d_x\). Wybierając \(y = (y_\text{min} + y_\text{max}) / 2\), minimalizujemy odległość do D i G – wynosi ona \(d_y = (y_\text{max} - y_\text{min}) / 2\). Przypadek ten zachodzi więc wtedy i tylko wtedy, gdy \(d_x \gt d_y\) (prostokąt jest „szerszy" niż „wyższy").

Zauważmy, że jeśli \(x_\text{min} + x_\text{max}\) jest nieparzyste, to \(x\) wynikające z powyższego warunku nie jest liczbą całkowitą, zatem punkt minimalizujący odległość o współrzędnych całkowitych nie istnieje i nie możemy uzyskać rozwiązania dla tego przypadku. Jeśli natomiast \(y_\text{min} + y_\text{max}\) jest nieparzyste, to dla \(y\) możemy spróbować dwóch możliwości: \(\lfloor(y_\text{min} + y_\text{max}) / 2\rfloor\) lub \(\lceil(y_\text{min} + y_\text{max}) / 2\rceil\).

(d) Trzy boki – np. {L, R, D}

Chcemy, by boki L, R i D były jednakowo odległe, a bok G bliżej. Z przypadku (c) mamy \(x = (x_\text{min} + x_\text{max}) / 2\) i \(d_x = (x_\text{max} - x_\text{min}) / 2\). Żeby D był w tej samej odległości \(d_x\), potrzebujemy \(y = y_\text{min} + d_x\). Bok G musi być bliżej, co zachodzi gdy \(y_\text{max} - y \lt d_x\), czyli gdy prostokąt jest „szerszy" niż „wyższy". Daje to co najwyżej jednego kandydata, o ile jego współrzędne okazują się być całkowite.

(e) Cztery boki – {L, R, D, G}

Szukamy punktu jednakowo odległego od wszystkich czterech boków. Jest to możliwe tylko wtedy, gdy prostokąt jest kwadratem (\(d_x = d_y\)), a jedynym kandydatem jest jego środek – o ile jego współrzędne są całkowite.

Odzyskiwanie wyników dla oryginalnego układu współrzędnych

Zwróćmy uwagę, że przekształcenie \((x, y) \rightarrow (x - y,\; x + y)\) przekształca nam punkty o współrzędnych całkowitych w punkty o współrzędnych całkowitych, natomiast jego przekształcenie odwrotne \((x, y) \rightarrow \left(\frac{x+y}{2},\; \frac{y-x}{2}\right)\) niekoniecznie. Mówiąc dokładniej, przekształcenie odwrotne daje nam punkt o współrzędnych całkowitych wtedy i tylko wtedy, gdy \(x\) oraz \(y\) mają taką samą parzystość. Oznacza to, że znalezienie odpowiedniego punktu w przekształconym układzie współrzędnych nie zawsze gwarantuje znalezienie odpowiedniego punktu w oryginalnym układzie współrzędnych.

W przypadku (a) wybrany punkt zawsze ma współrzędne o tej samej parzystości, więc ten problem nie występuje. W przypadku (b) parzystość sumy \(x+y\) wzdłuż półprostej jest stała, więc jeśli wybrany punkt ma współrzędne o różnej parzystości, to wszystkie punkty na tej półprostej też mają, czyli wynik dla tego przypadku nie istnieje. W przypadku (c) nie możemy zmieniać współrzędnej \(x\), ale możemy zmieniać współrzędna \(y\). Jeśli więc współrzędne wybranego punktu mają różną parzystość, można rozważać punkty, które są o 1 wyżej lub o 1 niżej od wybranego punktu. Ostatecznie w przypadkach (d) oraz (e) punkt wyznaczony jest jednoznacznie, więc wystarczy go odrzucić, gdy jego współrzędne mają różną parzystość.

Implementacja i złożoność

Zamiast implementować wszystkie przypadki osobno, wystarczy zaimplementować każdy typ (a)-(e) dla jednej orientacji boków, a następnie powtórzyć obliczenia po obróceniu całego zbioru punktów o \(90^{\circ}\), \(180^{\circ}\) i \(270^{\circ}\). Dzięki temu pokrywamy wszystkie podzbiory boków.

Dla każdego znalezionego kandydata sprawdzamy w czasie \(O(n)\), ile punktów jest od niego najdalszych. Ponieważ kandydatów jest stała liczba (co najwyżej kilkadziesiąt, uwzględniając obroty i zaokrąglenia), całkowita złożoność czasowa i pamięciowa wynosi \(O(n)\).

Alternatywnie, zliczając z góry liczbę punktów na każdym boku i w każdym rogu prostokąta ograniczającego, możemy sprawdzić każdego kandydata w czasie stałym, redukując stałą ukrytą w notacji wielkiego O. Nie było to jednak konieczne, aby rozwiązać to zadanie.