Podczas rekrutacji, moglibyśmy trafić na następujące zadanie:
W linii prostej znajduje się n pól. Na każdym polu znajduje się pewna liczba całkowita. Na polu z numerem pierwszym znajduje się pionek. Pionek może poruszać się po planszy w prawą stronę, ale w każdym kroku nie może poruszyć się o więcej niż k pól. Jaka jest możliwie najmniejsza suma liczb na drodze pionka od pola pierwszego do pola n-tego?
W jaki sposób podejść do takiego zadania? Zacznijmy od pytań do rekrutera:
Kandydat: Jak duża może być wartość zmiennej k?
Rekruter: Zmienna k może być dowolna, sensowna: 1 <= k <= n.
Jest to bardzo dobre pytanie. Jeśli zmienna k byłaby ograniczona z góry przez niewielką stałą (np. 10) to zadanie stałoby się dużo prostsze (dlaczego – wytłumaczę później). Kolejne pytanie jakie można zadać:
Kandydat: Jak duże są liczby na polach?
Rekruter: Mieszczą się w 32-bitowej zmiennej całkowitej.
Pytanie nie tylko dało nam informację jakiego typu zmiennej potrzebujemy aby przechowywać liczby na polach, ale również jakiego typu zmiennej potrzebujemy do zapisania wyniku. Ewidentnie tutaj potrzebujemy zmiennej 64-bitowej. Osoby piszące w pythonie mogą nie zadawać tego pytania.
Kandydat: Czy mogę założyć, że plansza składa się co najmniej z jednego pola?
Rekruter: Tak.
Możemy zapunktować u rekrutera pokazując, że myślimy o przypadkach brzegowych. Jeśli odpowiedzią byłoby “nie”, to musielibyśmy się spytać jaka jest poprawna odpowiedź dla pustej planszy.
Zacznijmy od prostego programowania dynamicznego. Dla każdego 1 <= i <= n niech DP[i] oznacza najmniejszą sumę liczb na drodze pionka od pola pierwszego do pola n-tego. Aby policzyć DP[i] potrzebujemy się zastanowić jaka była długość ostatniego skoku pionka. Jeśli wynosiła ona j, to DP[i] = board[i] + DP[i-j] (najtańsze dojście od pola 1 do pola i – j plus skok z pola i – j na pole i). Gdzie board oznacza tablicę wejściową. Ponieważ jednak nie znamy wartości j, musimy sprawdzić jej wszystkie możliwe wartości i wybrać z nich minimum. Zatem DP[i] = board[i] + min (1 <= j <= k) DP[i-j].
Piękno programowania dynamicznego polega na tym, że tak łatwo się go implementuje:
long long pawn_cheapest_tour(const vector<int> &board, int k)
{
vector<long long> DP(board.size());
// Korzystam z założenia, że plansza ma co najmniej jedno pole.
DP[0] = board[0];
for (int i = 1; i < board.size(); i++)
{
DP[i] = DP[i-1];
for (int j = 2; j <= k and i - j >= 0; j++)
if (DP[i-j] < DP[i])
DP[i] = DP[i-j];
DP[i] += board[i];
}
return DP.back();
}Szybki debug programu mógłby wyglądać na przykład tak:
board = {1, 10, 100, 100, 1, 100, 1, 100, 100, 100, 1}
k = 3
DP[0] = 1
DP[1] = min{1} + 10 = 1 + 10 = 11
DP[2] = min{11, 1} + 100 = 1 + 100 = 101
DP[3] = min{101, 11, 1} + 100 = 1 + 100 = 101
DP[4] = min{101, 101, 11} + 1 = 11 + 1 = 12
DP[5] = min{12, 101, 101} + 100 = 12 + 100 = 112
DP[6] = min{112, 12, 101} + 1 = 12 + 1 = 13
DP[7] = min{13, 112, 12} + 100 = 12 + 100 = 112
DP[8] = min{112, 13, 112} + 100 = 13 + 100 = 113
DP[9] = min{113, 112, 13} + 100 = 13 + 100 = 113
DP[10] = min{113, 113, 112} + 1 = 112 + 1 = 113Złożoność algorytmu to oczywiście O(kn). Gdyby k było ograniczone z góry przez małą liczbę naturalną (np. przez 10) to algorytm działałby w czasie liniowym (stąd to pytanie do rekrutera na początku). Ponieważ jednak k może być ~O(n) to nasz algorytm działa w czasie ~O(n^2). Jest więc dużo miejsca na ulepszenia.
Zauważmy, że podczas wyszukiwania minimum w tablicy DP (wewnętrzna pętla for) wielokrotnie przeszukujemy te same elementy.
| 7 | 3 | 6 | 4 | 5 | 8 | |
| 3 | 6 | 4 | 5 | 8 | 9 |
Problem może nam się skojarzyć z kolejką priorytetową. Faktycznie – jeśli umielibyśmy usuwać elementy z kolejki priorytetowej, to moglibyśmy użyć jej do rozwiązania naszego problemu. Wprawdzie istnieją kolejki priorytetowe, w których możemy wykonać operacje delete, ale żadna z nich nie jest zaimplementowana w STLu. Możemy zaimplementować oczywiście własną kolejkę priorytetową, ale dużo łatwiej będzie skorzystać z STLowego multiseta (czyli zbalansowanego drzewa wyszukiwań binarnych).
long long pawn_cheapest_tour(const vector<int> &board, int k)
{
vector<long long> DP(board.size());
multiset<long long> priority_queue;
// Korzystam z założenia, że plansza ma co najmniej jedno pole.
DP[0] = board[0];
for (int i = 1; i < board.size(); i++)
{
if (i - k - 1 >= 0)
priority_queue.erase(priority_queue.find(DP[i-k-1]));
priority_queue.insert(DP[i-1]);
DP[i] = *priority_queue.begin() + board[i];
}
return DP.back();
}W pętli for teraz dodajemy nowy element do kolejki i usuwamy stary (w razie potrzeby). Element minimalny wyciągamy korzystając z metody begin(). Złożoność algorytmu wynosi O(n lg k) gdyż nasz multiset w każdej chwili ma nie więcej niż k elementów.
Oczywiście, że my zrobimy to lepiej 🙂 Popatrzmy jeszcze raz na podtablicę w której szukamy wartości minimum. Taką “przesuwającą się” w prawo podtablicę nazywamy czasem okienkiem.
| 7 | 3 | 9 | 4 | 6 | 8 | |
| 3 | 9 | 4 | 6 | 8 | 5 |
Popatrzmy najpierw na górną podtablicę. Minimalną wartością w tej podtablicy jest wartość 3. Za chwilę okienko będziemy przesuwać w prawo. Zastanówmy się które wartości mają szansę stać się minimum po przesunięciu. Widzimy, że 9-tka nigdy nie stanie się minimum. Dlaczego? Bo za nią stoi 6. A 6 jest mniejsze od 9-tki, zatem 9-tka nigdy nie zostanie najmniejszą wartością w podtablicy. Mówiąc ogólniej: liczba ma szansę zostać minimum w okienku wtedy i tylko wtedy, gdy wszystkie wartości w okienku na prawo od niej są od niej większe. Takimi wartościami są 3, 4, 6 oraz 8. Zauważmy również że z powyższej własności wynika, że ciąg tych wartości jest rosnący.
Ponieważ nie interesują nas wartości, które nie mają szansy stać się minimum – wystarczy, że zapamiętamy jedynie te, które taką szansę mają. Użyjemy do tego kolejki dwustronnej (bo będziemy chcieli usuwać wartości i z lewej i z prawej). Wyobraźmy sobie że poruszamy się okienkiem o jedno pole w prawo. W jaki sposób zmieni się nasza kolejka? Widzimy, że ciąg wartości, które mają szansę zostać minimum to teraz 3, 4 oraz 5. Zatem z kolejki musimy najpierw usunąć wszystkie wartości większe (dla uproszczenia usuńmy też te równe) od 5. Następnie dodajemy 5 do końca kolejki. Musimy jeszcze uwzględnić sytuację w której może się zdarzyć, że usuniemy 3 z tablicy (stanie się to w naszym przykładzie gdy pójdziemy z okienkiem o jeszcze jeden krok w prawo).
Ponieważ wartości na kolejce są posortowane, aby odczytać minimum, wystarczy że spojrzymy na pierwszy element z lewej. Dla uproszczenia, zamiast wartości (3, 4, 6 i 8) będziemy w kolejce pamiętać indeksy tych elementów w tablicy DP. Implementacja może wyglądać tak:
long long pawn_cheapest_tour(const vector<int> &board, int k)
{
vector<long long> DP(board.size());
deque<int> queue;
// Korzystam z założenia, że plansza ma co najmniej jedno pole.
DP[0] = board[0];
for (int i = 1; i < board.size(); i++)
{
// Usuwamy najmniejszy element (w razie potrzeby)
if (queue.size() > 0 and queue.front() == i - k - 1)
queue.pop_front();
// Usuwamy elementy z końca jeśli są one większe bądź równe DP[i-1]
while (queue.size() > 0 and DP[queue.back()] >= DP[i-1])
queue.pop_back();
// Wstawiamy element DP[i-1] do kolejki
queue.push_back(i-1);
DP[i] = DP[queue.front()] + board[i];
}
return DP.back();
}Przykładowy przebieg algorytmu wygląda następująco:
board = {1, 10, 100, 100, 1, 100, 1, 100, 100, 100, 1}
k = 3
DP[0] = 1
Iteracja 1
Okienko: [1]
Zawartość kolejki: [1]
DP[1] = 1 + 10 = 11
Iteracja 2
Okienko: [1, 11]
Zawartość kolejki: [1, 11]
DP[2] = 1 + 100 = 101
Iteracja 3
Okienko: [1, 11, 101]
Zawartość kolejki: [1, 11, 101]
DP[3] = 1 + 100 = 101
Iteracja 4
Okienko: [11, 101, 101]
Zawartość kolejki: [11, 101]
DP[4] = 11 + 1 = 12
Iteracja 5
Okienko: [101, 101, 12]
Zawartość kolejki: [12]
DP[5] = 12 + 100 = 112
Iteracja 6
Okienko: [101, 12, 112]
Zawartość kolejki: [12, 112]
DP[6] = 12 + 1 = 13
Iteracja 7
Okienko: [12, 112, 13]
Zawartość kolejki: [12, 13]
DP[7] = 12 + 100 = 112
Iteracja 8
Okienko: [112, 13, 112]
Zawartość kolejki: [13, 112]
DP[8] = 13 + 100 = 113
Iteracja 9
Okienko: [13, 112, 113]
Zawartość kolejki: [13, 112, 113]
DP[9] = 13 + 100 = 113
Iteracja 10
Okienko: [112, 113, 113]
Zawartość kolejki: [112, 113]
DP[10] = 112 + 1 = 113Niepokoić może trochę pętla while w pętli for. Zauważmy jednak, że w każdej iteracji pętli for dodajemy dokładnie jeden element do kolejki. Natomiast w każdej iteracji pętli while usuwamy jeden element. Ponieważ nie możemy usunąć więcej elementów niż dodaliśmy, pętla while nie może sumarycznie wykonać więcej operacji niż n (bo do kolejki dodajemy nie więcej niż n elementów; dodajemy ich n – 1 jeśli chcemy być dokładni). Zatem złożoność całego algorytmu to O(n).
I myk, rekrutacja na celujący zdana!
