Motivation Problem
There are $N + 2$ blocks numbered from $0$ to $N + 1$. Given an array $A$ of integers of size $N$ and an integer $K$, where $A_i$ is the cost of stepping on $i$-th block. Calculate the minimum cost to go from position $0$ to ($N+1$) if we can only jump at most $K$ blocks.
Constraints:
- $1 \le A_i \le 10^9$
- $1 \le K \le N \le 10^6$
Related Algorithms & Data Structures
- Basic Data Structures (i.e. Stack and Queue)
- Dynamic Programming
- Segment Tree
First Approach
One of the naive approach is that we do a dynamic programming:
Iterate from $1$ to $N+1$, calculating the minimum value of the previous $K$ blocks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAXN = 1000010;
const long long MAX_VAL = 1e16;
long long minCost(int A[], int N, int K) {
long long answer[MAXN] = {};
for (int i = 1; i <= N + 1; ++i) {
answer[i] = MAX_VAL;
for (int j = 1; j <= K; ++j) {
if (i >= j) {
answer[i] = min(answer[i], answer[i - j] + A[i]);
}
}
}
return answer[N + 1];
}
The total complexity of this algorithm is $O(NK)$, so this will surely get Time Limit Exceeded. This solution is slow because of the time needed to calculate the minimum of $K$ previous elements. It takes $O(K)$, and of course we need to do better than $O(K)$.
Better Approach
We can improve the computation with a segment tree to reduce the total complexity to $O(N \log N)$.
Assume that:
query(l, r)
: get the minimum value of elements from $l$ to $r$ indices of the segment treeupdate(p, v)
: change the $p$-th element of the segment tree to $v$.
Now we can reduce the time for searching for the minimum of
1
2
3
4
5
6
7
8
9
10
11
12
13
const int MAXN = 1000010;
long long minCost(int A[], int N, int K) {
long long answer[1000010] = {}
for (int i = 1; i <= N + 1; ++i) {
answer[i] = A[i] + query(max(0, i - K), i - 1);
update(i, answer[i]);
}
return answer[N + 1];
}
Now the total complexity is $O(N \log N)$. To calculate the minimum of previous $K$ elements we only need $O(\log N)$.
This is good enough, but we can do better than $O(N \log N)$. We can solve the problem in $O(N)$ time using a monotonic queue with a sliding window technique.
What is a monotonic queue?
Monotonic queue is a data structure where the order of the elements is strictly increasing or strictly decreasing. For example a strictly increasing monotonic queue will be able to contain [1, 3, 5, 6, 7]
, but not [1, 1, 3, 5]
and [2, 1, 4, 5]
as the elements are not strictly increasing (1, 1
is not strictly increasing, and 2, 1
is decreasing).
To solve this problem, we will use a strictly increasing monotonic queue, that is, the first element of this monotonic queue will be the smallest element in the monotonic queue. Note that we can only jump at most $K$ blocks, so we need to make sure that we will not get over than $K$ blocks. We can handle it by using a pair of numbers instead of a single integer for the elements of the monotonic queue.
The pair is in the form of <int, int>
where the one of the element is the value and the other is the position where the value was added to the container. In order to achieve this we need a data structure that can be accessed from front and end, so in C++ we can use deque
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
long long minCost(int A[], int N, int K) {
deque<pair<long long, int> > q;
// <value, index>
q.push_back(make_pair(0, 0));
for (int i = 1; i <= N; ++i) {
// while the first element in deque
// cannot be used anymore
while (q.front().second < i - K) {
q.pop_front();
}
long long answer = A[i] + q.front().first;
while (!q.empty() && q.back().first >= answer[i]) {
q.push_back(make_pair(answer[i], i));
}
}
return q.front().first;
}
Problems that can be solved using Monotonic Queue:
Sources
- Topcoder Coding Contest - Single Round Match - University of Indonesia Problem 1000 points