Testy alergiczne

Z lekkim opóźnieniem, ale jeszcze przed (moim) urlopem proponuję ciekawe zadanie Allergy Testing z finału Google Code Jam 2014. Nie jest ono, niestety, najfajniejsze z całego zestawu, bo tego najfajniejszego jakoś nie umiem. Ale i tak będzie zabawnie.

Może darujemy sobie szczegóły historyjki z treści i sformułujemy problem w następujący sposób: chcemy jak najszybciej wykryć, który ze zbioru N przedmiotów jest specjalny. Wiemy, że jest taki dokładnie jeden. W kolejnych krokach wybieramy dowolny podzbiór i wykonujemy na nim test. Po A sekundach dowiadujemy się, czy nasz podzbiór zawierał specjalny przedmiot. Jeśli nie, możemy od razu wykonać kolejny test. Jeśli tak, przed wykonaniem kolejnego testu musimy poczekać jeszcze dodatkowe B-A sekund (autor obiecuje, że A\leq B). Naszym celem jest skonstruowanie strategii, która zminimalizuje sumaryczny czas potrzebny na znalezienie specjalnego przedmiotu. Zauważmy, że kończymy całą zabawę tak szybko, jak tylko zlokalizujemy szukamy przedmiot, więc jeśli stało się tak tuż po wykonaniu testu na podzbiorze zawierającym specjalny przedmiot, nie trzeba odczekać dodatkowych B-A sekund. Zauważmy też, że interesuje nas minimalizowanie sumarycznego czasu w najgorszym możliwym przypadku, czyli można sobie myśleć, że gramy z wyjątkowo złośliwym adwersarzem, który zawsze tak dobierze wynik testu, aby zmaksymalizować czas całej zabawy. Adwersarz, choć złośliwy, jest jednocześnie bezwzględnie uczciwy.

Limity są raczej konkretne: zarówno w wersji easy i jak i hard N \leq 10^{15}. Zajmijmy się najpierw wersją easy, w której B\leq 100.

Łatwo skonstruować strategię, która gwarantuje czas \leq \left\lceil\log_2n\right\rceil B. Wystarczy bowiem zastosować wyszukiwanie binarne: wybieramy podzbiór o mocy \frac{N}{2}, wykonujemy na nim test, i po co najwyżej B sekundach wyrzucamy ze zbioru \frac{N}{2} elementów. Taka strategia niekoniecznie jest super mądra, bo (być może) A jest istotnie mniejsze niż B. Jest jednak optymalna, gdy A=B. Co nawet lepsze, pokazuje, że nigdy nie potrzeba więcej niż 5000 sekund. No i.. co?

No i to, że możemy teraz odwrócić problem. Zamiast dla ustalonego N wyznaczać najlepszą strategię, dla każdego T można wyliczyć największe N, nazwijmy je N[T], dla którego istnieje strategia gwarantująca znalezienie specjalnego przedmiotu po T krokach. Mając wyznaczone wszystkie takie N[T] trzeba znaleźć najmniejsze T, dla którego N[T]\geq T. Powyższe rozumowanie gwarantuje nam, że interesują nas tylko T\leq 5000, czyli wystarczy pokazać, jak sprawnie wyliczyć N[0],N[1],\ldots,N[5000].

Okazuje się, że można napisać dość prostą rekurencję, która pozwoli na wyliczenie każdego N[T] w czasie stałym. Jeśli bowiem T<A, nie możemy absolutnie nic zrobić, co oznacza, że N[T]=1. Jeśli zaś T\geq A, możemy wykonać test na, powiedzmy, podzbiorze o mocy n. Jeśli specjalny przedmiot nie znajduje się w tym podzbiorze, zostanie nam jeszcze T-A sekund na znalezienie go wśród pozostałych N-n. Jeśli zaś specjalny przedmiot znajduje się w wybranym podzbiorze, mamy T-B sekund na znalezienie go wśród n przedmiotów. Tutaj trzeba trochę uważać: jeśli T<B, mamy do dyspozycji ujemną liczbę sekund, co może wydać się nieco dziwne. Wystarczy jednak zdefiniować N[T]=1 dla wszystkich ujemnych T. Co dalej? Wiemy, że mając do dyspozycji T-A sekund możemy znaleźć specjalny przedmiot wśród N[T-A] przedmiotów, a mając T-B wśród N[T-B]. Z tego wynika, że najlepiej wybrać n=N[T-B] i N-n=N[T-A], to znaczy na pewno nie da się lepiej. Z drugiej strony, możemy skonstruować strategię właśnie z takimi parametrami, i niezależnie od odpowiedzi złośliwego adwersarza znaleźć specjalny przedmiot po co najwyżej T sekundach. Czyli N[T]=N[T-A]+N[T-B].

