Binarna rzeka

Jeszcze przed rozpoczęciem sezonu wakacyjnego proponuję chwilę relaksu przy zadaniu E z rundy 3 tegorocznej edycji Google Code Jam. Trochę ciężko przypisać je do konkretnej kategorii, ale to nawet lepiej!

Treść można znaleźć tutaj. Rozważamy sumę funkcji stałej f(x)=c, c\geq 0 i (być może wielu) funkcji schodkowych. Funkcja schodkowa poziomu \ell przyjmuje wartość 1 dla x=r+\alpha\cdot 2^{\ell+1},\ldots,r+2^\ell-1+\alpha\cdot 2^{\ell+1}, gdzie \alpha jest dowolną liczbą całkowitą, a r ustalonym przesunięciem. Dla pozostałych całkowitych x taka funkcja przyjmuje wartość 0, sytuacja wygląda więc tak jak poniżej.

rzeka

Teraz dostajemy „wycinek” funkcji, którą podejrzewamy o bycie taką sumą, w której poziomy wszystkich funkcji schodkowych należą do \{0,1,\ldots,d\} (zwróćmy uwagę na to, że w sumie może pojawić się wiele funkcji schodkowych tego samego poziomu, a nawet tego samego poziomu i z takim samym przesunięciem r). Naszym zadaniem jest wyznaczenie najmniejszej możliwej liczby funkcji schodkowych wchodzących w skład tej sumy lub stwierdzenie, że podejrzenie było jednak pozbawione podstaw. Autorzy gwarantują, że wycinek ma długość przynajmniej 2^{d+1}, ale nie większą niż 5000. Czyli to pierwsze jest pewnie kluczowe w rozwiązaniu, a to drugie jest jakąś wskazówką w kwestii docelowej złożoności.

Spróbujmy najpierw przyjrzeć się założeniu, że wycinek ma długość co najmniej 2^{d+1}. Zauważmy, że funkcja schodkowa poziomu \ell ma okres 2^{\ell+1}. Taki sam okres ma więc suma dowolnie wielu funkcji schodkowych poziomu \ell. W związku z tym suma funkcji schodkowych poziomów nie większych niż d ma okres 2^{d+1}. Czyli znając wartości takiej sumy na wycinku długości 2^{d+1} tak naprawdę znamy wszystkie jej wartości! Możemy więc zapisać tylko wartości w 0,1,2,\ldots,2^{d+1}-1 i całkiem zapomnieć o pozostałych (o ile są zgodne z tymi zachowanymi: być może już teraz jesteśmy w stanie stwierdzić oszustwo).

Mamy więc funkcję o okresie 2^{d+1}, którą chcemy „rozłożyć” na funkcje schodkowe poziomów 0,1,2\ldots,d. Naturalna wydaje się próba zredukowania problemu do mniejszego, czyli wyznaczenia funkcji schodkowych poziomu d, które muszą pojawić się w sumie, a następnie zredukowanie problemu do rozbicia funkcji o okresie 2^{d} na sumę funkcji schodkowych poziomów 0,1,2,\ldots,d-1. Ale jak?

Problematyczne jest przede wszystkim to, że jeszcze nie wiemczy czy te funkcje schodkowe poziomu d są jednoznacznie wyznaczone (a jeśli nie są, to cały pomysł jest pewnie bez sensu). Oznaczmy przez a(0),a(1),\ldots,a(2^{d+1}) wartości oryginalnej funkcji. Niech b(x) będzie liczbą funkcji poziomu d z przesunięciem x wchodzących w skład całej sumy, wtedy wartość w x jest zwiększana przez te funkcje o b'(x)=b(x)+b(x-1)+\ldots+b(x-2^d+1), gdzie zawijamy indeksy modulo 2^{d+1}. Naszym wymarzonym celem jest jednoznaczne wyznaczenie wszystkich b(x).

Zauważmy, że skoro suma funkcji poziomów nie większych niż d-1 ma okres 2^d, to funkcja a(x)-b'(x) musi mieć okres 2^d, czyli a(x)-b'(x)=a(x+2^d)-b'(x+2^d) dla każdego x=0,1,2,\ldots,2^d. Teraz przepiszmy ten warunek:

\begin{aligned} a(x)-b'(x)&= a(x+2^d)-b'(x+2^d) \\ a(x)-(b(x)+b(x-1)+\ldots+b(x-2^d+1))&= a(x+2^d)-(b(x+2^d)+b(x-2^d-1)+\ldots+b(x-2^{d+1}+1)) \end{aligned}.

