Guide to Competitive Programming

After having discussed the basic concepts of dynamic programming, we are now ready to go through a set of problems that can be efficiently solved using dynamic programming. As we will see, dynamic programming is a versatile technique that has many applications in algorithm design.

The longest increasing subsequence of this array

Longest Increasing Subsequence:

The longest increasing subsequence in an array of n elements is a maximum-length sequence of array elements that goes from left to right, and each element in the sequence is larger than the previous element. For example, shows the longest increasing subsequence in an array of eight elements.

We can efficiently find the longest increasing subsequence in an array using dynamic programming. Let length(k) denote the length of the longest increasing subsequence that ends at position k. Then, if we calculate all values of length(k) where 0 ≤ k ≤ n − 1, we will find out the length of the longest increasing subsequence.

The values of the function for our example array are as follows:

length(0) = 1
length(1) = 1
length(2) = 2
length(3) = 1
length(4) = 3
length(5) = 2
length(6) = 4
length(7) = 2

For example, length(6) = 4, because the longest increasing subsequence that ends at position 6 consists of 4 elements.

To calculate a value of length(k), we should find a position i < k for which array[i ] < array[k] and length(i ) is as large as possible. Then we know that length(k) = length(i )+1, because this is an optimal way to append array[k]
to a subsequence. However, if there is no such position i , then length(k) = 1, which means that the subsequence only contains array[k].

Since all values of the function can be calculated from its smaller values, we can use dynamic programming to calculate the values. In the following code, the values of the function will be stored in an array length.

for (int k = 0; k < n; k++) {
length[k] = 1;
for (int i = 0; i < k; i++) {
if (array[i] < array[k]) {
length[k] = max(length[k],length[i]+1);
}
}
}

Dynamic Programming- Competitive programming

The resulting algorithm clearly works in O(n2) time.

Paths in a Grid:

Our next problem is to find a path from the upper-left corner to the lower-right corner of an n × n grid, with the restriction that we may only move down and right. Each square contains an integer, and the path should be constructed so that the sum of the values along the path is as large as possible.

As an example, shows an optimal path in a 5 × 5 grid. The sum of the values on the path is 67, and this is the largest possible sum on a path from the upper-left corner to the lower-right corner.

Assume that the rows and columns of the grid are numbered from 1 to n, and value[y][x] equals the value of square (y, x). Let sum(y, x) denote the maximum sum on a path from the upper-left corner to square (y, x). Then, sum(n, n) tells us the maximum sum from the upper-left corner to the lower-right corner.

For example, in the above grid, sum(5, 5) = 67. Now we can use the formula

sum(y, x) = max(sum(y, x − 1), sum(y − 1, x)) + value[y][x],

which is based on the observation that a path that ends at square (y, x) can come  either from square (y, x − 1) or from square (y − 1, x) (Fig. 6.3). Thus, we select the direction that maximizes the sum. We assume that sum(y, x) = 0 if y = 0 or x = 0, so the recursive formula also works for leftmost and topmost squares.

Since the function sum has two parameters, the dynamic programming array also has two dimensions. For example, we can use an array.

In this problem, it is also possible to calculate the dynamic programming values more efficiently in O(n log n) time. Can you find a way to do this?

int sum[N][N];
and calculate the sums as follows:
for (int y = 1; y <= n; y++) {
for (int x = 1; x <= n; x++) {
sum[y][x] = max(sum[y][x-1],sum[y-1][x])+value[y][x];
}
}

The time complexity of the algorithm is O(n2).

Knapsack Problems:

The term knapsack refers to problems where a set of objects is given, and subsets with some properties have to be found. Knapsack problems can often be solved using dynamic programming.

In this section, we focus on the following problem: Given a list of weights [w1,w2, . . . , wn], determine all sums that can be constructed using the weights.

For example, shows the possible sums for weights [1, 3, 3, 5]. In this case, all sums between 0 . . . 12 are possible, except 2 and 10.

For example, the sum 7 is possible because we can choose the weights [1, 3, 3].
To solve the problem, we focus on subproblems where we only use the first k weights to construct sums. Let possible(x, k) = true if we can construct a sum x using the first k weights, and otherwise possible(x, k) = false.

The values of the function can be recursively calculated using the formula possible(x, k) = possible(x − wk , k − 1) or possible(x, k − 1), which is based on the fact that we can either use or not use the weight wk in the sum. If we use wk , the remaining task is to form the sum x −wk using the first k −1 weights, and if we do not use wk , the remaining task is to form the sum x using the first k − 1 weights. The base cases are because if no weights are used,wecan only form the sum 0. Finally,possible(x, n) tells us whether we can construct a sum x using all weights.

Dynamic Programming photo

Dynamic Programming- Competitive programming Dynamic Programming- Competitive programming

Shows all values of the function for the weights [1, 3, 3, 5] (the symbol “” indicates the true values). For example, the row k = 2 tells us that we can construct the sums [0, 1, 3, 4] using the weights [1, 3].

Let m denote the total sum of the weights. The following O(nm) time dynamic programming solution corresponds to the recursive function: possible[0][0] = true;

for (int k = 1; k <= n; k++) {
for (int x = 0; x <= m; x++) {
if (x-w[k] >= 0) {
possible[x][k] |= possible[x-w[k]][k-1];
}
possible[x][k] |= possible[x][k-1];
}
}

It turns out that there is also a more compact way to implement the dynamic programming calculation, using only a one-dimensional array possible[x] that indicates whether we can construct a subset with sum x. The trick is to update the array from right to left for each new weight:

