Gra w kulki

Po krótkiej przerwie wracamy do gry! A konkretniej, do gry w kulki, która pojawiła się na ostatnich Akademickich Mistrzostwach Polski w Programowaniu Zespołowym. Jak w każdej porządnej grze, także i w tej kluczem do zwycięstwa okaże się odrobina teorii liczb i sprytny sposób na ograniczenie przestrzeni interesujących rozwiązań.

Treść można zobaczyć tutaj, ale równie dobrze można skoncentrować się na jej skróconej wersji, która brzmi tak: dla podanych k_0,k_1,\ldots,k_9 \in [0,10^{15}] chcemy sprawdzić, czy można podzielić multizbiór k_0 zer, k_1 jedynek, k_2 dwójek, … , k_9 dziewiątek na dwie równoliczne części tak, aby iloczyn elementów w obu (multi)zbiorach był taki sam. Na przykład \{1,3,4,6,8,9\} można podzielić na \{3,4,6\} i \{1,8,9\}. Oczywiście zakładamy, że \sum_i k_i jest parzyste. Inaczej byłoby przecież nudno.

Patrząc na treść, lekko podejrzany jest dość wysoki limit na wszystkie k_i. Ciężko dopasować go do jakiejkolwiek złożoności, co może oznaczać, że jedynym powodem jego istnienia jest umożliwienie wykonania wszystkich obliczeń używając zmiennych typu long long.

Załóżmy, że (jak nigdy) mieliśmy szczęście, i wszystkie k_i są parzyste. Wtedy podział na dwie części nie przysparza żadnego kłopotu. No to teraz wyobraźmy sobie, że niektóre k_i są nieparzyste. W zasadzie od razu możemy zapomnieć o k_0, gdyż jeśli k_0 \geq 2 możemy bez problemu utworzyć dwie części o iloczynie równym zero, jeśli zaś k_0 = 1 nijak nie unikniemy sytuacji, w której jedna z części ma iloczyn równy zero, a druga niezbyt. No i fajnie, ale co z pozostałymi k_i? Od razu widać, że jeśli nieparzyste jest k_5 lub k_7, to nigdy nie uda nam się skonstruować części o równych iloczynach. Jeśli zaś k_5 i k_7 są parzyste, nie bardzo mamy jakikolwiek wybór w kwestii rozdzielenia tych piątek i siódemek: w każdej z dwóch części musi się ich znaleźć tyle samo (tutaj skorzystaliśmy już z tego, że k_0=0). Od tego momentu możemy więc całkiem zapomnieć również o k_5 i k_7.

Mamy więc k_1 jedynek, k_2 dwójek, k_3 trójek, k_4 czwórek, k_6 szóstek, k_8 ósemek, i k_9 dziewiątek. No i co? No i tak naprawdę chcemy rozwiązać następujący układ równań:

\begin{array}{rcl}k'_1+k'_2+k'_3+k'_4+k'_6+k'_8+k'_9&=&(k_1-k'_1)+(k_2-k'_2)+(k_3-k'_3)+(k_4-k'_4)+(k_6-k'_6)+(k_8-k'_8)+(k_9-k')\\k'_2+2k'_4+k'_6+3k'_8&=&(k-k'_2)+2(k_4-k'_4)+(k_6-k'_6)+3(k_8-k'_8)\\k'_3+k'_6+2k'_9&=&(k-k'_3)+(k_6-k'_6)+2(k_9-k'_9)\end{array}

gdzie k'_1\in [0,k_1], k'_2\in [0,k_2], k'_3\in[0,k_3], k'_6\in[0,k_6], k'_8\in[0,k_8] i k'_9\in[0,k_9]. Pierwsze równanie mówi, że interesuje nas podział na dwie równe części. Drugie wymusza, że otrzymane części są podzielne przez taką samą potęgę 2, natomiast trzecie gwarantuje, że są one podzielne przez taką samą potęgę 3. Ponieważ 2 i 3 to jedyne liczby pierwsze, które mogą pojawić się w rozkładzie otrzymanych iloczynów, gwarantuje to ich równość.

