Omówienie zadań
Tygodnie treningu
Maksymalną liczbę tygodni uzyskamy zakładając, że drużyna wykonywała 1 trening tygodniowo, a zatem będzie ona równa liczbie treningów jakie przeprowadzili.
Minimalną liczbę tygodni uzyskamy zakładając, że drużyna wykonywała możliwie jak najwięcej treningów w ciągu tygodnia. Wiemy, że nie przeprowadzali więcej niż 1 treningu w ciągu dnia, a zatem jeżeli odbyli np. 3 treningi w poniedziałek to zajęło im to 3 tygodnie. Minimalna liczba tygodni treningu będzie zatem równa liczbie wystąpień najliczniejszego spośród dni tygodnia.
Złożoność czasowa: O(n)
Złożoność czasowa
Oznaczmy przez d stopień zagnieżdżenia pętli, zaś przez c maksymalny stopień zagnieżdżenia pętli. Początkowo ustawiamy d oraz c na 0. Następnie analizujemy po kolei k instrukcji.
W momencie kiedy trafiliśmy na instrukcję for zwiększamy wartość d o 1 i aktualizujemy wartość c = max(c, d). W momencie kiedy trafiamy na instrukcję end zmniejszamy wartość d o 1.
Po przeanalizowaniu wszystkich instrukcji mamy obliczony maksymalny stopień zagnieżdżenia pętli c i w zależności od jego wartości wypisujemy odpowiednią złożoność czasową.
Złożoność czasowa: O(k)
Ciąg rosnący
Tworzymy dwie tablice pomocnicze L i R. Komórka i-ta w tablicy L będzie przechowywała informację czy spójny podciąg od wyrazu 1 do wyrazu i-tego jest rosnący. Komórka i-ta w tablicy R będzie przechowywała informację czy spójny podciąg od wyrazu i-tego do wyrazu n-tego jest rosnący. Tablice te możemy utworzyć w czasie liniowym przechodząc nasz ciąg dwukrotnie, raz od lewej, a drugi raz od prawej strony.
Następnie przechodzimy przez wszystkie wyrazy naszego ciągu szukając wyrazu, który możemy zmienić. Będąc na i-tym wyrazie ciągu w pierwszej kolejności sprawdzamy czy wartości L[i - 1] i R[i + 1] są prawdziwe. Jeżeli, któraś z nich nie jest prawdziwa tzn. że ciąg z lewej lub prawej strony i-tego wyrazu nie jest rosnący i zmiana wyrazu nic nie da. W przeciwnym wypadku próbujemy zmienić wartość i-tego wyrazu. W tym celu sprawdzamy wszystkie wartości od A[i - 1] + 1 do A[i + 1] - 1. Jeżeli sprawdzana wartość jest różna od A[i] to znaleźliśmy rozwiązanie. Warto tutaj zauważyć, że dla każdego wyrazu sprawdzimy maksymalnie 2 wartości. Żeby nie rozpatrywać osobno pierwszego i ostatniego wyrazu ciągu, dla których nie mamy odpowiednio wyrazu poprzedniego i następnego, możemy wstawić na początku naszego ciągu wyraz o wartości 0, a na jego końcu wyraz o wartości 109+1.
Złożoność czasowa: O(n)
K-częsta liczba
Dla każdej liczby jaka występuje w ciągu chcemy obliczyć minimalne k, dla którego dana liczba jest k-częsta. Do tego celu potrzebujemy dwóch tablic pomocniczych. Tablica P na indeksie i będzie przechowywać ostatnie wystąpienie liczby i w naszym ciągu. Tablica D na indeksie i będzie przechowywać maksymalną odległość pomiędzy dwoma kolejnymi wystąpieniami liczby i.
Na początku tablicę P inicjalizujemy samymi 0. Ma to na celu zasymulowanie, że każda z liczb występuje tuż przed pierwszym wyrazem ciągu. Dzięki temu uwzględnimy w swoich obliczeniach również odległość od początku ciągu, aż do pierwszego wystąpienia liczby. Tablicę D również inicjalizujemy samymi 0.
Następnie przechodzimy po kolei przez wyrazy ciągu począwszy od 1 aż do n-tego. Będąc na i-tym wyrazie, którego wartością jest A[i], aktualizujemy maksymalną odległość D[A[i]] = max(D[A[i]], i - P[A[i]]) i zmieniamy ostatnie wystąpienie wartości i-tego wyrazu P[A[i]] = i.
Po przejściu całego ciągu musimy jeszcze zasymulować wystąpienie każdej liczby za ostatnim jego wyrazem, tak żeby w obliczeniach uwzględnić odległość od ostatniego wystąpienia danej liczby do końca ciągu. W tym celu przechodzimy całą tablicę D i dla każdego indeksu i wykonujemy aktualizację D[i] = max(D[i], n + 1 - P[i]). Jeżeli po tej aktualizacji, na dowolnym indeksie jest wartość k tzn. że znaleźliśmy szukaną liczbę k-częstą i jest nią liczba równa danemu indeksowi. W przeciwnym wypadku odpowiedzią będzie 0.
Złożoność czasowa: O(n)
Usuwanie palindromów
Zadanie można rozwiązać stosując podejście rekurencyjne. Zdefiniujmy sobie funkcję solve(l, r), która zwraca minimalną liczbę operacji jakie trzeba wykonać żeby usunąć fragment wyrazu od indeksu l do indeksu r. Jakich wyborów możemy dokonać wewnątrz funkcji?
Jeżeli litery na końcowych indeksach są takie same czyli s[l] = s[r] to możemy zredukować nasz problem do rozwiązania funkcji solve(l + 1, r - 1). W takim wypadku wiadomo, że po usunięciu fragmentu wyrazu od indeksu l + 1 do indeksu r - 1 pozostaną nam dwie litery, które na pewno utworzą palindrom. Takie podejście sugeruje nam również jakie powinny być warunki stopu. Jeżeli indeksy l i r spotkają się (np. dla fragmentu aba) albo wyminą (np. dla fragmentu aa) to nasza funkcja powinna zwrócić wartość 1.
Innym rozwiązaniem może być wybranie dowolnego indeksu i pomiędzy l a r i rozwiązanie podproblemów solve(l, i) + solve(i + 1, r).
Spośród tych wszystkich opcji powinniśmy oczywiście wybrać tę, która wymaga najmniejszej liczby operacji. Ponieważ wywołania rekurencyjne dla tych samych wartości parametrów mogą się powtarzać musimy dodać do naszego rozwiązania zapamiętywanie wyników cząstkowych.
Złożoność czasowa: O(długość(s)3)
RSS