SUBSQ - Editorial

editorial
, , , ,
1

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:

dp[i][m] = \sum_{j<i} dp[j][m-A_i] \text{ where } f(j,i)>\max(A_j,A_i)

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:

S=\{i,i-1,i-2\dots,l_i,l_{l_i},l_{l_{l_i}},\dots\}

Thus, the above recurrence can be rewritten as:

\begin{aligned} dp[i][m] = \sum_{j<i} dp[j][m-A_i]-\sum_{x\in S} dp[x][m-A_i] \\ \ \\ = \sum_{j\le l_i} dp[j][m-A_i]-\sum_{x\in S'} dp[x][m-A_i] \end{aligned}

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:

O(N+NM)\approx O(NM)

SOLUTIONS:

Editorialist’s solution can be found here.
Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes