Omówienie zadania Pomniejszenie (I etap XXVII OI)

Dane są dwie duże liczby \(A\) i \(B\) o długości \(n\) (mogą mieć zera wiodące) oraz liczba \(k\). Jest spełnione \(A \geq B\) oraz \(1 \leq k \leq n\).

Należy znaleźć liczbę \(A'\) o długości \(n\) (może mieć zera wiodące). Ma być spełnione \(A' < B\), a ponadto \(A'\) można uzyskać z liczby \(A\), zmieniając dokładnie \(k\) cyfr, i \(A'\) jest największa możliwa.

Podzadanie 1

Ponieważ \(n\leq 5\), więc możemy przejrzeć wszystkich możliwych kandydatów na liczbę \(A'\) (będzie ich \(10^n\)) i dla każdego z nich sprawdzić w czasie \(O(n)\) warunki zadania. Złożoność czasowa to \(O(n 10^n)\).

Podzadanie 2

Niech \(A[i]\) będzie \(i\)-tą cyfrą liczby \(A\) (patrząc od lewej do prawej). Warunek \(A' < B\) oznacza, że istnieje pozycja \(i\) taka że \(A'[j]=B[j]\) dla \(j<i\) oraz \(A'[i]<B[i]\).

Aby skonstruować \(A'\), przeiterujmy się zatem po wszystkich pozycjach \(i\) i po każdej cyfrze \(c\), dla której \(c < B[i]\). Dla takiej pary \((i,c)\) załóżmy, że \(i\) jest pierwszą pozycją od lewej, na której \(A'\) i \(B\) się różnią, oraz \(A'[i]=c\).

Musimy wykonać następujące zamiany, aby przekształcić \(A\) na \(A'\):

• Na lewo od \(i\) musimy wykonać zamiany na wszystkich pozycjach \(j\), na których \(A[j] \neq B[j]\). Oznaczmy, że jest \(d\) takich pozycji.

• Jeśli \(A[i]\neq c\), to robimy zamianę na pozycji \(i\)-tej. Zwiększmy wtedy \(d\) o 1.

• Pozostałe zamiany musimy zrobić na prawo od \(i\). Jest tam możliwych \(n-i\) pozycji; na każdej z nich możemy zrobić zamianę cyfry z \(A\) na jakąś inną (bo te cyfry nie będą wpływać na nierówność \(A'<B\)).

Musimy więc wykonać co najmniej \(d\) zamian oraz co najwyżej \(d+(n-i)\) zamian. Warunek na istnieje rozwiązania jest zatem \[d \leq k \leq d+(n-i).\] Jeśli nie jest on spełniony, to dla takiego wyboru pary \((i,c)\) nie jesteśmy w stanie skonstruować liczby \(A'\).

Ponieważ chcemy maksymalizować liczbę \(A'\), więc spośród par \((i,c)\), dla których warunek jest spełniony, wybieramy tę z największym \(i\), a w drugiej kolejności tę z największą cyfrą \(c\).

Mając już ustaloną parę \((i,c)\), konstruujemy liczbę \(A'\). Do pozycji \(i\)-tej włącznie zmieniamy, tak jak opisaliśmy wyżej. Musimy jednak pokazać, jak zrobić \(k-d\) zamian na prawo od pozycji \(i\), aby uzyskać jak największą możliwą liczbę \(A'\):

• Idziemy po kolei (od lewej do prawej) i zmieniamy każdą cyfrę inną niż 9 na cyfrę 9 w \(A\), aż wyczerpiemy budżet zmian lub dojdziemy do końca.

• Idziemy po kolei od końca (od prawej do lewej) i zmieniamy każdą cyfrę 9 na cyfrę 8 w \(A\), aż wyczerpiemy budżet (przy czym uważamy, żeby nie zmieniać cyfr 9 dodanych w poprzednim kroku).

Dla każdej pary \((i,c)\) najkosztowniejsze jest wyznaczenie wartości \(d\), co możemy zrobić w czasie \(O(n)\). Tak więc dla wszystkich par zrobimy to w czasie \(O(n^2)\).

Konstrukcja liczby \(A'\) jest już w czasie \(O(n)\).

Pełne rozwiązanie

Zauważmy, że wszystkie wartości \(d\) możemy stablicować w czasie \(O(n)\), przechodząc liczby \(A\) i \(B\) raz od lewej do prawej. Zatem całe rozwiązanie zadziała w czasie \(O(n)\).