Omówienie zadania Licznik długu (I etap XXVIII OI)

W zadaniu dane są dwie duże liczby naturalne \(A\) i \(B\) (mające po \(n-1\) cyfr dziesiętnych) i chcemy obsługiwać operacje zmiany cyfr w tych liczbach i zapytanie o cyfrę ich sumy \(S = A+B\) (mogącą mieć \(n\) cyfr dziesiętnych).

Podzadanie 1

Kolejne cyfry liczb \(A\) i \(B\) będziemy trzymać w tablicach; \(i\)-tą cyfrę oznaczamy przez \(A[i]\).

Po każdej aktualizacji będziemy od nowa obliczać sumę \(S = A+B\). Wykonujemy to szkolnym algorytmem dodawania pisemnego, w którym dodajemy do siebie cyfry na kolejnych pozycjach, ale musimy uwzględniać przeniesienia, jeśli suma na którejś pozycji jest większa niż 9.

Niech \(r\) będzie przeniesieniem na pozycję \(i\) (zakładamy, że początkowe przeniesienie na pozycję \(n\) jest równe 0). Jeśli \(A[i]+B[i]+r \leq 9\), to \(S[i] = A[i]+B[i]+r\) i nowe przeniesienie (na pozycję \(i-1\)) jest równe 0. W przeciwnym wypadku \(S[i] = A[i]+B[i]+r-10\) i nowe przeniesienie jest równe 1. Taki algorytm dodawania działa w czasie \(O(n)\).

Ponieważ w każdym momencie znamy całą sumę \(S\), więc zapytanie robimy w czasie stałym, odczytując wartość \(S[i]\). Zatem cały algorytm działa w czasie \(O(nz)\).

Alternatywne rozwiązanie podzadania 1

Ponieważ operacje zmiany i zapytania dotyczą pojedynczych cyfr, spróbujmy nie wykonywać za każdym razem całego algorytmu dodawania. Nadal będziemy utrzymywać trzy liczby: \(A\), \(B\) i \(S\). Operacja zmiany \(A[i]\) na nową wartość \(A'[i]\) powoduje zmianę cyfry \(S[i]\) o \(d = A'[i]-A[i]\), przy czym \(d\) może być dodatnie lub ujemne.

Załóżmy, że \(d\) jest dodatnie. Jeśli \(S[i]+d \leq 9\), to zwiększamy \(S[i]\) o \(d\) i kończymy. W przeciwnym wypadku nowa wartość to \(S[i]+d-10\) i musimy uwzględnić przeniesienie 1 na pozycję \(i-1\). Jeśli \(S[i-1]=9\), to przeniesienie będzie się propagować na pozycję \(i-2\) itd. Zatem w pętli uaktualniamy kolejne pozycje na lewo od \(S[i]\), dopóki są równe 9.

Rozważmy teraz przypadek \(d\) ujemnego. Jeśli \(S[i]+d \geq 0\), to zmniejszamy \(S[i]\) o \(d\) i kończymy. W przeciwnym wypadku mieliśmy przeniesienie 1 na pozycję \(i-1\), które musimy zlikwidować. Nowa wartość to \(S[i]+d+10\), a od \(S[i-1]\) chcemy odjąć 1. Jeśli \(S[i-1]=0\), to likwidacja przeniesienia będzie się propagować na pozycję \(i-2\) itd. Tak więc w pętli uaktualniamy kolejne pozycje na lewo od \(S[i]\), dopóki są równe 0.

Pesymistyczny czas działania operacji zmiany nadal wynosi \(O(n)\), zatem całego algorytmu \(O(nz)\).

Podzadanie 2

Jeśli w każdym momencie wartości \(A[i]\) oraz \(B[i]\) są równe 0 lub 5, to wartości \(S[i]\) mogą być równe tylko 0 lub 5 (gdy nie było przeniesienia na pozycję \(i\)), albo 1 lub 6 (gdy było przeniesienie na pozycję \(i\)).

Zatem nigdy nie wystąpi propagacja przeniesienia w lewo (bo \(S[i]\) nie może być równe 9), a także propagacja likwidacji przeniesienia (bo jeśli mieliśmy przeniesienie na pozycję \(S[i-1]\), to wtedy \(S[i-1]\) nie mogło być równe 0).

Tak więc operacja zmiany z alternatywnego rozwiązania będzie tu działała w czasie stałym, a cały algorytm w czasie \(O(z)\).

Rozwiązanie wzorcowe

Widać, że w alternatywnym rozwiązaniu problematyczne są długie bloki w liczbie \(S\) złożone z samych cyfr 9 lub z samych cyfr 0. Możemy utrzymywać informację o takich blokach: dla każdej początkowej i końcowej cyfry 9 i 0 pamiętamy, że na niej zaczyna się lub kończy blok.

Teraz propagacja przeniesienia przez blok cyfr 9 powoduje zamianę tego bloku na blok cyfr 0 oraz konieczność wykonania poprawek (stałego rozmiaru) na początku i końcu bloku. Analogicznie działa propagacja likwidacji przeniesienia przez blok cyfr 0.

To da nam operację zmiany w czasie \(O(1)\) i ostateczną złożoność czasową rozwiązania \(O(z)\).