Omówienie zadania Dyscyplina (III etap XXXIII OI)

Skrócona treść zadania

Mamy \(n\) stosów kamieni o rozmiarach \(a_1, a_2, \ldots, a_n\). Każdego dnia możemy wybrać co najwyżej jeden stos i zabrać z niego jeden kamień. Obowiązuje jednak dodatkowe ograniczenie: w dniu \(k\)-tym (dla \(k =1,2,\dots\)) możemy zabrać kamień ze stosu numer \(i\) tylko wtedy, gdy w zapisie binarnym liczby \(k\) jej \(i\)-ty najmniej znaczący bit jest zapalony. Naszym celem jest znalezienie minimalnej liczby dni potrzebnych do zabrania wszystkich kamieni, a wynik należy podać modulo \(10^9+7\).

Podzadanie 1: \(n\leq 4,\ a_i\leq 5\) — przeszukiwanie z nawrotami

Najprostszym podejściem jest rekurencyjne przeszukiwanie z nawrotami, które każdego dnia rozważa wybranie kamienia z każdego ze stosów dozwolonych danego dnia lub niebranie żadnego kamienia. Możemy tu dodać następującą optymalizację: jeżeli obecnie jesteśmy w dniu \(d\), zostało nam jeszcze łącznie \(s\) kamieni oraz \(d+s\) jest większe niż najlepszy wynik znaleziony do tej pory, to możemy od razu przerwać przeszukiwanie tej gałęzi, ponieważ nie znajdziemy w niej lepszego rozwiązania niż to, które mamy obecnie.

W wywołaniach rekurencyjnych należy pamiętać o tym, żeby najpierw rozważać wszystkie opcje brania kamieni, a dopiero na końcu niebrania żadnego, aby uniknąć nieskończonej rekurencji.

Podzadanie 2: \(n\leq 6,\ a_i\leq 10\) — drobna optymalizacja

Powyższe podejście możemy łatwo przyspieszyć w następujący sposób. Jeśli danego dnia mamy możliwość zabrać kamień z jakiegoś stosu, to jest to zawsze nie gorsze niż niebranie żadnego kamienia. W takim wypadku możemy od razu pominąć opcję niebrania kamienia, co znacznie zmniejsza liczbę wywołań rekurencyjnych.

Podzadanie 3: \(n\leq 8,\ a_i\leq 30\) — skojarzenia

W tym zadaniu szukamy najmniejszej liczby \(d\) takiej, że da się do każdego kamienia dopasować jeden z dni \(1, \ldots, d\). Aby sprawdzić, czy dana wartość \(d\) jest wystarczająca, możemy utworzyć graf dwudzielny, w którym wierzchołki po jednej stronie reprezentują kamienie (jest ich \(\sum a_i\)), a wierzchołki po drugiej stronie reprezentują dni od 1 do \(d\) (jest ich \(d\)). Krawędź między kamieniem a dniem istnieje wtedy, gdy dany kamień może być zabrany danego dnia.

Następnie, korzystając z algorytmu do znajdowania maksymalnego skojarzenia w grafie dwudzielnym, możemy sprawdzić, czy istnieje skojarzenie, w którym każdy kamień jest dopasowany do jakiegoś dnia.

Możemy więc sprawdzać, czy dana wartość \(d\) jest wystarczająca, dla kolejnych wartości \(d\) od \(\sum a_i\) wzwyż, aż znajdziemy pierwszą wartość, dla której istnieje takie skojarzenie.

Alternatywnie możemy także wyszukać binarnie po \(d\), jednak przy limitach tego podzadania liniowe sprawdzanie jest wystarczająco szybkie. Pomysł z wyszukiwaniem binarnym po \(d\) będzie jednak bardzo przydatny w kolejnych podzadaniach.

Podzadanie 4: \(n\leq 8\) — sieć przepływowa

