Tags: DataStructure

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$
  • 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 tree
  • update(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