Skoro dla parzystych k_i patrzymy na rozwiązanie, w którym k'_i=k_i-k'_i, pewnie wygodniej jest wprowadzić nowe zmienne \delta_i=k'_i-(k_i-k'_i)=2k'_i-k_i. Wtedy takie rozwiązanie po prostu wybiera \delta_i=0. Teraz intuicja jest następująca: nawet jeśli niektóre (lub wszystkie) k_i są nieparzyste, sensowne wydaje się podzielenie każdego z nich na mniej więcej dwie równe części, czyli ograniczenie się do małych (co do wartości bezwzględnej) \delta_i. Ta intuicja jak na razie nie ma oczywiście żadnego podparcia.

Wróćmy do układu równań. Szukamy \delta_2, \delta_3, \delta_6, \delta_8, \delta_9 takich, że:

\begin{array}{llllllllllllllcl}\delta_1&+&\delta_2&+&\delta_3&+&\delta_4&+&\delta_6&+&\delta_8&+&\delta_9&=&0\\  &&\delta_2& & &+&2\delta_4&+&\delta_6&+&3\delta_8& & &=&0\\  && & &\delta_3& & &+&\delta_6& & &+&2\delta_9&=&0\\  \end{array}

a ponadto \delta_i odpowiadają poprawnym k'_i\in[0,k_i], czyli k_i+\delta_i jest parzyste oraz \delta_i\in[-k_i,k_i]. Teraz wróćmy do intuicji. Zapomnijmy na chwilę o ograniczeniach \delta_i\in[-k_i,k_i]. Wtedy cały układ równań (włącznie z warunkiem, że każde \delta_i ma określoną parzystość) ma wyjątkowo prostą strukturę: wszystkie pojawiające się w nim stałe są wręcz mizerne. Okazuje się, że wynika stąd, że jedno z jego rozwiązań (jeśli jakieś istnieje) przyporządkowuje wszystkim niewiadomym równie niewielkie wartości.

Twierdzenie. Jeśli \delta_1,\delta_2,\delta_3,\delta_4,\delta_6,\delta_8,\delta_9 są prawidłowym rozwiązaniem powyższego układu równań, lecz wartość bezwzględna choć jednej z tych liczb przekracza 98, istnieją \delta'_1,\delta'_2,\delta'_3,\delta'_4,\delta'_6,\delta'_8,\delta'_9, które także są prawidłowym rozwiązaniem, dla każdego i mamy, że \delta_i-\delta'_i jest parzyste i |\delta'_i| \leq |\delta_i|, oraz dodatkowo \sum_i |\delta'_i| < \sum_i |\delta_i|.

Dowód powyższego twierdzenia chwilę nam zajmie, zauważmy więc najpierw, że od razu wynika z niego szybki algorytm dla całego zadania. Wystarczy bowiem po prostu brutalnie przejrzeć wszystkie rozwiązania, w których |\delta_i| \leq 666 dla wszystkich i. No, taka metoda jest może odrobinę zbyt brutalna, lepiej brutalnie przeglądać tylko \delta_6, \delta_8, \delta_9, a następnie na ich podstawie wyliczyć sobie \delta_2, \delta_3, \delta_4.

Zanim zabierzemy się za dowód, warto spojrzeć na powyższy układ równań w trochę inny sposób. Możemy mianowicie zdefiniować sobie wektory v_2,v_3,v_4,v_6,v_8,v_9 odpowiadające jego kolumnom, czyli v_1=[1,0,0], v_2=[1,1,0], v_3=[1,0,1], v_4=[1,2,0], v_6=[1,1,1], v_8=[1,3,0], v_9=[1,0,2] i rozważać tylko jedno równanie \sum_i \delta_i v_i = 0. Zero po prawej stronie to tak naprawdę [0,0,0].