Wygląda to dość nieciekawe. Ale… można zauważyć, że równości dla x oraz x+1 są do siebie dość podobne. Więc może dobrym pomysłem na uproszczenie byłoby odjęcie ich od siebie?

\begin{aligned} a(x)-(b(x)+b(x-1)+\ldots+b(x-2^d+1))&= a(x+2^d)-(b(x+2^d)+b(x-2^d-1)+\ldots+b(x-2^{d+1}+1)) \\ a(x+1)-(b(x+1)+b(x)+\ldots+b(x-2^d+2))&= a(x+2^d+1)-(b(x+2^d+1)+b(x-2^d)+\ldots+b(x-2^{d+1}+2)) \\ a(x)-a(x+1)+b(x+1)-b(x-2^d+1) &= a(x+2^d)-a(x+2^d+1)+b(x+2^d+1)-b(x-2^{d+1}+1) \\ \end{aligned}.

Teraz korzystając z tego, że b(x)=b(x+2^{d+1}) dostajemy:

2(b(x+1)-b(x+2^d+1))= a(x+2^d)+a(x+1)-a(x)-a(x+2^d+1).

Prawa strona równości jest znana. Jeśli dla pewnego x jest ona nieparzysta, wykryliśmy oszustwo (bo z pewnością nie da się odpowiednio dobrać wszystkich b(x)). W przeciwnym wypadku znamy różnicę b(x)-b(x+2^d) dla każdego x=0,1,2,\ldots,2^d-1.

Dobrze, ale my chcemy wyliczyć te wszystkie b(x) oraz b(x+2^d) dla x=0,1,2,\ldots,2^d-1. Nie bardzo widać jak z powyższych równości wycisnąć więcej informacji, na szczęście okazuje się, że nie jest to konieczne. Bez straty ogólności możemy bowiem założyć, że b(x)=0 lub b(x+2^d)=0. Jeśli bowiem jest inaczej, czyli b(x)\geq 1 oraz b(x+2^d)\geq 1 dla jakiegoś x, to tak naprawdę możemy zmniejszyć b(x) oraz b(x+2^d) o jeden oraz zwiększyć o jeden funkcję stałą wchodzącą w skład sumy. Równości pozwalają nam więc jednoznacznie wyznaczyć wszystkie b(0),b(1),\ldots,b(2^{d+1}-1) w następujący sposób. Oznaczmy

\Delta=a(x+2^d)+a(x+1)-a(x)-a(x+2^d+1).

Jeśli \Delta>0 wybieramy b(x)=\Delta/2 oraz b(x+2^d)=0, a jeśli \Delta<0 to b(x)=0 oraz b(x+2^d)=-\Delta/2.

Po wyliczeniu wszystkich b(x) należy zaktualizować a(0),a(1),\ldots,a(2^d-1) (już rozpatrzone równości gwarantują, że nie trzeba mysleć o a(2^d),a(2^d+1),\ldots,a(2^{d+1}-1)). Należy przy tym troszkę uważać na ujemne wartości: jeśli tylko takie się pojawią, znów wykryliśmy oszustwo. Następnie powtarzamy rozumowanie z mniejszym d. Prędzej lub później dojdziemy do d=0 i zakończymy pracę.

Pozostaje oszacować koszt całego rozwiązania. Dla każdego x=0,1,2\ldots,2^d-1 rozpatrujemy jedną równość, czyli wszystkie b(0),b(1),\ldots,b(2^d-1) można wyliczyć w sumarycznym czasie \mathcal{O}(2^d). Trochę gorzej z aktualizacją a(0),a(1),\ldots,a(2^d-1). Podejście naiwne wymagałoby pewnie czasu \mathcal{O}((2^d)^2), gdyż każda z nowych wartości zależy od 2^d wartości b(x), łatwo jednak zauważyć, że akumulując odpowiednie sumy można ją zmniejszyć również do \mathcal{O}(2^d). Dodając po wszystkich d dostajemy, że całe rozwiązanie działa w czasie liniowym.

Advertisements

3 myśli nt. „Binarna rzeka

    • Kusilo mnie, zeby napisac ze zadanie kojarzy mi sie z FFT, ale jest to na tyle metne skojarzenie, ze balem sie kompromitacji ^^ Tego Hadamarda nie znalem, dzieki. 22 cze 2015 09:49 „Fajne zadania” napisał(a):

      >

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