W tym podzadaniu zarówno liczba kamieni, jak i liczba dni, są zbyt duże na zwykłe sprawdzanie skojarzenia. Zauważmy jednak, że jeśli \(d\) jest wystarczającą liczbą dni, aby przenieść wszystkie kamienie, to każda liczba dni większa od \(d\) także jest wystarczająca. Możemy więc skorzystać z wyszukiwania binarnego po wyniku. Wówczas otrzymujemy prostszy problem: sprawdzić, czy dana liczba dni jest wystarczająca.

W tym celu możemy zgrupować wszystkie kamienie danego stosu w jeden wierzchołek, a także zgrupować dni według ich reszty z dzielenia przez \(2^n\), ponieważ dni o tej samej reszcie mają krawędzie do tych samych stosów.

Na takich wierzchołkach budujemy sieć przepływową, gdzie krawędzie mają następujące przepustowości: ze źródła do stosów przepływa \(a_i\) jednostek, między stosami a dniami przepustowość jest nieskończona (jeśli w danym dniu można zabrać kamień z danego stosu), a z dni do ujścia przepływa tyle jednostek, ile jest dni pośród \(1,2,\dots,d\) o danej reszcie modulo \(2^n\). Na takiej sieci możemy użyć algorytmu Dinica bądź Edmondsa-Karpa, aby znaleźć maksymalny przepływ i sprawdzić, czy jest on równy dokładnie \(\sum a_i\). Jeżeli tak, to dana wartość \(d\) jest wystarczająca, w przeciwnym wypadku nie jest.

Podzadanie 5: \(n\leq 16\) — ważone twierdzenie Halla

Dla tak dużych danych wejściowych stworzona wcześniej sieć przepływowa jest już zbyt duża dla dowolnego algorytmu przepływowego. Skorzystamy więc z innego podejścia, opartego na ważonym twierdzeniu Halla.

Przypomnijmy klasyczne twierdzenie Halla: w grafie dwudzielnym z wierzchołkami \(L\) po lewej stronie i \(R\) po prawej, skojarzenie pokrywające wszystkie wierzchołki z \(L\) istnieje wtedy i tylko wtedy, gdy dla każdego podzbioru \(S \subseteq L\) zachodzi \(|S| \leq |N(S)|\), gdzie \(N(S)\) to zbiór sąsiadów wierzchołków z \(S\).

Ważona wersja twierdzenia Halla uogólnia ten warunek na przypadek, gdy wierzchołki mają niejednostkowe wagi. Niech każdy wierzchołek \(v \in L\) ma wagę \(w_L(v)\), a każdy wierzchołek \(u \in R\) ma wagę \(w_R(u)\). Szukamy przepływu, w którym z każdego \(v \in L\) wypływa dokładnie \(w_L(v)\) jednostek, a do każdego \(u \in R\) wpływa co najwyżej \(w_R(u)\) jednostek. Ważone twierdzenie Halla mówi, że taki przepływ istnieje wtedy i tylko wtedy, gdy dla każdego podzbioru \(S \subseteq L\) zachodzi \[\sum_{v \in S} w_L(v) \leq \sum_{u \in N(S)} w_R(u).\]

W naszym problemie wierzchołkami po lewej stronie są stosy z wagami \(a_i\), a po prawej stronie są grupy dni (zgrupowane według reszty modulo \(2^n\)) z wagami równymi liczbie dni danego typu pośród \(1, 2, \ldots, d\). Dla ustalonej wartości \(d\) z wyszukiwania binarnego, musimy sprawdzić, czy dla każdego podzbioru stosów \(S\) zachodzi \(\sum_{i \in S} a_i \leq f(S)\), gdzie \(f(S)\) oznacza łączną wagę grup dni sąsiadujących ze stosami z \(S\).

Liczbę dni każdego typu możemy łatwo obliczyć na podstawie \(d\). Następnie, aby wyznaczyć \(f(S)\) dla wszystkich podzbiorów \(S\), wykonujemy programowanie dynamiczne SOS (sum-over-subsets), które pozwala obliczyć te wartości w złożoności \(O(n \cdot 2^n)\).

