Xor

Nie wiem jak Wam, ale mi w zawodach organizowanych przez Rosjan bardzo podoba się to, że zwykle nie czują oni specjalnej potrzeby, żeby wymyślać długie bajeczki. Często można tam spotkać zadania, które mimo treści mieszczącej się w ledwie kilku linijkach potrafią dostarczyć rozrywki na długie godziny. Może nie było tego za bardzo widać w przypadku zadania o Moskiewskim metrze, ale proponuję popatrzeć na problem I z tego zestawu. Jeśli nie macie i nie chcecie mieć konta na codeforces, pytanie jest następujące: dla danego ciągu n liczb 1 \leq a_1,a_2,\ldots,a_n \leq 10^{18}, ile jest x \in [0,\min_i a_i) takich, że xor wszystkich a_i - x jest zerem? Proste, prawda?…

No, a może nie takie proste. Pewnie warto wspomnieć, że w oryginalnej treści tak naprawdę mowa o zliczaniu x, dla których pierwszy gracz może zapewnić sobie zwycięstwo w grze Nim na planszy a_1-x,a_2-x,\ldots,a_3-x. No ale, każdy, kto choć przez chwilę interesował się teorią gier, pewnie wie, że jest tak dokładnie wtedy, gdy wszystkie a_i-x xorują (na pewno jest na to jakieś ładne polskie słowo…?) się do zera.

Dość naturalne jest popatrzenie, jak zmieniają się bity na poszczególnych pozycjach wszystkich a_i-x. W końcu licząc xor operujemy na każdej z tych pozycji z osobna. Zacznijmy od bitów na najmniej znaczących pozycjach, czyli po prostu parzystości. Chcemy, żeby \sum_i a_i -x = 0 \bmod 2, czyli tak naprawdę nx=\sum_i a_i \bmod 2. A więc jeśli n jest nieparzyste, znamy już ostatni bit x! Teraz wystarczy tylko powtórzyć całe rozumowanie dla wszystkich pozycji.

No, albo i nie wystarczy. Sytuacja dla bitów na wyższych pozycjach wygląda trochę gorzej: to, czy a_i-x ma zapalony bit na k-tej pozycji zależy nie tylko od k-tego bitu a_i oraz x, ale (ze względu na możliwe przeniesienia) tak naprawdę od wszystkich bitów na pozycjach k,k-1,\ldots,0! Czyli jest źle. Ale nie tragicznie: zależność ta nie jest bowiem szczególnie skomplikowana. Powiedzmy, że a_i = .. y_k y_{k-1} \ldots y_0. Tak długo, jak x\bmod 2^{k+1} \leq a_i\bmod 2^{k}, k-ty bit a_i - x to dokładnie y_k. Dla kolejnych 2^{k} wartości x\bmod 2^{k+1}, czyli a_i\bmod 2^{k} < x\bmod 2^{k+1} \leq 2^{k}+a_i\bmod 2^{k}, k-ty bit zmienia się na przeciwny. A następnie… dla wszystkich 2^{k}+a_i\bmod 2^{k}<x\bmod 2^{k+1} znów wracamy do oryginalnej wartości y_k. Czyli udało się nam wyznaczyć k-ty bit a_i-x w zależności od wartości x\bmod 2^{k+1}:

  1. dla [0,a_i\bmod 2^{k}+1) jest to y_k,
  2. dla [a_i\bmod 2^{k}+1,a_i\bmod 2^{k}+2^{k}+1) jest to 1-y_k,
  3. dla [a_i\bmod 2^{k}+2^{k}+1,2^{k+1}) jest to znów y_k.

Dla każdego a_i dostajemy więc podział [0,2^{k+1}) na trzy przedziały, na których k-ty bit a_i-x ma ustaloną wartość. Teraz wystarczy tylko wyobrazić sobie (jednocześnie) wszystkie przedziały utworzone dla różnych i i zauważyć, że tak naprawdę daje nam to podział [0,2^{k+1}) na nie więcej niż 2n+1 rozłącznych kawałków, na których k-ty bit \oplus_i a_i-x ma taką samą ustaloną wartość. Znalezienie tego podziału wymaga tylko posortowania i przejrzenia w kolejności od lewej do prawej wszystkich a_i\bmod 2^{k}, po czym możemy usunąć przedziały, na których rzeczony bit jest niezerowy. Czasami może się zdarzyć, że w naszym podziale zostały dwa przedziały postaci [x,y) i [y,z), a więc równie dobrze moglibyśmy zamienić je na [x,z). Nie będziemy jednak tego robić, i to wcale nie dlatego, że jesteśmy leniwi. Po prostu przyda nam się, że każde a_i\bmod 2^{k}+1 i a_i\bmod 2^{k}+2^{k}+1 jest początkiem lub końcem jakiegoś przedziału, czyli tak naprawdę początki i końce przedziałów to dokładnie 0, 2^{k+1}, i wszystkie a_i\bmod 2^{k}+1 oraz a_i\bmod 2^{k}+2^{k}+1.

Pięknie. Dla każdego k skonstruowaliśmy więc (niewielki) zbiór przedziałów \mathcal{A}_k, który opisuje kdobre wartości x\bmod 2^{k+1}. Czyli teraz wypadałoby tylko połączyć ze sobą te wszystkie warunki.

