Omówienie zadania Ciąg binarny (II etap XXXI OI)

Wstępna obserwacja

Rozważmy ciąg binarny \(a_1, a_2, \dots, a_s\), którego szukamy jego \(k\)-przybliżenia - ciągu \(b_1, b_2, \dots, b_s\). Zauważmy, że by miał on największą możliwą sumę, to musi zachodzić implikacja \(a_i = a_{i+1} \Rightarrow b_i = b_{i+1}\) dla każdego \(i \in \{1, \dots, s-1\}\). Dowód:

  • Jeżeli \(a_i = a_{i+1} = 0\), to oczywiście \(b_i = b_{i+1} = 0\).
  • Jeżeli \(a_i = a_{i+1} = 1\), to dowodząc przez sprzeczność załóżmy, że \(b_i \neq b_{i+1}\). Skupmy się na przypadku \(b_i = 1, b_{i+1} = 0\) - przypadek \(b_i = 0, b_{i+1} = 1\) jest analogiczny. Wtedy możemy rozważyć ciąg \(b'\) równy ciągowi \(b\) na każdej pozycji poza pozycją \(i+1\)-tą, na której ma ona wartość \(1\). Ponieważ \(b'_i = b'_{i+1}\), to liczba pozycji, na których sąsiednie wartości są różne w \(b'\) jest nie większa niż w ciągu \(b\). Ponadto, ciąg \(b'\) ma większą sumę niż ciąg \(b\), a więc ciąg \(b\) nie jest \(k\)-przybliżeniem ciągu \(a\) - sprzeczność. Z uzyskanej sprzeczności wynika teza.

Dalsza analiza

Wiemy już, że opłaca nam się brać tylko pełne przedziały jedynek. Załóżmy, że początkowo nie mamy żadnego wybranego przedziału jedynek. Każdy przedział jedynek, który możemy wziąć do rozwiązania, ma pewien koszt, który ponosimy, jeżeli chcemy wziąć go do ciągu \(b\). Jeżeli cały ciąg \(a\) składa się tylko z jedynek, to ten jedyny przedział jedynek ma koszt \(0\). Pomijając ten trywialny przypadek, przedział jedynek będący na początku lub na końcu ciągu \(a\) ma koszt \(1\). Natomiast wzięcie do ciągu \(b\) ciągu jedynek będącego ściśle wewnątrz ciągu \(a\) (to znaczy: niezawierający elementów brzegowych) kosztuje nas \(2\).

Naszym zadaniem jest wybrać takie przedziały, aby ich sumaryczny koszt nie przekroczył \(k\) oraz by suma ich długości była jak największa. Ponieważ wszystkie przedziały ściśle wewnątrz mają ten sam koszt równy \(2\), to sugeruje nam to spróbować rozpatrzyć je razem. Rozpatrzmy więc trzy przypadki:

  • Po pierwsze, jeżeli przedział jedynek występuje i na początku i na końcu ciągu \(a\), to możemy rozpatrzeć wzięcie ich obydwu do rozwiązania. Zostanie nam wtedy budżet \(k - 2\) na przedziały ściśle wewnątrz, a więc będziemy mogli wziąć ich \(\lfloor\frac{k - 2}{2}\rfloor\).
  • Drugą opcją jest wziąć dłuższy z tych dwóch przedziałów, jeżeli któryś z nich występuje. Zostanie nam wtedy budżet \(k - 1\) na przedziały ściśle wewnątrz, a więc będziemy mogli wziąć ich \(\lfloor\frac{k - 1}{2}\rfloor\).
  • Trzecią opcją jest nie brać żadnego z brzegowych przedziałów. Zostanie nam wtedy budżet \(k\) na przedziały ściśle wewnątrz, a więc będziemy mogli wziąć ich \(\lfloor\frac{k}{2}\rfloor\).

Rozpatrywanie zapytań

W zadaniu nie mamy jednak danego ciągu \(a_1, \dots, a_s\), tylko interesują nas spójne fragmenty danego ciągu \(x_1, \dots, x_S\). Dodaje nam to pewne techniczne problemy, które teraz omówimy.

Niech ciąg \(e\) będzie równy \(d_1, d_3, d_5, \dots\). Po pierwsze, musimy na podstawie liczb \(l, r\) znaleźć odpowiedni fragment \(l', r'\) ciągu \(e\). Możemy sobie z tym poradzić licząc na początku programu sumy prefiksowe na ciągu \(d\), a następnie wykonując na nich wyszukiwanie binarne.

Po znalezieniu fragmentu \(l', r'\) ciągu \(e\) musimy sprawdzić czy na początku oraz końcu przedziału \(x_l, \dots, x_r\) są ciągi jedynek i jeżeli tak, to jak długie są. Warto uważać podczas pisania tego ciągu \(if\)-ów. Łatwo tu popełnić błąd.

Mając już wyznaczone te wartości zostało nam rozpatrzyć wspomniane wcześniej trzy przypadki, które sprowadzają się do znajdowania sumy \(k'\) największych wartości na przedziale \(e_{l'}, \dots, e_{r'}\), gdzie \(k'\) to odpowiednio \(\lfloor\frac{k}{2}\rfloor\), \(\lfloor\frac{k - 1}{2}\rfloor\) lub \(\lfloor\frac{k - 2}{2}\rfloor\).

Należy również zwrócić szczególną uwagę na przypadki takie jak \(k = 0\) oraz \(k = 1\), w których nie możemy potencjalnie wziąć jednego bądź obydwu przedziałów brzegowych.

Znajdowanie sumy \(k'\) największych wartości na przedziale

Problem znajdowania sumy \(k'\) największych wartości na przedziale statycznego ciągu można rozwiązać na wiele sposobów. Poniżej opiszemy niektóre z nich.

  • Rozwiązania pierwiastkowe

    By osiągnąć złożoność lepszą niż rozwiązanie brutalne, można próbować rozwiązać to zadanie z użyciem rozbicia przez pierwiastek lub wykorzystać fakt, że różnych liczb w ciągu \(e\) jest co najwyżej \(O(\sqrt{S})\). Takie podejścia mają szansę rozwiązać znaczącą liczbę podzadań, ale raczej nie dostaną kompletu punktów.

  • Wavelet tree

    Pierwsze rozwiązanie wzorcowe tego problemu używa struktury danych zwanej Wavelet Tree. Dokładny jej opis (w języku angielskim) można znaleźć np. na tym blogu. W skrócie, chcemy na ciągu wartości występujących w ciągu \(e\) zbudować drzewo przedziałowe, które w węzłach bazowych trzyma posortowane indeksy pozycji, na których one występują. Po wzbogaceniu tej struktury o sumy prefiksowe w węzłach bazowych oraz wskaźniki na odpowiadające indeksy w dzieciach danego wierzchołka jesteśmy w stanie w czasie \(O(\log S)\) odpowiadać na zapytania. Natomiast skalując na początku rozwiązania wartości do przedziału \([1, n]\) jesteśmy w stanie zbić złożoność do \(O(\log n)\) na zapytanie.

  • Trwałe drzewo przedziałowe

    Podczas gdy Wavelet Tree pozwala nam odpowiadać na zapytania online, możemy jednak spróbować wykorzystać fakt, że mamy dostęp do wszystkich zapytań na raz i odpowiedzieć na nie offline. Wykorzystamy w tym celu zamiatanie wykorzystujące trwałe drzewo przedziałowe. Będziemy szli po pozycjach ciągu \(e\) od lewej do prawej i w momencie rozpatrywania pozycji \(p\), będziemy chcieli odpowiedzieć na wszystkie zapytania, których \(r'\) jest równe \(p\). Rozłóżmy drzewo przedziałowe po wartościach występujących w ciągu \(e\). Podczas przechodzenia po elementach ciągu \(e\), będziemy utrzymywać z jego pomocą informację o liczności oraz sumie wartości na rozważonym już prefiksie ciągu. Jeżeli utrwalimy to drzewo, to dla zapytania \(l', r'\) oraz pewnej wartości \(z\) pozwoli ono nam odpowiedzieć na pytanie ile liczb na przedziale \(e_{l'}, \dots, e_{r'}\) jest większych niż \(z\) oraz jaka jest ich suma. Wykorzystując więc wyszukiwanie binarne pozwoli nam to w złożoności \(O(\log^2 n)\) odpowiedzieć na pojedyncze zapytanie, po początkowym przeskalowaniu wartości ciągu \(e\). Jednakże, można dosyć łatwo zbić to do \(O(\log n)\) jeżeli wykonamy wyszukiwanie binarne na drzewie przedziałowym polegające na umiejętnym zejściu po nim zaczynając od korzenia i kierując się wartościami z dzieci.

  • Równoległe wyszukiwanie binarne

    Jeszcze inne rozwiązanie stara się wyznaczyć dla każdego zapytania największą taką liczbę \(z\), że ciąg \(e_{l'}, \dots, e_{r'}\) zawiera co najmniej \(k'\) liczb większych niż \(z\). Możemy do tego wykorzystać równoległe wyszukiwanie binarne. W danej iteracji wyszukiwania binarnego \(i\)-te zapytanie będzie chciało się dowiedzieć ile na przedziale \([l', r']\) jest liczb większych niż \(z_i\). By odpowiedzieć na te wszystkie zapytania na raz możemy posortować razem ciąg \(e\) oraz wartości \(z_i\) i przejść po nich od największych. Jak natrafimy na wartość ciągu \(e\), to zaznaczamy to na drzewie przedziałowym. Natomiast jak natrafimy na wartość \(z_i\), to wykonujemy zapytanie o liczbę zaznaczonych już liczb na przedziale \([l', r']\). W ten sposób jesteśmy w stanie w złożoności \(O((n+q)\log^2 n)\) wyznaczyć wszystkie pożądane wartości i następnie w podobny sposób wyliczyć sumy wartości, które nas interesują. Ponieważ ma ono gorszą złożoność, to może dostać mniej punktów niż inne przedstawione rozwiązania, ale ze względu na małą stałą ma ono również szansę na wysoki wynik.