Łącząc to z wyszukiwaniem binarnym po odpowiedzi, uzyskujemy rozwiązanie o złożoności \(O(n \cdot 2^n \cdot \log \text{odp})\), co wystarcza dla tego podzadania.

Podzadanie 6: \(n\leq 20\) — bezpośrednie obliczenie w \(O(n \cdot 2^n)\)

W tym podzadaniu możemy pozbyć się wyszukiwania binarnego i obliczyć bezpośrednio dla każdego podzbioru \(S\) minimalną liczbę dni potrzebną, aby dni "obsługujące" ten podzbiór wystarczyły do wyniesienia wszystkich odpowiadających mu kamieni.

Algorytm dla jednego podzbioru \(S\) wygląda następująco. Podzbiór \(S\) reprezentujemy jako maskę bitową długości \(n\), gdzie bit \(i\) jest zapalony wtedy i tylko wtedy, gdy \(i \in S\). Niech \(m = \max(S)\) będzie największym elementem podzbioru (czyli kamienie ze stosu \(m\) możemy zabierać tylko w dniach, w których zapalony jest bit \(m\)-ty). Bity indeksujemy od 1 do \(n\), przy czym 1 oznacza najmniej znaczący bit.

Przyjrzyjmy się cyklowi dni o długości \(2^m\). Zastanówmy się, ile dni w tym cyklu ma zapalony przynajmniej jeden bit należący do \(S\). Zauważmy, że podczas takiego cyklu każda możliwa maska bitowa długości \(m\) pojawia się dokładnie raz na \(m\) najmniej znaczących bitach numeru dnia. Oznaczmy \(s = |S|\). Podczas tego cyklu mamy dokładnie \((2^s-1)\cdot 2^{m-s}\) dni, w których zapalony jest przynajmniej jeden bit z \(S\). Czynnik \(2^s - 1\) to liczba niepustych konfiguracji \(s\) bitów należących do \(S\) (przynajmniej jeden bit musi być zapalony, co odejmuje nam jedną możliwość spośród wszystkich \(2^s\) możliwości), a \(2^{m-s}\) to liczba konfiguracji pozostałych \(m-s\) bitów (tych spoza \(S\), ale poniżej \(m\)), które mogą być dowolne.

Mając tę wartość, od sumy kamieni \(\sum_{i \in S} a_i\) odejmujemy tyle pełnych cykli, ile się da, zwiększając liczbę potrzebnych dni o długość cyklu (\(2^m\)) przy każdym odjęciu. Pozostaje nam reszta kamieni i musimy rozważyć niepełny cykl. Rozważmy pierwszą połowę cyklu, czyli dni \(1, \ldots, 2^{m-1}-1\). Pośród tych dni jest dokładnie \((2^{s-1}-1)\cdot 2^{m-s}\) dni z zapalonym bitem z \(S\), ponieważ w tej połowie cyklu bit \(m\)-ty nie jest zapalony, więc mamy do dyspozycji tylko \(s-1\) bitów z \(S \setminus \{m\}\), a pozostałe \(m-s\) bitów może być dowolnych.

Jeśli ta liczba dni jest mniejsza niż liczba kamieni, które pozostały do obsłużenia, to wiemy, że musimy wykorzystać wszystkie te dni, a następnie przejść do drugiej połowy cyklu, czyli dni \(2^{m-1}, \ldots, 2^m-1\). W każdym z tych dni bit \(m\)-ty jest zapalony, więc każdy z nich możemy wykorzystać do zabrania kamienia. Zatem w tym przypadku do odpowiedzi dodajemy \(2^{m-1}\) (długość pierwszej połowy cyklu) plus tyle dni z drugiej połowy cyklu, ile kamieni pozostało do obsłużenia po wykorzystaniu dni z pierwszej połowy.