Załóżmy, że \sum_i \delta_i v_i = 0 i przyjrzyjmy się tym \delta_i, które są bardzo małe lub bardzo duże. Oczywiście może być tak, że są takie tylko niektóre z nich, ale zacznijmy od prostszego przypadku, w którym |\delta_i| > 12 dla każdego i. W takiej sytuacji chcielibyśmy pokazać, że można zwiększyć o 2x_i te \delta_i, które są mniejsze niż -12, oraz zmniejszyć o 2x_i te \delta_i, które są większe niż 12. Te wszystkie zmiany muszą się zerować, czyli chcielibyśmy, aby \sum_i x_i u_i = 0, gdzie u_i=v_i jeśli \delta_i < -12 i u_i=-v_i gdy \delta_i > 12, ale jednocześnie muszą być na tyle małe, aby nie nastąpiła zmiana znaku żadnego \delta_i, a wartość bezwzględna przynajmniej jednego z nich zmalała, czyli x_i\in [0,1,\ldots,6] dla każdego i oraz x_i > 0 dla jakiegoś i. Jedynym kłopotliwym warunkiem jest tutaj wymaganie, że x_i są niewielkie, łatwo bowiem skonstruować rozwiązanie, które jest nieujemne i niezerowe: wystarczy tylko wybrać x_i=2|\delta_i|. Wystarczyłoby więc tylko pokazać, że jeśli \sum_i x_i u_i = 0 ma nieujemnie i niezerowe rozwiązanie, to tak naprawdę ma nieujemne i niezerowe rozwiązanie, które w dodatku jest niewielkie. Okazuje się, że faktycznie tak jest.

Lemat. Jeśli u_1,u_2,\ldots,u_k\subseteq\{v_1,_2,\ldots,v_9,-v_1,-v_2,\ldots,-v_9\} jest zbiorem wektorów, dla którego równanie \sum_i x_i u_i=0 ma niezerowe rozwiązanie, w którym wszystkie x_i są nieujemne, to istnieje takie niezerowe rozwiązanie, w którym dodatkowo x_i \in [0,1,\ldots,6] dla wszystkich i.

Dowód. Weźmy jakieś poprawne rozwiązanie. Nie ma sensu rozważać sytuacji, w której w zbiorze wektorów mamy zarówno jakieś v_i, jak i -v_i. Ponadto bez straty ogólności możemy założyć (wyrzucając niepotrzebne wektory), że x_i > 0 dla każdego i, czyli możemy przekształcić \sum_i x_i u_i=0 otrzymując \sum_{i<k} \frac{x_i}{x_k} u_i=-u_k, więc -u_k należy do przestrzeni rozpiętej przez u_1,\ldots,u_{k-1}. Załóżmy na chwilę, że k=4 i u_1,u_2,u_3 są liniowo niezależne.

W takiej sytuacji mamy dokładnie jeden sposób na przedstawienie -u_1 jako kombinację liniową u_1,u_2,u_3. Tę unikalną reprezentację można łatwo znaleźć patrząc na y_1 u_1 + y_2 u_2 + y_3 u_3 = -u_4 i stosując wzory Cramera. Dostaniemy z nich, że y_i=\frac{p_i}{q}, gdzie q jest wyznacznikiem macierzy A utworzonej przez u_1, u_2, u_3, zaś każde p_i jest wyznacznikiem macierzy powstałej przez zastąpienie i-tej kolumny A przez -u_k. Teraz trzeba tylko zauważyć, że z unikalności reprezentacji i tego, że założyliśmy istnienie jakiegoś nieujemnego rozwiązania wynika, że nieujemnym całkowitym rozwiązaniem jest x_1=p_1\frac{|q|}{q}, x_2=p_2\frac{|q|}{q}, x_3=p_3\frac{|q|}{q}, x_4=|q|. Wystarczy więc tylko oszacować wszystkie p_i i q. Tak naprawdę interesuje nas więc największa możliwa wartość bezwzględna wyznacznika macierzy utworzonej przez wybranie 3 z możliwych wektorów. Bardzo łatwo przekonać się, że na przykład nie może ona przekroczyć 10^{\frac{3}{2}}, gdyż wyznacznik to nic innego jak objętość bryły rozpiętej przez wybrane wektory, a przecież wszystkie z nich mają długość co najwyżej \sqrt{10}. Tak naprawdę jest jednak dużo lepiej, i pisząc prosty brutalny program można sprawdzić, że największa możliwa wartość to 6.