To kończy wersję easy: wyliczamy kolejne N[T] aż do co najwyżej N[5000]. Przejdźmy więc do wersji hard, w której B\leq 10^{12}.

Nooo, tutaj jest już konkretnie. Powyższe rozumowanie staje się całkowicie bezużyteczne. Choć z drugiej strony, mamy bardzo prostą rekurencję opisująca kolejne N[T]. Szukane T być może jest bardzo duże, ale przecież możemy zastosować wyszukiwanie binarne. Czyli wystarczy zająć się wyliczeniem konkretnego N[T].

W tym momencie przydatne będzie trochę inne spojrzenie na równanie N[T]=N[T-A]+N[T-B]. Rozważamy bardzo prosta jednoosobową grę, w której zaczynamy z x=T. W jednym kroku mamy dwa możliwe ruchu: zmniejszenie x o A, oraz zmniejszenie x o B (nawet jeśli A=B, są to dwa różne ruchy!). Kończymy zabawę gdy tylko x<A. Czyli jeśli w całej rozgrywce wykonaliśmy a ruchów pierwszego typu, i b ruchów drugiego typu, to aA+bB > T-A. Podzielmy wszystkie rozgrywki na dwie kategorie w zależności od typu ostatniego ruchu. Sytuacja jest tutaj w miarę symetryczna, zajmijmy się więc policzeniem tych pierwszych, wtedy (skoro ostatni ruch był pierwszego typu) aA+bB\leq T. Łatwo zobaczyć, że każda para (a,b) taka, że a \geq 1, b \geq 0 oraz aA+bB\in (T-A,T] odpowiada dokładnie a+b-1 \choose a-1 rozgrywkom, gdyż możemy w dowolny sposób ustalić, które z pierwszych a+b-1 początkowych ruchów są pierwszego typu. Udało nam się zredukować cały problem do zliczania rozwiązań pewnego równania.

Dla wygody powiedzmy, że interesuje nas zliczenie sum wag par (a,b), dla których a,b\geq 0, aA+bB\in [f,t], przy czym waga pary (a,b) to po prostu a+b \choose b. Jak można by się za to zabrać? Chyba najprotszy pomysł to wygenerowanie wszystkich par (a,b), dla których aA+bB\in [f,t]. W jaki sposób? Na przykład można rozważać kolejne a=0,1,2,3,\ldots i wyliczyć dla takiego konkretnego a zakres „dobrych” wartości b. Są jednak przynajmniej dwa problemy. Ten zakres często może być pusty, i nie widać prostego sposobu na przeskoczenie takich wartości a. A w dodatku maksymalne a może być całkiem spore. (OK, być może jest to tylko jeden problem; zależy jak liczyć.)

Na szczęście można dość łatwo obejść wspomniany kłopot. Przypomnijmy bowiem, że dokładny wynik interesuje nas tylko wtedy, gdy nie przekracza N. Gdy tylko znajdziemy więc parę (a,b), dla której aA+bB\in [f,t] oraz \binom{a+b}{b} > N, możemy darować sobie dalsze rozważania. Teraz zauważmy jeszcze, że zawsze t-f+1 \geq A, więc wystarczy nam para (a,b), dla której aA+bB \leq t. Mamy też następującą przydatną obserwację.

Obserwacja. Jeśli a,b\geq 26, to \binom{a+b}{b} > 10^{15}.