W przeciwnym razie, jeśli liczba pozostałych kamieni jest nie większa niż \((2^{s-1}-1)\cdot 2^{m-s}\), to wiemy, że nie będziemy już wykorzystywać bitu \(m\), więc usuwamy go z \(S\) (tzn. rozważamy \(S' = S \setminus \{m\}\)) i powtarzamy procedurę rekurencyjnie dla \(S'\) z nowym \(m' = \max(S')\).

Obliczenie wartości dla jednego podzbioru zajmuje czas \(O(n)\), więc dla wszystkich podzbiorów otrzymujemy złożoność \(O(n \cdot 2^n)\). Odpowiedzią w zadaniu jest maksimum po wszystkich podzbiorach.

Podzadanie 7: \(a_i\leq 10^5\) — lemat dla dużych \(n\)

Łatwo zauważyć, że dla wystarczająco dużego \(n\) tylko \(a_n\) ma znaczenie. Możemy to sformalizować następującym lematem:

Lemat: Jeżeli \(2^{n-2} \geq \sum_{i=1}^{n-1} a_i\), oraz \(a_n \leq 2^{n-1}\), to wynikiem w zadaniu jest \(2^{n-1} + a_n - 1\).

Dowód: Zauważmy, że wynik wynosi co najmniej \(2^{n-1}\), ponieważ jest to numer pierwszego dnia, w którym możemy zabrać kamień ze stosu \(n\). Rozważmy dni od 1 do \(2^{n-1} - 1\) oraz stosy od \(1\) do \(n-1\). Dla każdego z tych stosów wśród rozważanych dni jest dokładnie \(2^{n-2}\) dni, w których możemy z niego brać kamienie. Korzystając ponownie z ważonej wersji twierdzenia Halla, można przekonać się, że warunek wspomniany w tym twierdzeniu jest spełniony dla każdego podzbioru, ponieważ każdemu kamieniowi z tych stosów przypisujemy przynajmniej tyle dni, ile jest łącznie wszystkich kamieni. Tak więc istnieje pewne przypisanie wszystkich kamieni ze stosów od \(1\) do \(n-1\) do dni od \(1\) do \(2^{n-1} - 1\). Po przypisaniu tych kamieni, pozostaje nam jeszcze co najwyżej \(a_n\) kamieni ze stosu \(n\) do obsłużenia, a mamy do dyspozycji dni od \(2^{n-1}\) wzwyż, więc możemy je wszystkie obsłużyć w dniach od \(2^{n-1}\) do \(2^{n-1} + a_n - 1\), z których każdy jest dobry dla stosu \(n\), ponieważ \(a_n \leq 2^{n-1}\).

Przy limitach w tym podzadaniu, używając lematu możemy dla \(n \geq 24\) wypisać wynik zgodnie ze wzorem, a dla mniejszych \(n\) stosować rozwiązanie podzadania 6.

Rozwiązanie wzorcowe — digit DP

W głównej wersji zadania lemat pozwala ograniczyć \(n\) do około 57, co jest jednak zbyt dużą wartością dla poprzedniego podejścia iterującego po wszystkich podzbiorach. Musimy więc zastanowić się dokładniej, co dzieje się w podejściu z twierdzeniem Halla.

Niech \(d\) będzie wartością z wyszukiwania binarnego. Dla podzbioru stosów \(S\) niech \(f(S)\) oznacza liczbę dni między 1 a \(d\) (włącznie), do których są krawędzie z \(S\). Chcemy sprawdzić, czy dla któregoś podzbioru \(S\) zachodzi \(\sum_{i \in S} a_i > f(S)\), co jest równoważne sprawdzeniu, czy \(\sum_{i \in S} a_i + (d + 1 - f(S)) > d + 1\). Wyrażenie \(d + 1 - f(S)\) to liczba dni pośród dni od 0 do \(d\), do których nie ma krawędzi w rozważanym grafie (do dnia o numerze 0 nie ma żadnych krawędzi).