possible[0] = true;
for (int k = 1; k <= n; k++) {
for (int x = m-w[k]; x >= 0; x–) {
possible[x+w[k]] |= possible[x];
}
}

Note that the general dynamic programming idea presented in this section can also be used in other knapsack problems, such as in a situation where objects have weights and values and we have to find a maximum-value subset whose weight does not exceed a given limit.

From Permutations to Subsets:

Using dynamic programming, it is often possible to change an iteration over permutations into an iteration over subsets. The benefit of this is that n!, the number of permutations, is much larger than 2n, the number of subsets. For example, if n = 20, n! ≈ 2.4 · 1018 and 2n ≈ 106. Thus, for certain values of n, we can efficiently go through the subsets but not through the permutations.

As an example, consider the following problem: There is an elevator with maximum weight x, and n people who want to get from the ground floor to the top floor. The people are numbered 0, 1, . . . , n −1, and the weight of person i is weight[i ].

What is the minimum number of rides needed to get everybody to the top floor?

For example, suppose that x = 12, n = 5, and the weights are as follows:

• weight[0] = 2
• weight[1] = 3
• weight[2] = 4
• weight[3] = 5
• weight[4] = 9

In this scenario, the minimum number of rides is two. One optimal solution is as follows: first, people 0, 2, and 3 take the elevator (total weight 11), and then, people 1 and 4 take the elevator (total weight 12).

The problem can be easily solved in O(n!n) time by testing all possible permutations of n people. However, we can use dynamic programming to create a more efficient O(2nn) time algorithm. The idea is to calculate for each subset of people two values: the minimum number of rides needed and the minimum weight of people who ride in the last group.

Let rides(S) denote the minimum number of rides for a subset S, and let last(S) denote the minimum weight of the last ride in a solution where the number of rides is minimum. For example, in the above scenario rides({3, 4}) = 2 and last({3, 4}) = 5, because the optimal way for people 3 and 4 to get to the top floor is that they take two separate rides and person 4 goes first, which minimizes the weight of the second ride. Of course, our final goal is to calculate the value of rides({0 . . . n − 1}).

We can calculate the values of the functions recursively and then apply dynamic programming. To calculate the values for a subset S, we go through all people who belong to S and optimally choose the last person p who enters the elevator. Each such choice yields a subproblem for a smaller subset of people. If last(S \ p) + weight[p] ≤ x, we can add p to the last ride. Otherwise, we have to reserve a new ride that only contains p.

A convenient way to implement the dynamic programming calculation is to use bit operations. First, we declare an array pair<int,int> best[1<<N]; that contains for each subset S a pair (rides(S), last(S)). For an empty subset,
no rides are needed:

Dynamic Programming- Competitive programming

best[0] = {0,0};

Then, we can fill the array as follows:

for (int s = 1; s < (1<<n); s++) {
// initial value: n+1 rides are needed
best[s] = {n+1,0};
for (int p = 0; p < n; p++) {
if (s&(1<<p)) {
auto option = best[s^(1<<p)];
if (option.second+weight[p] <= x) {
// add p to an existing ride
option.second += weight[p];
} else {
// reserve a new ride for p
option.first++;
option.second = weight[p];
}
best[s] = min(best[s], option);
}
}
}

Note that the above loop guarantees that for any two subsets S1 and S2 such that S1 ⊂ S2, we process S1 before S2.

Thus, the dynamic programming values are calculated in the correct order.

Counting Tilings:

Sometimes the states of a dynamic programming solution are more complex than fixed combinations of values. As an example, consider the problem of calculating the number of distinct ways to fill an n ×m grid using 1×2 and 2×1 size tiles. For example, there are a total of 781 ways to fill the 4 × 7 grid, one of them being the solution.

The problem can be solved using dynamic programming by going through the grid row by row. Each row in a solution can be represented as a string that contains m characters from the set Dynamic Programming- Competitive programming. For example, the solution in consists of four rows that correspond to the following strings:

Dynamic Programming- Competitive programming

Suppose that the rows of the grid are indexed from 1 to n. Let count(k, x) denote the number of ways to construct a solution for rows 1 . . . k such that string x corresponds to row k. It is possible to use dynamic programming here, because the state of a row is constrained only by the state of the previous row.

A solution is valid if row 1 does not contain the character , row n does not contain the character  and all consecutive rows are compatible. For example, the rows Dynamic Programming- Competitive programming are compatible, while the rows Dynamic Programming- Competitive programmingand Dynamic Programming- Competitive programming are not compatible.

Since a row consists of m characters and there are four choices for each character, the number of distinct rows is at most 4m. We can go through the O(4m) possible states for each row, and for each state, there are O(4m) possible states for the previous row, so the time complexity of the solution is O(n42m). In practice, it is a good idea to rotate the grid so that the shorter side has length m, because the factor 42m dominates the time complexity.

It is possible to make the solution more efficient by using a more compact representation for the rows. It turns out that it suffices to know which columns of the previous row contain the upper square of a vertical tile. Thus, we can represent a row using only the characters Dynamic Programming- Competitive programming is a combination of the characters , Dynamic Programming- Competitive programming. Using this representation, there are only 2m distinct rows, and the time complexity is O(n22m).

As a final note, there is also a direct formula for calculating the number of tilings:

Dynamic Programming- Competitive programming

This formula is very efficient, because it calculates the number of tilings in O(nm) time, but since the answer is a product of real numbers, a problem when using the formula is how to store the intermediate results accurately.