Oznacza ona, że jeśli tylko 26(A+B) \leq t, możemy zakończyć pracę (i zwrócić N). W przeciwnym przypadku jest o tyle fajnie, że zawsze a \leq 25 lub b \leq 25. Możemy więc przeiterować się po wszystkich a=0,1,2,\ldots,25 i dla każdego z nich przetworzyć wszystkie możliwe b. Następnie zaś przeiterować się po wszystkich b=0,1,2,\ldots,25 i dla każdego z nich przetworzyć wszystkie możliwe a.

Chwila! Przecież wtedy przetworzymy niektóre pary (a,b) dwa razy. No, niby tak, ale później możemy naprawić sytuację iterując się po wszystkich a=0,1,2,\ldots 25 i b=0,1,2,\ldots,25 odejmując ich wagi od wyniku jeśli aA+bB \in [f,t]. Jest więc OK i możemy jechać dalej.

Sytuacja wygląda teraz tak: mamy ustalone a, dla którego chcemy policzyć sumę \binom{a+b}{b} po wszystkich b\geq 0, dla których aA+bB \in [f,t]. Widać, że ten ostatni warunek można łatwo przekształcić na b\in [f',t']. Interesuje nas więc \sum_{x\in [f',t']} \binom{a+x}{x}.

Lemat. \sum_{x\in [f',t']} \binom{a+x}{x} = \binom{a+t'+1}{t'}-\binom{a+f'}{f'-1}.

Dowód. Wystarczy pokazać, że \sum_{x\in [0,y]} \binom{a+x}{x}=\binom{a+y+1}{y}. Dla y=0 jest to oczywiste. Załóżmy, że \sum_{x\in [0,y]} \binom{a+x}{x}=\binom{a+y+1}{y}. Wtedy \sum_{x\in [0,y+1]} \binom{a+x}{x} to z założenia indukcyjnego \binom{a+y+1}{y}+\binom{a+y+1}{y+1}=\binom{a+y+2}{y+1}, czyli tyle ile chcieliśmy.

Daje nam to prosty wzór na szukaną wartość. Jest jednak pewien problem: f' i t' mogą być całkiem spore. W tym momencie pojawiają się dwa problemy: \binom{a+t'+1}{t'} i \binom{a+f'}{f'-1} mogą być wręcz olbrzymie. Chciałoby się powiedzieć, że jeśli wartość któregoś z tych wyrażeń jest faktycznie duża, to (tak jak wcześniej) zwracamy N, ale przecież nie jest tak łatwo: różnica dwóch dużych liczb może być mała. Czyli każdą z nich trzeba wyznaczyć dokładnie, co może być dość czasochłonne. Wrócmy więc do pracy z \sum_{x\in [f',t']} \binom{a+x}{x}.

Równie dobrze, a może i nawet lepiej, można pracować z \sum_{x\in [f',t']} \binom{a+x}{a}. Jeśli a=0, policzenie sumy jest trywialne. Jeśli a=1, jest tylko odrobinę trudniejsze, gdyż trzeba zsumować f'+1,f'+2,\ldots,t'+1. A co jeśli a\geq 2? Wtedy k-ty wyraz naszej sumy to przynajmniej \binom{2+k}{2}=\frac{(k+2)(k+1)}{2}, czyli suma pierwszych i pierwszych wyrazów to przynajmniej \frac{i}{12}(2i^2+14i-9). Więc widać, że dla i \geq 200000 wynik na pewno przekroczy N. Oznacza to, że możemy naiwnie generować kolejne pary (a,b) i sprawdzać, czy aktualna suma jest ciągle poniżej N. Wtedy, w najgorszym możliwym przypadku, dla a=2 przetworzymy co najwyżej 200000 różnych b (dla większych a istotnie mniej), co w zupełności wystarcza, by w ciągu kilku sekund rozwiązać 200 zestawów testowych. Oczywiście można pójść krok dalej, i wyznaczyć jawny wzór na odpowiedź dla a=2, co w sumie nie jest przecież trudne. Ale pewnie lepiej minimalizować szansę na literówkę w kodzie.

Reklamy

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