Rakieta

Dzisiaj zajmiemy się wykrywaniem pocisków balistycznych. Będzie prawie poważnie, bo wiadomo: z takimi pociskami nie ma żartów! Ale nie całkiem poważnie, gdyż rozważymy uproszczoną wersję, w której rakieta jest punktem startującym z pozycji x=p na prostej i poruszającym się w prawo z prędkością v. O p i v wiemy tylko tyle, że 0\leq p,v\leq 10^5, ale mimo to chcielibyśmy wyznaczyć aktualną pozycję. Jedynym narzędziem, z którego możemy skorzystać, jest czarna skrzynka, które umożliwia nam sprawdzenie (dla dowolnie wybranych L,R), czy aktualna pozycja należy do przedziału [L,R]. Odpowiedź na każde kolejne pytanie zajmuje jedną jednostkę czasu, więc jest to prawdziwy wyścig z czasem. Tym bardziej, że po upływie 100 jednostek następuje detonacja, a z tym to już na pewno nie ma żartów. Przed dalszą lekturą proponuję jednak następującą zagadkę: z jakiego regionu ACM ICPC pochodzi to zadanie?

Jest to zadanie I z tegorocznej edycji ACM ICPC NEERC, cały zestaw można zobaczyć tutaj. Nie było to co prawda najtrudniejsze zadanie w tym zestawie (aż 3 z pozostałych nie udało się rozwiązać żadnej ze startujących tam drużyn, a jak pewnie wiecie, region ten jest wyjątkowo mocny), było jednak moim zdaniem najfajniejsze. Nie wymaga znajomości zaawansowanych technik ani wytrwałości w implementacji, lecz mimo to nie jest trywialne, szczególnie gdy chcemy (mniej lub bardziej formalnie) uzasadnić poprawność uzyskanego rozwiązania. A przecież chcemy, nie?

Zacznijmy może od mocno uproszczonej wersji, w której v=0, czyli rakieta stoi w miejscu x=p. Celem jest wyznaczenie tego p używając pytań postaci „czy p\in [L,R]?”. Od razu widać, że należy skorzystać tutaj z wyszukiwania binarnego. Zaczynamy wiedząc, że p\in [0,10^5]. Wiedząc, że p\in [\ell,r], sprawdzamy czy p\in [\ell,\lfloor\frac{\ell+r}{2}\rfloor] używająć jednego pytania. Jeśli tak, zastępujemy r przez \lfloor\frac{\ell+r}{2}\rfloor, w przeciwnym wypadku zaś zastępujemy \ell przez 1+\lfloor\frac{\ell+r}{2}\rfloor. Łatwo sprawdzić, że każda iteracja zmniejsza ilość pozostałych kandydatów z t do \lceil \frac{t}{2}\rceil, czyli po co najwyżej 1+\lceil\log(10^5+1)\rceil iteracjach doprowadzimy do sytuacji, w której \ell=r, co tak naprawdę daje nam szukane p.

No dobrze, ale przecież nie możemy zakładać, że v=0. W ogólnym przypadku sytuacja staje się o tyle niezręczna, że odpowiedź, którą dostajemy w i-tej iteracji to tak naprawdę „czy p+iv\in[L,R]„, a przecież nie mamy żadnej kontroli nad tym jakie jest i (no, oprócz takiej, że możemy sobie chwilę poczekać, ale pewnie nie jest to szczególnie rozsądne). Tym niemniej można spróbować uogólnić poprzednią metodę, czyli próbować w kolejnych iteracjach istotnie zmniejszać przestrzeń możliwych rozwiązań.

Wypada zacząć od wyobrażenia sobie przestrzeni możliwych rozwiązań. Są to po prostu punkty (x,y), gdzie początkowo wiemy tylko, że x,y\in [0,10^5]. Pytając w i-tej iteracji o [L,R] tak naprawdę pytamy, czy dla naszego szukanego punktu (x,y) jest L\leq xi+y\leq R. W zależności od wyniku pozbywamy się następnie tych punktów (x,y), dla których L\leq xi+y\leq R (jeśli odpowiedź była negatywna) lub tych, dla których xi+y <L \wedge R < xi+y (jeśli odpowiedź była npozytywna). Nie mamy żadnego wpływu na to, jaką odpowiedź uzyskamy (i znając autora zadania pewnie zawsze dobierze on ją tak, aby postawić nas w jak najtrudniejszej sytuacji), musimy więc dobrać [L,R] tak, aby niezależnie od odpowiedzi pozbyć się wielu punktów.

