Informatyczny kącik olimpijski

Cyfrowy ciąg

W tym odcinku omówimy rozwiązanie zadania "Cyfrowy ciąg", które pojawiło się w eliminacjach do zawodów Romanian Master of Informatics.

Zadanie (Cyfrowy ciąg). Tadek napisał ciąg $S = (s ,s ,...,s ), 1 2 n$ złożony z $|n$ cyfr od $1$ do $9.$ Chciałby podzielić ten ciąg na $|k$ spójnych fragmentów. Każdy fragment czytany od lewej do prawej tworzy liczbę. Tadek chciałby dokonać takiego podziału, aby największa z $|k$ otrzymanych liczb była jak najmniejsza.

Niech $|S[a b]$ oznacza fragment $|sa,sa+1,...,sb.$

Zauważmy, że $S$ zawiera tylko cyfry od $|1$ do $|9$ - nie ma cyfry $0.$ Zatem dowolny jego fragment opisuje liczbę bez zer wiodących. Od tego momentu zakładamy, że rozważamy tylko liczby bez zer wiodących. Wiadomo, że dłuższa liczba jest większa niż krótsza. W związku z tym chcemy tak podzielić ciąg, aby największa liczba była możliwie najkrótsza. Największa liczba zawiera przynajmniej $n ⌈ k⌉$ cyfr. Zauważmy, że w jakimś optymalnym podziale będą wyłącznie liczby $⌈nk ⌉$ -cyfrowe lub $|(⌈n ⌉− 1) k$ -cyfrowe. Dokładniej, w jakimś optymalnym podziale będzie:

$x$ liczb $|⌈nk ⌉$ -cyfrowych, gdzie $x = k,$ jeśli $k n$ i $|x = n mod k$ w przeciwnym przypadku,
$y$ liczb $n |(⌈ k⌉− 1)$ -cyfrowych, gdzie $y = k− x.$

Niech $n dx = ⌈k⌉$ oraz $n dy = ⌈k ⌉− 1.$ Szukamy takiego podziału $S$ na $x$ liczb $|dx$ -cyfrowych i $|y$ liczb $dy$ -cyfrowych, żeby największa liczba była jak najmniejsza.

Rozwiązanie $|O$
Ten problem możemy rozwiązać za pomocą metody programowania dynamicznego. Otóż niech $P[i][ j] |D$ oznacza wartość największej liczby w optymalnym podziale $|idx + jdy$ pierwszych cyfr ciągu na $|i$ liczb $|dx$ -cyfrowych oraz $| j$ liczb $|dy$ -cyfrowych. Wyznaczymy wartości $P[i][ j]D$ dla wszystkich takich $i, j,$ że $0 ⩽ i⩽ x$ oraz $0 ⩽ j⩽ y.$ Wówczas wynikiem będzie $P[x][y]. |D$ Niech $P[0][0]=0, |D$ zaś $P[i][ j]=min(p,p) |D 12$
dla $i + j > 0,$ gdzie:

$p1$ to wynik podziału przy założeniu, że ostatnia liczba ma $dx$ cyfr. Wtedy $P[i−1][ j],S[1+(i−1)d+ jd id+ jd]), p = max(D xyxy 1$ jeśli $i > 0$
i $p1 =∞$ w przeciwnym przypadku.
$p 2$ to wynik podziału przy założeniu, że ostatnia liczba ma $dy$ cyfr. Wtedy $P[i][ j−1],S[1+idx+( j−1)dy idx+ jdy]), p2 = max(D$ jeśli $j > 0$
i $p =∞ 2$ w przeciwnym przypadku.

Mamy $O(k)$ liczb "dłuższych" oraz $O(k) |$ liczb "krótszych", czyli wszystkich stanów do obliczenia jest $O(k |$ Obliczenie jednego stanu zajmuje $|O$ (porównanie dwóch liczb długości $|O$ ). Zatem całe rozwiązanie działa w czasie $O(nk).$

Rozwiązanie $|O$
W tym rozwiązaniu wykorzystamy algorytm wyszukiwania binarnego. Wiemy, że wynikiem jest wartość jakiegoś podsłowa długości $|dx.$ W pierwszej fazie rozwiązania weźmy wszystkie $|dx$ -cyfrowe podsłowa i uporządkujmy je niemalejąco. Takich liczb jest $O(n).$ Ich posortowanie wymaga $|O(n$ porównań, zaś jedno porównanie zajmuje czas $|O$ Zatem pierwsza faza działa w czasie $O$

Kiedy mamy już uporządkowany ciąg i wiemy, że jedna z tych liczb jest wynikiem, to możemy wykonać w tym ciągu wyszukiwanie binarne - drugą fazę rozwiązania. Załóżmy, że w kroku algorytmu sprawdzamy, czy wynik jest nie większy niż $w.$ Zatem chcemy dowiedzieć się, czy istnieje podział ciągu na co najwyżej $k |$ liczb nie większych niż $|w.$ W tym celu będziemy dokonywali podziału od lewej do prawej. W każdym kroku zachłannie wybieramy największą możliwą liczbę. Jeśli liczba tworzona przez $|dx$ kolejnych cyfr jest nie większa niż $|w,$ to dodajemy ją do podziału. W przeciwnym przypadku dodajemy liczbę o jeden krótszą. Jeśli po $|k$ krokach wykorzystamy wszystkie cyfry, to znaleźliśmy podział o wyniku co najwyżej $w.$

Algorytm wyszukiwania binarnego wykona $O(log(n)) |$ kroków. W każdym kroku przechodzimy po całym ciągu, co zajmuje $O(n) |$ operacji. Zatem druga faza działa w czasie $O(n$ a w całym rozwiązaniu wykonuje się $|O$ operacji.

Rozwiązanie $|O$
Spróbujmy przyspieszyć pierwszą fazę poprzedniego rozwiązania. W tym celu wykorzystamy słownik podsłów bazowych, którego konstrukcja wymaga $|O(n$ operacji. Za pomocą tej struktury danych możemy w czasie $|O(1)$ porównać leksykograficznie dwa podsłowa, co jest równoważne porównaniu wartości liczbowych przez nie reprezentowanych. A więc pierwszą fazę rozwiązania wykonujemy w czasie $O(n |$

Wersja trudniejsza - cyfry na okręgu
Dla ambitnych Czytelników proponujemy trudniejszą wersję zadania - cyfry są ułożone na okręgu, który możemy rozciąć w dowolnym miejscu. Przedstawimy krótki zarys rozwiązania. Zduplikujmy ciąg $|S,$ sklejając dwie jego kopie. W ten sposób każde podsłowo długości $n$ opisuje jakąś rotację cykliczną $|S.$ Wynik będziemy wyszukiwali binarnie (jak w poprzednim rozwiązaniu). W każdym kroku, dla każdej pozycji wyznaczamy najdalszą pozycję na prawo, gdzie może zaczynać się kolejna liczba. Jeśli pozycje zinterpretujemy jako wierzchołki, a przejścia do kolejnych liczb jako krawędzie, to otrzymamy graf acykliczny. Pytamy, czy w takim grafie istnieje $|k$ -krawędziowa ścieżka, która pokrywa $n$ liter. Można to sprawdzić metodą skoków potęgami dwójki.