Jeżeli znajdziemy podzbiór \(S\) maksymalizujący wyrażenie \(\sum_{i \in S} a_i + (d + 1 - f(S))\), to będziemy mogli po prostu sprawdzić, czy ta wartość przekracza \(d+1\). Jeżeli tak, to \(d\) jest zbyt małe, a jeżeli nie, to \(d\) jest wystarczające.

Oznaczmy przez \(g(S) = d + 1 - f(S)\) liczbę dni pośród \(0, 1, \ldots, d\), które nie mają żadnego wspólnego bitu z maską \(S\). Zauważmy, że dla pełnych cykli \([0, 2^n-1], [2^n, 2 \cdot 2^n - 1], \ldots\) liczba dni rozłącznych z maską \(S\) wynosi zawsze \(2^{n - |S|}\). Niech \(d + 1 = c \cdot 2^n + r\), gdzie \(c\) to liczba pełnych cykli, a \(r \in [0, 2^n)\) to reszta. Wówczas \[g(S) = c \cdot 2^{n - |S|} + h(S, r),\] gdzie \(h(S, r)\) to liczba dni w przedziale \([0, r)\) rozłącznych z \(S\).

Aby obliczyć \(h(S, r)\), będziemy rozważać reprezentacje binarne liczb. Dla liczby \(x\) oznaczamy przez \(x_i\) jej \(i\)-ty bit, gdzie bity numerujemy od 1 (najmniej znaczący) do \(n\) (najbardziej znaczący). Analogicznie \(S_i\) oznacza, czy pozycja \(i\) należy do maski \(S\) i podobnie dla \(r_i\).

Iterujemy po wszystkich możliwych pozycjach \(p\), które są najwyższą pozycją, na której zarówno \(S\) jak i \(r\) mają jedynkę. Ustalenie takiej pozycji \(p\) nakłada ograniczenia na maskę \(S\):

• Na pozycji \(p\): Musi zachodzić \(S_p = 1\) (z definicji \(p\)).
• Powyżej \(p\) (pozycje \(i > p\)): Jeśli \(r_i = 1\), to musimy mieć \(S_i = 0\) (inaczej \(p\) nie byłoby najwyższą wspólną jedynką). Jeśli \(r_i = 0\), możemy dowolnie wybrać \(S_i \in \{0, 1\}\).
• Poniżej \(p\) (pozycje \(i < p\)): Nie ma ograniczeń i możemy dowolnie wybrać \(S_i \in \{0, 1\}\).

Zastanówmy się, jak wyglądają liczby \(x < r\) rozłączne z \(S\). Każda taka liczba \(x\) musi mieć \(x_p = 0\) (bo \(S_p = 1\)), co oznacza, że najdłuższy wspólny prefiks \(x\) i \(r\) kończy się na pozycji większej niż \(p\). Na pozycjach poniżej \(p\) liczba \(x\) może mieć dowolne bity, o ile są rozłączne z \(S\).

Dla pozycji \(p, p+1, \dots, n\) zdefiniujemy następujące programowanie dynamiczne: \[\text{DP}(i, j) = \text{maksymalna wartość } \sum_{k \in S} a_k + |\{x < r : x \cap S = \emptyset,\, x \text{ ma wspólny prefiks z } r \text{ do pozycji } i+1\}|\] pośród wszystkich \(S \subseteq \{1, \ldots, i\}\), gdzie \(|S| = j\) oraz \(p\in S\).