Jeśli kolejno zadawane pytania się dowolne, trochę ciężko jest wyobrażać sobie zbiór pozostałych punktów. Powiedzmy więc, że zawsze będziemy pytać „czy xi+y\leq R?”. Wtedy tak naprawdę w zależności od odpowiedzi pozbywamy się wszystkich punktów nad lub pod pewną prostą y=ax+b! Oznacza to, że zbiór pozostałych punktów P będzie cały czas zbiorem wypukłym. Tak naprawdę powinniśmy więc pokazać, że dla dowolnego takiego zbioru wypukłego można wskazać prostą y=ax+b, która dzieli go mniej więcej na dwie równe części, prawda?

Prawie prawda. To znaczy właściwie nieprawda. Nie mamy bowiem żadnej kontroli nad a=-i, możemy tylko manipulować (dowolnie) wartością b. Tym niemniej wydaje się, że zwykle wystarcza to, aby w miarę równo podzielić P. Popatrzmy na poniższą ilustrację.

rakieta

Wyobraźmy sobie, że zaczynamy z b=-\infty i przesuwamy naszą prostą w górę aż do b=\infty. Niech f(b) będzie liczbą punktów w P, dla których y=ax+b. Wtedy tak naprawdę chcielibyśmy dobrać b tak, aby zarówno \sum_{b' < b} f(b) jak i \sum_{b'\geq b} f(b) były istotnie mniejsze niż |P|=\sum_{b'} f(b). Czasami jest to jednak w dość oczywisty niemożliwe. Wyobraźmy sobie bowiem, że wszystkie punkty leżą na pewnej prostej y=ax+b. Wtedy nijak nie uda nam się zmniejszyć aktualnego zbioru wybierając prostą z takim a! Jeśli jednak jest tak, że f(b') \leq 1+\frac{1}{2} |P| dla każdego b', na pewno istnieje b', dla którego \sum_{b' < b} f(b) \leq \frac{|P|}{4} i \sum_{b'\geq b} f(b) \leq \frac{|P|}{4}. Czemu? Popatrzmy na \sum_{b' < b} f(b). Dla b'=\infty suma ta jest równa 0, dla b'\infty wzrasta do |P|. Jeśli zaś pomyślimy o tym, jak zmienia się ona po zwiększeniu b', łatwo dojść do wniosku, że nie może ona wzrosnąć o więcej niż 1+\frac{|P|}{2}. Czyli na pewno można wybrać b' tak, aby suma była między \frac{1}{2}|P| a \frac{3}{4}|P|, a o to nam tak naprawdę chodziło.

Czyli doszliśmy do wniosku, że jeśli tylko f(b') \leq 1+\frac{1}{2} |P| dla każdego b', istnieje pytanie, które (niezależnie od odpowiedzi) pozwoli nam na istotne zmniejszenie zbioru kandydatów. Ale co jeśli mamy pecha i wcale tak nie jest? Pewnie nic, załóżmy więc, że sytuacja jest naprawdę tragiczna, czyli nie dość, że dla pewnego b' mamy, że f(b') > 1+\frac{1}{2}|P|, to jeszcze odpowiedź na zadane pytanie nie pozwoliła nam wyeliminować żadnego z punktów leżących na prostej y=ax+b', które wszystkie należą do nowego zbioru kandydatów P'. W kolejnej iteracji przesuwamy prostą y=(a+1)x+b''. Podobnie jak przed chwilą, niech g(b'') będzie liczbą punktów z P', dla których y=(a+1)x+b''. Teraz trzeba tylko zauważyć, że nie może istnieć b'', dla którego g(b'') > 1+\frac{1}{2}|P|. Oznaczałoby by to bowiem, że mamy więcej niż jeden punkt, który jednocześnie leży na dwóch nierównoległych prostych y=ax+b' i y=(a+1)x+b''! A to oznacza, że po dwóch iteracjach na pewno uda nam się zmniejszyć liczbę kandydatów o przynajmniej jedną czwartą.

No i fajnie. Pokazaliśmy, że zawsze można dobrać pytania tak, aby zagwarantować zmniejszenie się zbioru kandydatów o przynajmniej jedną czwartą w dwóch kolejnych iteracjach. Skoro początkowy zbiór zawiera (10^5+1)^2 par, oznacza to, że na pewno zmieścimy się w 132 iteracjach. To trochę więcej niż wspomniane na samym początku 100, ale to tylko dlatego, że powyższa analiza była nieco niechlujna. Można na przykład dodatkowo zauważyć, że pierwszy moment, którym mamy pecha, może pojawić się dopiero wtedy, gdy |P| < 2*10^5, co od razu zmniejsza ograniczenie górne na liczbę iteracji do 102. Dodając obserwację, że tak naprawdę mając pecha w dwóch iteracjach zmniejszamy liczbę kandydatów przynajmniej o \frac{3}{8}|P| lub wracając do obserwacji, że P jest zbiorem wypukłym, można zmniejszyć to ograniczenie poniżej 100.

Ale czy na pewno daje nam to efektywne rozwiązanie całego zadania? Pokazaliśmy tylko, że istnieje ciąg pytań, które zagwarantują nam zwycięstwo. Czy umiemy je także szybko wygenerować? Hmmm.

Przede wszystkim należy jakoś utrzymywać zbiór pozostałych kandydatów. Skoro początkowo |P|=(10^5+1)^2, pewnie nie można tego robić całkiem naiwnie. Nie jest to jednak trudne: wystarczy na przykład zauważyć, że skoro P jest wypukły, dla każdego x współrzędne y punktów o właśnie takim x tworzą spójny przedział [\alpha_x,\beta_x]. Wystarczy więc dla każdego x=0,1,\ldots,10^5 utrzymywać końce tego przedziału. Pozostaje tylko pokazać, jak szybko wyznaczyć kolejne pytanie, czyli tak naprawdę b', dla którego prosta y=ax+b' dzieli aktualny zbiór mniej więcej na pół. Najprościej użyć do tego wyszukiwania binarnego. Skoro bowiem zwiększając b' zwiększamy liczbę punktów, które leżą poniżej prostej, tak naprawdę wystarczy wyszukać binarnie b', dla którego ta liczba to mniej więcej \frac{1}{2}|P| (dla odpowiedniej definicji mniej więcej, której znalezienie pozostawiam Czytelnikowi). Aby zaimplementować wyszukiwanie binarne, musimy tylko umieć policzyć dla każdego x wartość |y\in[\alpha_x,\beta_x]: y\leq ax+b'\}|. Nie jest to jednak specjalnie trudne.

Opisane powyżej rozwiązanie spokojnie mieści się w limicie czasu, zarówno tego procesora, jak i tego, który pozostał do eksplozji. Warto się jednak zastanowić, czy można zmniejszyć ten pierwszy. Okazuje się, że wyszukiwanie binarne użyte do wyliczenia b' nie jest najlepszym możliwym pomysłem. Można (po chwili zastanowienia) zastąpić je wyszukiwaniem k-tego elementu w czasie liniowym, co pozostawiam jako ciekawe ćwiczenie dla Czytelnika. Można też podejść trochę inaczej do utrzymywania zwięzłego opisu aktualnego P wracając do obserwacji, że jest to zbiór wypukły, co także pozostawiam jako (mniej ciekawe) ćwiczenie.

Advertisements

4 myśli nt. „Rakieta

  1. Fajne zadanie. Rozwiązanie też fajne, bo opisaną przez Ciebie technikę da się pewnie zastosować do wielu problemów. Nie mniej to konkretne zadanie wydaje się mieć kilka cech z których jakby nie korzystasz. Ciekawe czy da się tu coś ugrać dzięki temu, że w zadaniu nie proszą o znalezienie początkowego punktu i początkowej prędkości, a „jedynie” o znalezienie obecnej pozycji. Intuicyjnie usuwa to jeden stopień swobody, więc być może przeszukiwana przestrzeń może się istotnie zmniejszyć? Albo inny kierunek myślenia : po 100 krokach, z prędkością 10^5, rakieta nie może zalecieć dalej niż do ~10^7, więc może da się to jakoś rozwiązać w log(10^7) zamiast log(10^10) ? Albo jeszcze inaczej: wiedząc, że rakieta zaczyna na lewo od 10^5 i że leci nie szybciej niż 10^5, może można ustawić takie jakby dwa checkpointy „start gate” i „finish gate” i zmierzyć jej najpierw prędkość?

  2. No to jest rozwiązanie, który było dla mnie najbardziej naturalne, choć całkiem możliwe, że nie jest najprostsze. Trochę popatrzyłem na inne, ale wyglądało mi na to, że może być trudniej uzasadnić ich poprawność (przynajmniej dla mnie). Nie wiem czy da się zbić log(10^10), ale da się pozbyć tego 10^5 na zliczanie, stąd uwaga o „zwięzłym opisie” (mając wielokąt o 100 bokach, można szybko zliczyć punkty w środku, a w sumie to robimy).

  3. Fajne zadanie :). Dzisiaj robiliśmy NEERCa na treningu na UW i idea w zasadzie taka sama. Ja osobiście nienawidzę wszechobecnego manieryzmu niektórych olimpijczyków, którzy wymyślają bezsensowne algorytmy mówiąc „widać, że działa, a dowodzić to sobie mogą matematycy”, ale jeżeli nie chce się skopywać konkursów, to warto czuć odpowiednią granicę pomiędzy algorytmami, które widać, że działają, choć konkretny dowód mógłby być trochę żmudny, a algorytmami, które wyglądają podejrzanie – na pewno w trakcie konkursu nie warto się wdawać w takie dokładne rozważania jak tutaj (ale już po nim, czemu nie?). Rzeczywiście jeżeli nasz zbiór punktów to prosta, to możliwe, że pewna iteracja nie pozwoli nam zmniejszyć przestrzeni stanów ani o jeden punkt, ale wtedy każda następna będzie mogła podzielić idealnie na pół. A jeżeli nie leżą na jednej prostej, ale ciągle punktów jest w miarę dużo i nie umiemy ich w miarę równo podzielić, to jak przekręcimy nasz pas o niewiele to już będziemy mogli bardzo drobno siekać nasz zbiór. To 100 to na pewno jest bardzo na wyrost. Do rozwiązania doprowadzi zapewne jakakolwiek sensowna metoda dzielenia na „pół”. My robiliśmy tak, że najpierw przekształcaliśmy nasz wielokąt w każdym kroku, aby te skośne proste były poziome i liczyliśmy środek ciężkości. Ja też zaproponowałem, aby walnąć po prostu prostą w połowie między najwyższym, a najniższym punktem zbioru (już po przekształceniu) – zapewne też by weszło, ale tu już bym głowy nie dał. Inni za to losowali k z przedziału [1, liczba punktów w wielokącie] i liczyli k-ty punkt zbioru w porządku leksykograficznym i przez niego prowadzili prostą. A oczywiście można też binary-searchem najlepsze cięcie znaleźć, ale to to trochę droższe czasowo i więcej kodu.

    A nad rozwiązaniami idącymi w innym kierunku raczej bym się nie zastanawiał – każde zapytanie to jest dokładnie przecięcia naszego aktualnego zbioru z jakimś odpowiednio nachylonym pasem i dopóki to przecięcie jest większe niż 1 punkt, to więcej niż 1 punkt spełnia warunki zadania. A raczej bym nie szukał możliwości uzyskania odpowiedzi bez pozyskania początkowego położenia i stanu, bo to by był równoważne temu, że w pewnym k-tym kroku nasz zbiór będzie się zawierał w pewnej prostej o odpowiednim współczynniku kierunkowym, a czegoś takiego na pewno nie da się uzyskać w istotnie łatwiejszym algorytmem niż tymi cięciami, które dają pełny obraz problemu. Żeby walnąć takie cięcia, po których zostałaby pewna prosta o określonym współczynniku trzeba by się trochę napracować raczej…

    • Mówienie, że “widać, że działa, a dowodzić to sobie mogą matematycy” jest o tyle kiepskie, że (dla mnie) dowodzenie, że działa, jest najciekawszą częścią 🙂 W sumie nawet bym powiedział, że ciekawa część informatyki to w zasadzie matematyka…

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s