Omówienie zadania Bukmacher (III etap XXXI OI)

Zauważmy, że pesymistycznie (dla \(n = 20)\) jest \(2^{20} = 1\,048\,576\) różnych możliwych zapytań, a w jednym teście możemy dostać ich aż \(1\,000\,000\). Sugeruje to stworzenie rozwiązania, który przelicza odpowiedzi dla wszystkich możliwych pytań.

Rozwiązanie wzorcowe \(O(2^n \cdot n + q + z)\):

Aby być w stanie indeksować tablice ciągami binarnymi, będziemy reprezentować je maskami bitowymi.

Rozważmy następujące programowanie dynamiczne: \(dp[i][mask]\) = największy zysk z pierwszych \(i\) meczy, pomniejszony o koszt zakładu jaki jesteśmy w stanie uzyskać, gdy pierwsze \(i\) wyników naszego zakładu jest takie same jak pierwsze \(i\) bitów maski \(mask\), a wyniki meczu zgadzają się z \(mask\) na ostatnich \(n - i\) bitach.

Stany początkowe to \(dp[0][mask] = -(\) koszt najtańszego zakładu opisywanego maską \(mask)\) oraz \(-\infty\) jeżeli taki zakład nie istnieje.

Wynik znajdzie się w \(dp[n][mask]\) dla zapytania równego \(mask\).

Z definicji programowania dynamicznego wynikają następujące przejścia:

Jeśli \(i \in mask\), to \(dp[i][mask] = max(dp[i - 1][mask] + b_i , dp[i][mask \oplus 2^i])\).

(Ponieważ albo druga drużyna zwyciężyła na \(i\)-tym bicie, za co zyskujemy \(b_i\), albo nie zwyciężyła, a takim przypadku nic nie zyskujemy.)

Jeśli \(i \notin mask\), to \(dp[i][mask] = max(dp[i - 1][mask] + a_i, dp[i][mask \oplus 2^i])\).

(Uzasadnienie analogiczne.)

Operacja \(\oplus\) oznacza xor bitowy. Aby znaleźć liczbę kombinacji, możemy rozszerzyć utrzymywane wartości w programowaniu dynamicznym o parę liczb całkowitych, gdzie jedna z liczb utrzymuje wyżej opisany wynik, a druga z nich liczbę wystąpień tego konkretnego wyniku. Gdy porównujemy dwie pary w przejściu programowaniu dynamicznego w funkcji \(max\), jeżeli wynik jednej z par jest ściśle większy, to bierzemy ją. W przeciwnym przypadku sumujemy liczby wystąpień.

Poprawność algorytmu wynika z faktu, że dla danej pary masek, istnieje dokładnie jeden sposób przekształcenia jednej z nich w drugą zastępując bit jeden po drugim.