Informatyczny kącik olimpijski

Piramida liczbowa i Żabka

Tym razem omówimy dwa zadania z zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

Zadanie (Piramida liczbowa). Julia postanowiła zbudować piramidę liczbową. Budowę rozpoczęła od wypisania swojego ulubionego $|n$ -elementowego ciągu $|an,$ który stanowił podstawę konstrukcji. Następnie, dla każdej pary sąsiednich liczb napisała nad nią większą z nich. Zauważmy, że każde kolejne piętro jest o jedną liczbę krótsze od poprzedniego. Naszym zadaniem jest obliczyć sumę elementów tej piramidy. Po prawej znajduje się przykład piramidy, której podstawę stanowi ciąg $(4,3,2,6,1).$

Rozwiązanie $|O$
Pierwszym pomysłem, który nasuwa się na myśl, jest wygenerowanie piramidy, która składa się z $n -n+1- 2$ liczb, a następnie zsumowanie tych wartości. Takie rozwiązanie działa w czasie $O(n2).$

Rozwiązanie $|O$
Zauważmy, że zbiór wartości, które występują w całej piramidzie, jest równy zbiorowi wartości, które występują w podstawie tej piramidy. Wynika to bezpośrednio z konstrukcji piramidy. W związku z tym dla każdego elementu w podstawie piramidy obliczymy, ile razy występuje on w piramidzie. Wybierzmy maksymalny element w podstawie (jeśli jest więcej niż jeden taki element, wtedy wybieramy dowolny z nich), oznaczmy go przez $|ai.$

Na rysunku zaznaczono elementy piramidy o wartości $ai.$ Pozostałe elementy tworzą dwie mniejsze piramidy. Jedna o podstawie $|(a1,a2,...,ai−1),$ druga zaś o podstawie $(ai+1,ai+2,...,an).$ Wartość $|ai$ występuje:

n(n + 1) i(i −1) (n −i)(n − i + 1) k = --------− ------- − ---------------- 2 2 2

razy w piramidzie (jest to rozmiar całej piramidy pomniejszony o rozmiar lewej oraz prawej piramidy). Suma wszystkich elementów w piramidzie to $k ⋅ai + L+ P ,$ gdzie $L$ jest sumą elementów lewej piramidy $|(a1,a2,...,ai−1),$ zaś $P$ jest sumą elementów prawej piramidy $|(a ,a ,...,a ). i+1 i+2 n$ Aby obliczyć $|L$ i $P ,$ wystarczy opisaną procedurę wywołać rekurencyjnie.

Pozostało nam jeszcze zastanowić się, jak znajdować numer maksymalnego elementu w przedziale. Oczywiście, możemy naiwnie przejrzeć cały przedział i wybrać maksimum. Niestety, wówczas otrzymamy rozwiązanie, które działa w czasie $O(n2).$ W celu przyspieszenia znajdowania maksimum w przedziale możemy wykorzystać drzewo przedziałowe, które w każdym węźle przechowuje dwie wartości: wartość największego elementu oraz numer tego elementu. Wówczas otrzymujemy rozwiązanie, które działa w czasie $|O(n$

Zadanie (Żabka). Żabka o imieniu Bajtuś znajduje się na kamieniu numer $a.$ Natomiast jej upragniona mucha znajduje się na kamieniu numer $|b.$ Żabka w jednym skoku z kamienia numer $|x$ może przemieścić się na kamień o numerze $|2x$ lub $2x + 1.$ Czy istnieje taka sekwencja ruchów, która pozwoli Bajtusiowi dotrzeć do muchy?

Na początku rozważmy trywialny przypadek. Jeśli $a = b,$ wtedy, oczywiście, Bajtuś dotarł już do muchy. Załóżmy zatem, że $a < b.$ W pierwszym skoku Bajtuś może skoczyć na kamienie numer $|2a$ oraz $2a +1,$ innymi słowy na kamienie o numerach całkowitych z przedziału $[2a;2a + 1].$ W drugim skoku Bajtuś może skoczyć na kamienie numer $|4a,4a + 1$ z kamienia numer $|2a$ oraz na kamienie numer $4a + 2,4a+ 3$ z kamienia numer $2a + 1.$ Zatem po wykonaniu dwóch skoków Bajtuś może znaleźć się na kamieniach o numerach całkowitych z przedziału $[4a;4a + 3].$

Obserwacja: Jeśli w $|i$ skokach Bajtuś może osiągnąć kamienie numer $[c;d],$ to po $|i + 1$ skokach może osiągnąć kamienie numer $|[2c;2d + 1].$

Dowód: Rozważmy dwa przypadki:

$i +1$ -wszy skok jest typu $(x 2x).$ Wówczas Bajtuś może osiągnąć kamienie numer $|2c,2c+ 2,...,2d.$
$i +1$ -wszy skok jest typu $(x 2x + 1).$ Wówczas Bajtuś może osiągnąć kamienie numer $2c +1,2c +3,...,2d + 1.$

Zatem każdy z kamieni numer $[2c;2d + 1]$ jest osiągalny przez Bajtusia po $| i + 1$ skokach.

Na podstawie powyższej obserwacji generujemy przedziały numerów kamieni, które są osiągalne przez Bajtusia w kolejnych skokach:

[8a; 8a+ 7], [16a;16a +15], [32a;32a + 31],....

Następnie sprawdzamy, czy istnieje przedział, którego początek jest nie większy niż $b$ oraz $b$ do niego należy.

Zauważmy, że numery początków kolejnych przedziałów rosną wykładniczo. Zatem rozwiązanie działa w czasie $O(log(b/a)).$