A jak pozbyć się założenia? Żeby powyższe rozumowanie było poprawna potrzeba tylko, żeby u_1,u_2,\ldots,u_{k-1} były liniowo niezależne (wtedy automatycznie u_k jest ich kombinacją liniową). Powiedzmy więc, że zarówno u_{k-1} i u_k są kombinacją liniową u_1,u_2,\ldots,u_{k-2}. Wtedy oprócz nieujemnego i niezerowego rozwiązania x_1,\ldots,x_k istnieje też inne niezerowe (choć niekoniecznie nieujemne) rozwiązanie y_1,\ldots,y_k, które w dodatku nie powstaje przez przeskalowanie tego poprzedniego. Teraz należy zauważyć, że w takim razie dla dowolnego \alpha prawidłowym rozwiązaniem jest także ich kombinacja liniowa \alpha x_1+y_1,\ldots,\alpha x_k+y_k. Co nawet lepsze, zawsze można dobrać \alpha tak, aby wszystkie współczynniki tej kombinacji liniowej były nieujemne, przynajmniej jeden był równy zero, oraz nie wszystkie były równe zero. To zaś oznacza, że możemy wyrzucić jeden z wektorów zachowując istnienie nieujemnego rozwiązania. Powtarzając takie wyrzucanie prędzej lub później będziemy mogli zastosować powyższe rozumowanie.

No dobrze, jak na razie idzie nam wręcz świetnie. Wiemy już co zrobić, gdy |\delta_i|>12 dla wszystkich i, ale może się przecież zdarzyć, że jest tak tylko dla niektórych z nich. Tak naprawdę jest jednak trochę lepiej: powyższe rozumowanie równie dobrze działa, jeśli |\delta_i|>5 dla wszystkich i. Czemu? Bo tak naprawdę wcale nie zależy nam na tym, żeby uniknąć zmiany znaku \delta_i. Wystarczy nam gwarancja, że |\delta_i| nie wzrośnie. Na pewno tak będzie jeśli tylko x_i\in [0,\ldots,6] i |\delta_i|>5. Jeśli zaś w dodatku choć jedno x_i jest mniejsze niż 6, odpowiadające mu |\delta_i| zmaleje, czyli polepszymy wynik. Trzeba jeszcze zauważyć, że jeśli wszystkie x_i są równe 6, możemy podzielić je przez 6.

Nijak nie załatwia to jednak sytuacji, w której \delta_i>5 lub \delta_i<-5 tylko dla niektórych i. Może jednak wciąż dałoby się zastosować powyższy lemat? Poprzestawiajmy wektory tak, aby |\delta_i|>5 dokładnie dla i=1,2,\ldots,k. Jeśli teraz zdefiniujemy u_i tak jak wcześniej, ale zastosujemy lemat tylko do u_1,u_2,\ldots,u_k, pozwoli on nam na polepszenie aktualnej sytuacji jeśli tylko \sum_i x_i u_i = 0 ma jakiekolwiek nieujemne i niezerowe rozwiązanie (z tym polepszeniem trzeba trochę uważać: potrzebna jest znów obserwacja, że bez straty ogólności rozwiązanie zawiera choć jedną liczbę mniejszą niż 6). Czyli problem pojawia się tylko i wyłącznie wtedy, gdy rzeczonego rozwiązania nie ma. Ale co to właściwie znaczy?

Lemat. \sum_i x_i u_i = 0 nie ma nietrywialnego nieujemnego rozwiązania dokładnie wtedy, gdy wszystkie u_i leżą (ściśle) po tej samej stronie pewnej płaszczyzny przechodzącej przez środek układu współrzędnych.

Dowód. Zamist dowodu proponuję prosty eksperyment myślowy w dwóch wymiarach, czyli na kartce papieru. Można też użyć poniższego rysunku.

