PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
SIMPLE
PREREQUISITES:
Dynamic Programming
PROBLEM:
You’re given an array A of integers. You may delete some of the elements so that each subsegment formed (that contains no deleted elements) is non-decreasing. Determine the number of ways to do so.
QUICK EXPLANATION:
Let dp[i] denote the number of ways to delete the elements among the first i elements of the array so that the conditions are satisfied. We can get a simple recurrence for dp[i] which can be computed in linear time.
EXPLANATION:
The first subtask has small constraints : n \le 20. Thus, we can iterate through all possible subsets of elements to delete and check whether each way is feasible. The complexity of this solution is O(2^{n} \cdot n) and this can pass the first subtask. However, to get the full 100 points, we need something much faster than that.
At first, this problem seems hard. However, once you have the idea of dp in mind, this problem becomes trivial.
Let dp[i] denote the number of ways to delete a set of integers so that the first i integers satisfies the conditions. Now, the base case dp[1] = 2 is trivial. (since we can choose to delete it or keep it) It remains to see how we can calculate dp[i + 1] from dp[i].
There are two cases : We either delete a[i + 1] for keep a[i + 1]. If we delete a[i + 1], then the number of ways will be increased by dp[i], since we’ve already reduced it to solving the same problem on the first i elements. On the other hand, if we choose to keep a[i + 1], then we have two more cases :
- If a[i] \le a[i + 1]. In this case, we again reduce the problem to solving it on the first i elements. So, we add dp[i] to the answer.
- If a[i] > a[i + 1], then we must delete a[i]. Now, we only need to solve it on the first i - 1 elements, so we add dp[i - 1] to the answer. (we let dp[-1] = 1)
The answer can be found as dp[n]. This solution takes O(n) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.