No, albo i nie wypadałoby. Co prawda dla każdego k mamy tylko 2n+1 przedziałów, jednak jeśli popatrzymy się na te wartości x\bmod 2^{k+1}, które są jednocześnie 0-, 1-, …, i k-dobre, ich zbiór przedziałów może zawierać nawet wykładniczo wiele elementów! Wynika to stąd, że (na przykład) chcąc wyznaczyć wartości, którą są jednocześnie k– i k+1-dobre, wypadałoby zduplikować \mathcal{A}_k, a dokładniej przesunąć o 2^{k+1} każdy X\in \mathcal{A}_k tworząc w ten sposób X'\in\mathcal{A}'_k, i przeciąć \mathcal{A}_k\cup\mathcal{A}'_k z \mathcal{A}_{k+1} tak jak na poniższym rysunku. Może się zdarzyć, że takie dokładanie warunków odpowiadających kolejnym bitom będzie powodować wykładnicze puchnięcie wynikowego zbioru przedziałów. Czyli raczej lipa.

xor

No, a może i nie lipa: w końcu nikt nie każe nam rzeczywiście konstruować tych wszystkich przedziałów. Tak naprawdę interesuje nas tylko zliczanie rozwiązań, więc może wystarczyłoby dla każdego z X\in\mathcal{A}_k pamiętać, ile z mieszących się tam liczb jest także k-1-, …, 0-dobrych? Popatrzmy jeszcze raz na operację przedstawioną na powyższym rysunku. Czy wiedza o tym, ile liczb znajduje się w każdym z przedziałów z \mathcal{A}_k, na pewno wystarczy nam na określenie ile liczb znajduje się w nowych przedziałach z \mathcal{A}_{k+1}? Moglibyśmy mieć pewien problem, gdyby jeden ze „starych” przedziałów był tylko częściowo zawarty w jednym z tych „nowych”. Na szczęście nie może się tak zdarzyć.

Lemat Jeśli X\in \mathcal{A}_k\cup\mathcal{A}'_k i Y\in\mathcal{A}_{k+1}, to X\subseteq Y lub X\cap Y=\emptyset.

Dowód. Przypomnijmy, że początki i końce przedziałów w \mathcal{A}_{k+1} to 0, 2^{k+2}, i a_i\bmod 2^{k+1}+1 oraz a_i\bmod 2^{k+1}+2^{k+1}+1. Teraz zauważmy, że:

  1. a_i\bmod 2^{k+1}+1 to a_i\bmod 2^k+1 lub a_i\bmod 2^k + 2^k+1, a wszystkie liczby tej postaci są początkami lub końcami przedziałów z \mathcal{A}_k,
  2. a_i\bmod 2^{k+1}+2^{k+1}+1 to a_i\bmod 2^k+2^{k+1}+1 lub a_i\bmod 2^k+2^{k+1}+2^k+1, a wszystkie liczby tej postaci są początkami lub końcami przedziałów z \mathcal{A}'_k.

Czyli w końcu widać, dlaczego nie sklejaliśmy ze sobą sąsiednich przedziałów! Dzięki temu każdy początek/koniec przedziału z \mathcal{A}_{k+1} jest początkiem lub końcem przedziału z \mathcal{A}_k\cup\mathcal{A}'_k, co tak naprawdę kończy dowód lematu.

No i świetnie. Wyznaczenie liczby rozwiązań w każdym z k-dobrych przedziałów może być dość łatwo wykonane za pomocą jednego przejścia od lewej do prawej (jednocześnie po \mathcal{A}_k i \mathcal{A}_{k-1}\cup\mathcal{A}'_{k-1}). To wymaga zaś tylko posortowania ich końców, czyli złożoność całego rozwiązania to \mathcal{O}(n\log n\log M), gdzie M=\max_i a_i. Ale co właściwie jest odpowiedzią? Po chwili zastanowienia można dojść do wniosku, że można ją odczytać patrząc na najlewszy przedział w ostatnim \mathcal{A}_k. A dokładniej, ten przedział to dokładnie [0,\min_i a_i], czyli po prostu wypisujemy wyznaczoną liczbę zawartych w nim rozwiązań (jeśli \min_i a_i jest prawidłowym rozwiązaniem, pomniejszoną o jeden). I tyle.

No, a może i nie tyle. Okazuje się bowiem, że powyższe rozwiązanie jest woooolne: sortowanie 60 zestawów złożonych z 200000 liczb jednak trochę trwa. Jednak czy rzeczywiście musimy sortować? Za każdym razem porządkujemy zbiór liczb postaci a_i\bmod 2^k. Czyli można by o tym próbować myśleć w następujący sposób: mając już posortowane liczby postaci a_i\bmod 2^k, odsłaniamy kolejny bit każdej z nich tak, aby dostać liczby postaci a_i\bmod 2^{k+1}. Jak zmieni się ich kolejnośc po posortowaniu? Bardzo prosto! a_i z jedynką na kolejnej pozycji przeskoczą a_i, które mają tam zero. Czyli tak naprawdę można dość łatwo naprawić porządek za pomocą jednego przejścia po liście, co daje nam całkowity czas działania \mathcal{O}(n\log M) i teraz to już naprawdę koniec 🙂

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