kulki

Czyli dostajemy, że problem pojawia się tylko wtedy, gdy u_1,u_2,\ldots,u_k leżą (ściśle) po tej samej stronie pewnej płaszczyzny o wektorze normalnym h. Wiemy, że h \cdot u_i > 0 (gdzie \cdot oznacza iloczyn skalarny) dla i=1,2,\ldots,k, może też (ale nie musi) tak być dla i=k+1,\ldots,7. Dość niewygodne jest to, że nie wiemy nic na temat tego, jak duże są współrzędne h. Jasne jest jedyne to, że bez straty ogólności są one całkowite.

A może jednak coś wiemy? Ułatwmy sobie nieco życie i wymagajmy tylko, żeby h \cdot u_i \geq 0 dla wszystkich i=1,2,\ldots,k i h \cdot u_1 > 0. Myśląc o sytuacji w trzech wymiarach można dojść do wniosku, że wtedy prawie zawsze można lekko obrócić płaszczyznę tak, aby była ona wyznaczona przez dwa z u_i. Prawie zawsze oznacza tutaj, że być może wszystkie u_1,u_2,\ldots,u_k leżą na tej samej płaszczyźnie, i wtedy podczas obracania ciężko zadbać o warunek, że h \cdot u_i > 0 dla choć jednego z nich. Nie jest to jednak problem: wystarczy na chwilę dorzucić do zbioru wektorów któreś z u_{k+1},u_{k+2},\ldots,u_7. Mamy więc, że h można wyliczyć rozwiązując pewien układ równań utworzony przez wybranie dwóch z u_i. Teraz, podobnie jak w przedostatnim lemacie, możemy oszacować współczynniki najmniejszego rozwiązania takiego układu. Znów, pisząc prosty brutalny program (a nawet używając poprzedniego programu) można sprawdzić, że w najgorszym przypadku h=[h_x,h_y,h_z] gdzie |h_x|,|h_y|,|h_z|\leq 6.

Teraz okazuje się, że łatwo możemy ograniczyć |\delta_1|. Mamy bowiem, że \sum_i |\delta_i|u_i=0, czyli \sum_i |\delta_i|h\cdot u_i=0. Skoro h\cdot u_i \geq 0 dla i=2,3,\ldots,k, mamy |\delta_1|h\cdot u_1 \leq \sum_{i>k} |\delta_i| h\cdot u_i, czyli |\delta_1| \leq \sum_{i>k}|\delta_i|h\cdot u_i. Wiemy, że małe są zarówno |\delta_i| dla i=k+1,k+2,\ldots,7, jak i wszystkie współrzędne h i każdego u_i. Oznacza to, że także |\delta_1| nie może być zbyt duże! W najgorszym przypadku h=[6,6,5] i k=1, czyli |\delta_1|\leq 98. W powyższym rozumowaniu u_1 może być tak naprawdę zastąpione dowolnym innym wektorem z u_2,u_3,\ldots,u_k, czyli pokazaliśmy, że |\delta_1|,|\delta_2|,\ldots,|\delta_k|\leq 98. Znów, pisząc prosty brutalny program można uzyskać lepsze ograniczenie górne, ale tę przyjemność zostawimy sobię na inną okazję.

Pokazaliśmy więc, że nie warto rozważać rozwiązań, w których którekolwiek |\delta_i| jest duże. Uzyskane ograniczenie górne nie jest najlepsze możliwe, zaś metoda, którą użyliśmy, by je uzyskać, pewnie jest trochę przekombinowana. Ma ona jednak jedną zaletę: po lekkich modyfikacjach działa w zasadzie dla każdego podobnego problemu. W szczególności, używając podobnych sztuczek można pokazać, że programowanie całkowitoliczbowe może być rozwiązane w niedeterministycznym czasie wielomianowym. To zaś jest faktem równie wesołym, co (zapewne) niepraktycznym.

Reklamy

2 myśli nt. „Gra w kulki

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