Najpierw zastanówmy się, jak obliczyć \(\text{DP}(p, j)\) dla \(j \in [1, p]\). Naturalnie \(S\) musi zawierać pozycję \(p\), na której jest jedynka, stąd rozważamy \(j \geq 1\). Mamy więc \(j-1\) jedynek do rozłożenia na pozycjach \(1, \ldots, p-1\). Liczba dni \(x\), które mają wspólny prefiks z \(r\) przynajmniej do pozycji \(p+1\) i są rozłączne z \(S\), wynosi dokładnie \(2^{p-j}\), ponieważ na pozycjach, gdzie nie wybierzemy jedynek w \(S\), możemy mieć dowolne bity, a każdy taki ciąg binarny odpowiada wartości mniejszej od \(r\) (bo ma wspólny prefiks do pozycji \(p+1\) oraz 0 na pozycji \(p\), gdzie \(r\) ma 1). W takim razie \[ \text{DP}(p, j) = 2^{p-j} + a_p + \text{suma } j-1 \text{ największych } a_k \text{ dla } 1 \leq k < p. \]

Następnie, obliczając \(\text{DP}(i, j)\) dla \(i > p\), mamy dwie możliwości. Jeśli \(r_i = 1\), to wiemy, że musimy mieć \(S_i = 0\). Wówczas nie dochodzi nam żadna wartość \(a_i\) do sumy, a liczba dni rozłącznych z \(S\), mniejszych od \(r\) i mających wspólny prefiks z \(r\) przynajmniej do pozycji \(i+1\), rośnie względem tej zliczanej w \(\text{DP}(i-1, j)\), bo teraz pozwalamy na takie dni \(x\), gdzie \(x_i\) może być równe 0, a wcześniej nie pozwalaliśmy, bo \(x_i\) musiało być takie samo jak \(r_i\). Ta liczba rośnie o dokładnie \(2^{i-1-j}\), ponieważ na pozycjach \(1, \dots, i-1\), gdzie nie wybierzemy jedynek w \(S\), możemy mieć dowolne bity. Otrzymujemy więc wzór \[ \text{DP}(i, j) = \text{DP}(i-1, j) + 2^{i-1-j}. \]

Jeśli natomiast \(r_i = 0\), to możemy mieć \(S_i = 1\) lub \(S_i = 0\). W pierwszym przypadku dorzucamy \(a_i\) do sumy, a liczba dni \(x\) rozłącznych z \(S\), mniejszych od \(r\) i mających wspólny prefiks z \(r\) przynajmniej do pozycji \(i+1\), nie ulega zmianie (nowe dni muszą mieć \(x_i = 0\), a mamy też \(r_i = 0\)). W drugim przypadku nie dorzucamy \(a_i\) do sumy, ale liczba dni także się nie zmienia, bo nowe dni muszą mieć \(x_i = 0\), gdyż muszą być takie same jak \(r\) na pozycjach większych od \(i\) i muszą być mniejsze od \(r\) (czyli nie mogą mieć \(x_i = 1\)). Otrzymujemy więc wzór \[ \text{DP}(i, j) = \max(\text{DP}(i-1, j-1) + a_i, \text{DP}(i-1, j)). \]

Ostatecznie wystarczy spojrzeć na \(\text{DP}(n, j)\) dla \(j \in [1, n]\) i znaleźć maksimum pośród wartości \(\text{DP}(n, j) + c \cdot 2^{n-j}\), ponieważ nasza wartość \(\text{DP}(n, j)\) odpowiada obliczonemu \(h\) zawężonemu tylko do masek, w których dokładnie \(j\) bitów jest zapalonych, a najwyższy wspólny bit \(S\) i \(r\) jest na pozycji \(p\).

Powtarzając ten algorytm dla wszystkich pozycji \(p\) od \(1\) do \(n\), gdzie \(r\) ma zapalony bit, a także dla specjalnego przypadku, gdzie rozważamy maski \(S\) rozłączne z \(r\) (rozwiązujemy go podobnym programowaniem dynamicznym, które zaczyna od sztucznej pozycji \(p = 0\)), możemy znaleźć maksymalną wartość \(\sum_{i \in S} a_i + g(S)\) w złożoności \(O(n^3)\) dla jednego \(d\). W połączeniu z wyszukiwaniem binarnym po \(d\) daje to rozwiązanie o złożoności \(O(n^3 \cdot \log(\text{odp}))\), gdzie \(\text{odp}\) to wynik zadania.