Mopadulo

Dzisiaj zajmiemy się rozwiązaniem zadania mopadulo z potyczek algorytmicznych 2021. W zadaniu tym pytają się nas na ile sposobów można podzielić ciąg na spójne fragmenty tak aby suma każdego fragmentu modulo p była parzysta. Dla przykładu dla ciągu [10, 1, 5, 8] i p = 11 są trzy takie podziały:

10   1   5   8
10   1 | 5   8
10 | 1   5 | 8

Zacznijmy od przestawienia algorytmu dynamicznego działającego w czasie O(n²). Niech D[i] oznacza liczbę sposobów na jaką możemy podzielić ciąg a[1 .. i]. Wtedy D[i] można policzyć w następujący sposób:

D[0] = 1
D[i] = sum D[j] po 0 <= j < i dla których suma elementów a[j+1 .. i] modulo p jest parzysta

W jaki sposób sprawdzić czy suma elementów a[j+1 .. i] modulo p jest parzysta? Można po prostu tę sumę policzyć i sprawdzić. Spróbujmy jednak zrobić to inaczej. Policzmy sumę prafiksową modulo p. Niech S[i] oznacza sumę elementów a[1 .. i] modulo p. Teraz zastanówmy się kiedy suma elementów a[j .. i] modulo p jest parzysta. Jak się domyślamy, musimy popatrzeć na S[j] oraz S[i]. Gdyby wartości nie były liczone modulo p, to suma elementów a[j+1 .. i] byłaby parzysta, gdyby S[j] oraz S[i] miały taką samą parzystość. Jednak ponieważ sumy liczymy modulo p, możemy mieć dziwną sytuację w której S[j] > S[i]. Można zauważyć że w takiej sytuacji parzystość musi być inna. Dla przykładu niech S[j] = 9, S[i] = 4 i niech p = 11. Wtedy suma a[j+1 .. i] modulo p musi być równa 6. Bo 9 + 6 (mod 11) = 4. A skoro jest równa 6, to znaczy że jest parzysta.

Zatem chcielibyśmy znaleźć sumę D[j] dla 0 <= j < i dla których S[j+1] ma taką samą parzystość co S[i] i dla których S[j] <= S[i] lub dla których S[j+1] ma inną parzystość niż S[i] i dla których S[j] > S[i]. Zapomnijmy na chwilę o parzystości i zastanówmy się jaka struktura danych umożliwia dodanie pary (S[i], D[i]) do struktury oraz którą można odpytać o sumę D[i] dla par w których S[i] <= x dla zadanego x. Taką strukturą danych jest na przykład zbalansowane drzewo poszukiwań binarnych w której dodatkowo pamiętamy sumę wartości D[i] w poddrzewie dla każdego wierzchołka (Cormen, rozdział “Wzbogacanie struktur danych” do powtórki). Ta struktura umożliwia zarówno wstawianie jak i odpytanie w czasie logarytmicznym. Inną strukturą, która umożliwia podobne operacje (i w dodatku jest prostsze do implementacji) jest drzewo przedziałowe. Teraz pozostaje jedynie stworzenie dwóch takich struktur (dla elementów parzystych i nieparzystych) i cieszenie się z algorytmu O(n lg n).