Czy ktos moze wyjasnic jak sie robilo 3 kule?

Przyłączam się do prośby.

Ja do tego tak podszedłem:
Wszystko da się sprowadzić z zasady włączeń i wyłączeń do problemu wyznacz przecięcie trzech hiperkul.
Mamy 3 maski bitowe, chcemy policzyć ile jest takich masek bitowych które dla każdej z tych trzech danych nie są oddalone o nich o więcej niż pewne r_i dla maski, gdzie odległość między maskami a oraz b była określona jako ilość zapalonych bitów maski (a xor b).

Można najpierw zacząć od zxorowania naszych trzech masek z pierwszą, przez co pierwsza maska jest samymi zerami (można tak zrobić, bo xor to przesunięcie o pewien wektor). Teraz, liczę ile jest takich pozycji że (drugą maskę oznaczę przez m2, trzecią przez m3, zakładam że m1[i] = 0), m2[i] = 0, m3[i] = 0 - niech ta ilość to będzie A, odpowiednio dalej B to ilość pozycji, że m2[i] = 0, m3[i] = 1, C, że m2[i] = 1, m3[i] = 0, D, że m2[i] = 1, m3[i] = 1. Teraz można skonstruować pewien układ nierówności, które są spełniane przez każdą maskę w przecięciu.

No więc weźmy pewną maskę należącą do przecięcia. Niech [mała literka] oznacza ile wybraliśmy jedynek na pozycjach [duża literka], czyli np a to ilość jedynek, na takich pozycjach, że m2[i] = m3[i] = 0. Mamy pierwsze nierówności
0 <= a <= A, 0 <= b <= B, 0 <= c <= C, 0 <= d <= D

Teraz zobaczmy jakie ograniczenia generują nam promienie (r1, r2, r3) hiperkul
a+b+c+d <= r1, bo zawsze m1[i] = 1
a+b+(C - c) + (D - d) <= r2, bo w m2 jedynki są na pozycjach typu C i D
a+(B - b) + (C - c) + d <= r3, bo w m3 jedynki są na pozycjach typu B i D
Dla każdego rozwiązania tego równania, do wyniku trzeba było dodać (A po a) * (B po b) * (C po c) * (D po d), bo ze zbioru pozycji wybieramy miejsca gdzie postawimy jedynki.

Rozwiązywałem ten układ nierówności w ten sposób: iteruję się po c i d, wtedy dostawałem układ nierówności w postaci
0<=a<=A, 0<=b<=B, a+b<=s1, a-b<=s2 gdzie s1 oraz s2 to pewne współczynniki wyliczone z wcześniejszego układu. Ten układ dało się rozwiązać geometrycznie.

O(n^2) można było zrobić preprocessing po pewnych sumach (A po i) * (B po j), żeby liczyć potem w czasie stałym dla jakiegoś c i d móc policzyć sumę tych wyrazów na trójkątach, więc złożoność całkowita to też O(n^2)

Możliwe, że przekombinowałem, ale 10pkt jest :>

Dzięki za tak szczegółowy opis. Ja doszedłem tylko do tego miejsca, że można podzielić na A i B, co wystarczało na rozwiązanie tylko 2 kul.

A wiecie, że dopełnienie kuli też jest kulą? Ktoś widzi, co to ułatwia w zadaniu?

@Michał
Ja tak samo nawet nazwałem u siebie A,B,C i D - ale nie preprocesuję sum na trójkątach, tylko tak:
Też iteruję dla każdego `c` i `d`, ale potem jak zostaje mi `a` i `b` do ustalenia, to pierwsze 2 kule mają na tych pozostałych bitach te same wartości, czyli problem (dla już ustalonego `c` i `d`, wewnątrz pojedynczej iteracji) redukuje nam się do przecięcia już tylko 2 kul w mniejszej przestrzeni A+B wymiarowej. W każdej iteracji jak ustalimy `c` i `d`, to oddalają one nas od wejściowych 3 kul o pewną odległość, więc te kule ze zredukowanego problemu musimy rozwiązać dla mniejszych promieni (pomniejszonych o te odległości, które już przebyliśmy). No i w każdej iteracji będą nam się zmieniały tylko promienie tych pozostałych 2 kul, więc dla każdej możliwej pary promieni mamy spreprocessowany wynik.

Prawie to samo, ale jakoś cieplej człowiek myśli o kulach niż o układzie nierówności.

@Kamil
wow, faktycznie, a ja też zasadę włączeń i wyłączeń robiłem :D

> A wiecie, że dopełnienie kuli też jest kulą? Ktoś widzi, co to ułatwia w zadaniu?

Też to zauważyłem, a nawet to że suma kul jest dopełnieniem przecięcia dopełnień (można było liczyć przecięcie zamiast sumy).

Osobiście próbowałem podejść do rozwiązania od "środka", tzn. od punktu który leży na najkrótszych drogach pomiędzy wszystkimi trzema kulami. Każdy układ można było sprowadzić do 7 liczb: liczba wymiarów, 3 promienie i 3 odległości od środka. Ale zadania nie rozwiązałem.