Omówienie zadań
f(x)=ax+b
Pomimo tego, że zadanie nie jest trudne to należało bardzo uważać podczas implementacji żeby nie pominąć żadnego z przypadków. Poniżej wymieniamy przykłady tych najbardziej złośliwych:
- a = 0, b = 0 odpowiedź: f(x)=0
- a = 1, b = 0 odpowiedź: f(x)=x
- a = -1, b = 0 odpowiedź: f(x)=-x
- a = 0, b = 2 odpowiedź: f(x)=2
- a = 0, b = -2 odpowiedź: f(x)=-2
- a = 1, b = -2 odpowiedź: f(x)=x-2
- a = -1, b = 2 odpowiedź: f(x)=-x+2
Rozwiązanie sprowadza się do sprawdzenia serii warunków i w zależności od ich wyniku odpowiedniego wypisywania fragmentów wzoru. Zapraszam do zapoznania się z rozwiązaniem wzorcowym.
Złożoność czasowa: O(1)
Cyfry parzyste i nieparzyste
W zadaniu mamy policzyć ile jest liczb n-cyfrowych, dla których mamy określone pozycje cyfr parzystych i nieparzystych.
Na początek zajmijmy się przypadkiem, gdy n = 1. Zauważmy, że niezależnie od parzystości tej jedynej cyfry odpowiedzią jest 5.
Teraz rozpatrzmy przypadek, gdy n > 1. Zauważmy, że parzystość cyfr poza skrajnie lewą pozycją nie ma znaczenia. Na każdej z nich możemy ustawić 1 z 5 cyfr, a zatem wynik dla tego fragmentu analizowanej liczby to 5(n-1). Inaczej sprawa ma się z pierwszą cyfrą. Jeżeli pierwsza cyfra ma być nieparzysta to do wyboru mamy 1 z 5 cyfr. Jeżeli jednak pierwsza cyfra ma być parzysta to do wyboru mamy 1 z 4 cyfr, ponieważ na pierwszej pozycji nie może stanąć 0. Gdyby pierwszą cyfrą było 0, byłoby ono nieznaczące i tak naprawdę uzyskalibyśmy liczbę n-1-cyfrową. Podsumowując, gdy pierwsza cyfra jest nieparzysta odpowiedzią jest 5n, w przeciwnym wypadku odpowiedzią jest 4×5n-1.
Pozostaje nam kwestia policzenia reszty z dzielenia wyniku przez 109+7. Ponieważ n może być duże musimy liczyć resztę z dzielenia na bieżąco w pętli dla każdej analizowanej pozycji cyfry. Korzystamy tutaj z faktu, że:
(a × b) mod c = ((a mod c) × b) mod c.
Złożoność czasowa: O(tn)
YouTube
Zadanie to możemy potraktować jako zadanie grafowe. Filmy to wierzchołki grafu, zaś lista polecanych filmów to lista sąsiedztwa danego wierzchołka.
Załóżmy, że Janek rozpoczyna oglądanie od wyszukania filmu o numerze i. W jaki sposób możemy odpowiedzieć na pytanie ile maksymalnie filmów może obejrzeć zaczynając od i-tego? Najprostszym sposobem jest puszczenie przeszukiwania grafu wszerz (BFS) zaczynając właśnie od wierzchołka i. Odpowiedzią na pytanie będzie odległość do najdalszego wierzchołka osiągalnego z i powiększona o 1.
Ponieważ w zadaniu nie mamy określonego, od którego filmu Janek zaczyna oglądanie dlatego przeszukiwanie grafu wszerz musimy wykonać dla każdego z wierzchołków, a następnie spośród uzyskanych odpowiedzi wybrać maksymalną.
Złożoność czasowa: O(n(n+m))
Uwaga! Zadanie to można rozwiązać w zdecydowanie lepszej złożoności czasowej O(n+m). Czy wiesz jak?
Zamiana liter
Było to najtrudniejsze zadanie w całym zestawie. Rozwiązanie naiwne to oczywiście wyszukanie dla każdego zapytania n1-go wystąpienia 1 litery i n2-go wystąpienia 2 litery i ich zamiana. Takie rozwiązanie ma złożoność O(qn), co przy maksymalnej liczbie zapytań q równej 105 oraz maksymalnej długości wyrazu n równej 106 oznacza, że jest ono zdecydowanie za wolne.
Wiemy, że nie mamy żadnego wpływu na liczbę zapytań dlatego przyspieszenia musimy poszukać w części algorytmu odpowiedzialnej za wyszukiwanie k-tego wystąpienia wybranej litery.
Skupmy się na problemie szybkiego znajdowania k-tego wystąpienia litery A, ponieważ mając rozwiązania dla jednej litery, tak naprawdę mamy rozwiązanie dla całego alfabetu. Wystarczy po prostu powielić rozwiązanie dla pozostałych liter. Do rozwiązania naszego problemu użyjemy drzewa pozycyjnego. Jest to struktura danych, która reprezentuje zbiór liczb całkowitych. Liczby te muszą się jednak zawierać w pewnym określonym przedziale, w naszym wypadku będzie to przedział [0, n). Umożliwia ona dodawanie albo usuwanie wystąpień dowolnej liczby z tego przedziału, a także wyszukanie k-tej najmniejszej liczby jaką przechowuje.
Jak wygląda takie drzewo?
Korzeniem drzewa jest wierzchołek o numerze 1, który odpowiada za pełny przedział liczb czyli [0, n). Przechowuje on informację ile wystąpień liczb z tego przedziału znajduje się w zbiorze. Jego potomkami są wierzchołki o numerach 2 i 3. Wierzchołek 2 odpowiada za przedział [0, (0 + n) / 2), zaś wierzchołek 3 odpowiada za przedział [(0 + n) / 2, n). Analogicznie jak wierzchołek 1 przechowują one informację ile wystąpień liczb z reprezentowanych przez nie przedziałów znajduje się w zbiorze. Potomkami wierzchołka numer 2 są wierzchołki o numerach 4 oraz 5, zaś wierzchołka numer 3 są wierzchołki o numerach 6 oraz 7 i tak dalej aż do wierzchołków będących liśćmi. Uogólniając wierzchołek o numerze x odpowiadający za przedział [l, r) będzie miał dwóch potomków. Pierwszy z nich to wierzchołek o numerze 2x odpowiadający za przedział [l, (l + r) / 2), zaś drugi to wierzchołek 2x + 1 odpowiadający za przedział [(l + r) / 2, r). Jeżeli l + 1 = r tzn., że mamy do czynienia z wierzchołkiem, liściem, odpowiadającym za przedział 1-liczbowy i nie będzie miał on potomków.
Jak dodajemy/usuwamy wystąpienia liczby w zbiore?
Żeby dodać b wystąpień liczby a w zbiorze przechodzimy ściężkę od korzenia drzewa, czyli wierzchołka o numerze 1 odpowiadającego za pełny przedział [0, n), aż do wierzchołka liścia odpowiadającego za przedział [a, a + 1). Na każdym z odwiedzonych wierzchołków zwiększamy liczbę wystąpień liczb z reprezentowanego przez niego przedziału o b, bo tyle wystąpień dodajemy. Usuwanie realizujemy identycznie jak dodawanie. Po prostu liczba wystąpień jaką dodajemy jest ujemna. Zauważmy, że każdy kolejny wierzchołek reprezentuje przedział o połowę mniejszy od poprzedniego. W związku z tym wiemy, że odwiedzimy maksymalnie log2(n) wierzchołków.
Jak wyszukać k-tą najmniejszą liczbę w zbiorze?
Podobnie jak w przypadku dodawania/usuwania wystąpień będziemy przechodzić ścieżkę od korzenia aż do liścia. Jeżeli jesteśmy na wierzchołku x, który nie jest liściem to sprawdzamy, na którego z jego potomków powinniśmy przejść. Jeżeli aktualna wartość k jest mniejsza bądź równa liczbie wystąpień przechowywanej na wierzchołku 2x to przechodzimy na niego. W przeciwnym wypadku przechodzimy na wierzchołek 2x + 1 jednocześnie zmniejszając wartość naszego k o liczbę wystąpień z wierzchołka 2x. W końcu dochodzimy do liścia odpowiadającego za przedział 1-liczbowy. k-tą najmniejszą liczbą w zbiorze jest ta, której przedział reprezentuje nasz znaleziony liść. Zauważmy, że podobnie jak w przypadku poprzedniej operacji tutaj też odwiedzimy tylko log2(n) wierzchołków żeby odnaleźć k-tą najmniejszą liczbę. Jest to potężne przyspieszenie w porównaniu z odwiedzieniem n wierzchołków w rozwiązaniu naiwnym.
Jak zastosować drzewo pozycyjne w naszym zadaniu?
Tworzymy drzewo pozycyjne dla każdej litery alfabetu. Do drzewa będziemy wstawiać indeksy, na których dana litera występuje. W momencie kiedy mamy zamienić n1 wystąpienie litery 1 z n2 wystąpieniem litery 2 wykonujemy poniższe operacje:
- Znajdujemy n1 najmniejszą liczbę w drzewie litery 1, czyli tak naprawdę wyszukujemy indeks n1 wystąpienia. Znalezioną liczbę oznaczmy jako a.
- Znajdujemy n2 najmniejszą liczbę w drzewie litery 2, czyli tak naprawdę wyszukujemy indeks n2 wystąpienia. Znalezioną liczbę oznaczmy jako b.
- W drzewie litery 1 usuwamy jedno występienie liczby a i wstawiamy jedno wystąpienie liczby b. Innymi słowy oznaczamy, że litera 1 nie występuje już na indeksie a, ale występuje na indeksie b.
- W drzewie litery 2 usuwamy jedno występienie liczby b i wstawiamy jedno wystąpienie liczby a. Innymi słowy oznaczamy, że litera 2 nie występuje już na indeksie b, ale występuje na indeksie a.
W ten sposób obługujemy wszystkie zamiany, każdą w czasie logarytmicznym. Po dokonaniu zamian wystarczy odczytać z każdego drzewa, na jakich indeksach występują poszczególne litery i zbudować nowy wyraz.
Złożoność czasowa: O(q log2(n))
Prawie jak Fibonacci, prawie
Było to najprostsze zadanie w całym zestawie. Wybieramy każdą trójkę elementów stojących obok siebie. Następnie zliczamy w ilu z tych trójek suma dwóch pierwszych elementów od lewej strony jest równa trzeciemu. Zadanie można rozwiązać w następujący sposób. W pierwszej kolejności wczytujemy wszystkie elementy do tablicy albo wektora. Następnie przechodzimy tablicę w pętli zaczynając od indeksu i równego 2 aż do n-1. Będąc na indeksie i sprawdzamy czy suma elementów na indeksach i-2 oraz i-1 jest równa elementowi i.
Złożoność czasowa: O(n)
Posortuj Euklidesa
W zadaniu tym należało zaimplementować dowolny algorytm sortujący o złożoności O(n log2(n)) albo lepszej. Można też było skorzystać z gotowych funkcji sortujących dostępnych w językach programowania. Jedyna różnica polega tutaj na niestandardowej kolejności elementów. Porównując dwie liczby w pierwszej kolejności musieliśmy wziąć pod uwagę wartość największego wspólnego dzielnika danych liczb z liczbą 1260, a dopiero w przypadku identycznych wartości NWD elementy były sortowane niemalejąco. Największy wspólny dzielnik można było obliczyć za pomocą algorytmu Euklidesa albo skorzystać z gotowej funkcji dostępnej w języku programowania.
Złożoność czasowa: O(n log2(n))
RSS