# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

Monotonic Stack, DP

# PROBLEM:

Given an array A of N distinct positive integers. Determine for each k, the number of subsequences (A_{i_1}, A_{i_2},\dots,A_{i_p}) such that:

- \sum A_{i_x} = k, and
- f(i_x, i_{x+1}) > \max(A_{i_x}, A_{i_{x+1}}) for all valid x, where f(l, r)=\max(A_l, A_{l+1},\dots,A_r).

# EXPLANATION:

**Note:** A subsequence (A_{i_1}, A_{i_2},\dots,A_{i_p}) is considered *valid* if f(i_x, i_{x+1}) > \max(A_{i_x}, A_{i_{x+1}}) holds for all valid x.

We start with the straighforward (naive) DP solution.

Let dp[i][m] represent the number of *valid* subsequences of A[..i] **that includes** element A_i, and sums to m. The recurrence is then as follows:

with the base case dp[0][0]=1.

This solution has a time complexity of O(N^2M), too slow to pass the final subtask.

However, we can optimise!

Let l_i represent the greatest x<i such that A_x>A_i. This can be determined in O(N) using a monotonic stack. Then it is easy to see that the only values of j<i where f(j, i)\le\max(A_j,A_i) are:

Thus, the above recurrence can be rewritten as:

where S'=\{l_i,l_{l_i},l_{l_{l_i}},\dots\}.

Both terms on the RHS of the above equation can be computed efficiently by maintaining a running sum over their previous values!

The final answer for each m is then \sum dp[i][m] over all valid i.

# TIME COMPLEXITY:

Computing array l takes O(N). Computing each state of the DP is done in O(1). Since there are N\cdot M states, the total time complexity is:

# SOLUTIONS:

Editorialistâ€™s solution can be found here.

Authorâ€™s solution can be found here.

Testerâ€™s solution can be found here.