Informatyczny kącik olimpijski

Trzej znajomi

W tym odcinku omówimy rozwiązanie zadania "Trzej znajomi", które pojawiło się na drugim etapie XIII Młodzieżowej Olimpiady Informatycznej.

Zadanie. Trzej znajomi: Adam, Błażej i Cezary postanowili napisać ciąg $|n$ liczb naturalnych. Każdy z nich miał inny pomysł na ciąg. Adam chciał napisać ciąg $|a = (a1,a2,...,an),$ Błażej ciąg $|b = (b1,b2,...,bn),$ zaś Cezary ciąg $|c = (c1,c2,...,cn).$ Znajomi długo nie mogli dojść do porozumienia, dlatego postanowili zbudować nowy ciąg $|d = (d1,d2,...,dn).$ Ustalili, że na każdej pozycji wybiorą którąś ze swoich opcji, czyli $di∈ {ai,bi,ci}.$ Koledzy zgadzają się, że różnica pomiędzy największym a najmniejszym elementem ciągu $|d$ powinna być jak najmniejsza. Jaką najmniejszą różnicę może mieć ciąg $d?$

Rozwiązanie $|O$
Zacznijmy od rozwiązania, które generuje wszystkie możliwe ciągi $d.$ Takich ciągów jest $3n$ (wartość każdego z $n$ elementów można wybrać na $|3$ sposoby). Spośród wygenerowanych ciągów należy wybrać ten, który ma najmniejszą różnicę pomiędzy największym a najmniejszym elementem, oraz wypisać tę różnicę. Dla ustalonego ciągu $|d$ znalezienie najmniejszego i największego elementu można wykonać w czasie $O(n)$ (przeglądamy kolejne elementy, pamiętając najmniejszy oraz największy). Rozwiązanie działa w czasie $O(3n$

Obserwacja:
Zauważmy, że dla ustalonych całkowitych $x, y(x ⩽y)$ możemy w czasie $|O(n)$ sprawdzić, czy istnieje ciąg $d, |$ którego wartości elementów należą do przedziału $[x; | y].$ Warunkiem koniecznym i wystarczającym jest, aby dla każdego indeksu $|i(1 ⩽i ⩽ n)$ przynajmniej jeden z trzech elementów $|ai,bi,ci$ należał do $[x;y].$

Rozwiązanie $|O$
Niech $|m1$ i $m2 |$ oznaczają odpowiednio wartość najmniejszego i największego elementu w ciągach $a, | b$ i $c.$ Korzystając z powyższej obserwacji, wystarczy dla wszystkich par liczb całkowitych $|x$ i $y$ $|(m1$ sprawdzić, czy istnieje ciąg $|d,$ którego wartości należą do przedziału $|[x;y].$ Spośród poprawnych przedziałów należy wybrać ten o najmniejszej różnicy $y − x.$ Wszystkich przedziałów do sprawdzenia jest $O((m2$ Zatem rozwiązanie zajmuje czas $|O((m2$

Rozwiązanie $|O$
Niech $S$ będzie zbiorem wartości, które występują przynajmniej raz w ciągu $|a,b$ lub $c.$ Zauważmy, że wystarczy rozważać tylko takie przedziały $|[x; y],$ dla których $|x⩽ y$ oraz $x, y∈ S.$ Moc zbioru $S$ jest rzędu $|O(n)$ (co najwyżej $3n |$ różnych wartości może pojawić się w $a,b, c,$ ponieważ tyle jest w sumie elementów). Stąd do sprawdzenia mamy $|O(n2)$ przedziałów, zatem całkowita złożoność czasowa wynosi $|O(n3).$

Rozwiązanie $O |$
Okazuje się, że nie musimy sprawdzać wszystkich wyżej wymienionych przedziałów. Wystarczy, że dla każdego $x ∈S$ wyznaczymy takie najmniejsze $|y,$ że istnieje ciąg $d,$ którego wartości elementów należą do $|[x; y].$ Ustalmy $|x ∈S,$ dla którego szukamy najmniejszego $y.$ Następnie wartość $|y$ wyszukajmy binarnie w przedziale $|[x;max(S)].$ Rozwiązanie działa w czasie $O(n$

Rozwiązanie $|O$
Podobnie jak wyżej, dla każdego $x ∈ S$ wyznaczymy najmniejsze poprawne $y.$ W tym celu skonstruujemy ciąg $d,$ którego największy element będzie możliwie najmniejszy. Dla każdego $|di$ mamy trzech kandydatów $a ,b ,c. i i i$ Spośród nich wybieramy najmniejszego, który jest większy lub równy $x.$ Jeśli taki element nie istnieje, to znaczy, że nie istnieje ciąg $|d$ z minimalnym elementem $|x.$ W przeciwnym przypadku $|y = max(d1, d2,...,dn).$ Dla ustalonego $x$ wyznaczenie minimalnego $|y$ odbywa się w czasie $O(n),$ zatem całe rozwiązanie działa w czasie $|O(n$

Rozwiązanie $|O$
Każdy z elementów ciągów $a, b$ i $c$ opiszmy parą liczb: wartość i indeks. W ten sposób otrzymamy $3n$ par: $|(a1,1),(a2,2),...,(an,n),$ $|(b1,1),(b2,2),...,(bn,n),$ $(c1,1),$ $|(c2,2),...,(cn,n).$ Następnie posortujmy te pary rosnąco względem pierwszej współrzędnej, aby otrzymać ciąg $|(p1,q1),(p2,q2),...,(p3n,q3n).$ Zauważmy, że z ciągu $pi,...,p j$ (dla $|1⩽ i⩽ j⩽ 3n$ ) można wybrać $n$ elementów, które utworzą ciąg $d,$ jeśli $|{1,2,...,n} ⊆ {qi,qi+1,...,q j}.$ Innymi słowy, dla każdej pozycji (od $1$ do $|n$ ) musimy ustalić przynajmniej jeden element. Zatem chcemy znaleźć takie indeksy $i, j(1⩽ i⩽ j ⩽3n),$ że z $pi,...,p j$ można zbudować ciąg $|d$ oraz $|p − p j i$ jest minimalne. Wystarczy, że dla każdego $i$ od $|1$ do $|3n$ znajdziemy najmniejsze takie $| j⩾ i,$ że z elementów $|pi,...,pj$ można zbudować ciąg $|d.$ Do rozwiązania tego problemu wykorzystamy metodę gąsienicy. Na początku $|i = j = 1.$ Dopóki fragment $pi,...,p j$ nie pozwala stworzyć poprawnego ciągu, to zwiększamy $j$ o jeden. W przeciwnym przypadku przechodzimy do kolejnego $|i.$ W każdym kroku zliczamy liczbę wystąpień każdego indeksu na rozpatrywanym fragmencie oraz pamiętamy liczbę różnych indeksów, które występują przynajmniej raz. Jeśli ta wartość jest równa $|n,$ to wtedy rozpatrywany fragment tworzy ciąg $|d.$

Sortowanie działa w czasie $|O(n$ zaś faza szukania najkrótszych fragmentów dla każdego początku zajmuje czas $|O(n).$ Zatem całe rozwiązanie działa w czasie $O(n$