GDSUB - Editorial (Unofficial) - Dynamic Programming Steps Demonstrated

Let’s analyse the constraints of the problem and the demands of the problem.

We are given N prime numbers - all less than 8000. (Example: 3 3 2 7 2 5 5).
We are required to generate sets such that

  1. Each element of a set is unique. (Example: {2}, {2,3}, {7,5,2} etc.)
  2. The number of elements of a set doesn’t exceed K.
    For the output, we are required to give a count of those sets.

Let’s simplify the problem:
Step 1: Elements of the set (i.e. prime numbers) are less than 8000. There are precisely 1007 such candidates.
Step 2: Given the fact that there are only 1007 candidate elements and that each element of our candidate set has to be unique, the MAXIMUM size of a candidate set is only 1007. If it’s more than 1007, it means that one of the numbers will have to repeat.

Given this understanding, we can simplify the problem into:
Input: 1007 elements present 0 or more times.
Output: Total number of sets that are generatable with size capped at K. Here, if K is greater than 1007, we only need to look at size capped at 1007.

Now, the fun part - doing it in terms of Dynamic Programming. Let’s take the example described earlier: (Example: 3 3 2 7 2 5 5)

It can be rewritten as 2 2 3 3 5 5 7. That is (2 repeated 2 times) (3 repeated 2 times) (5 repeated 2 times) and (7 repeated once).

In this case, the minimum size of the set can be 0 (Empty set). Maximum size can only be 4 (irrespective of the value of k).

So if k is 0: Number of possible sets is 1.
What if k is 1: We can either select 2 or 3 or 5 or 7 as our sole element. There are 2 ways to select 2, 2 ways to select 3, 2 ways to select 5, and 1 way to select 7. The total number of ways is 7. Here is how things look like when k is 1:


What if k is 2? Here is where things get interesting since recurrence is established.

Let’s consider the first one element (2), is it possible to generate a set of two elements with it? Ans: No. {2,2} is an invalid set. Here is what the table looks like now:


What if we consider the first two elements (2,3). Can we construct a set with 2 elements? Yes! How do we do that?
Step 1: Take all sets with one element {2}. There are “Two such sets”. Refer to Second Row, First Column.
Step 2: To all the above sets, add a {3}. How many ways to do it? There are 2 “3” in the input. So there are two ways to do it.
Step 3: Thus, there are 2 starting sets from step 1, and we can add 3 in 2 ways from step 2. Total possible sets with 2 elements 2,3 are 4. Recurrence will become more clear as we proceed with this exercise

Here is what the DP table looks like:

Next, is it possible to construct a two-element set with 2,3,5? (This set MUST contain a five or else it becomes a repetition of the previous case) Yes! In how many ways?
Step 1: Select either a 2 or a 3. This can be done in 2+2 ways. These 2+2 ways can be obtained as the sum of the first and the second column in the first row.
Step 2: Select a 5. This can be done in 2 ways.
Step 3: Obtain total possible sets as the product of step 1 and 2. That is 4*2 = 8 ways.
Here is what the table looks like now:

Now to the final step with k = 2. We are to construct a two-element set with 2,3,5,7 such that it necessarily contains 7.
Step 1: There are 2+2+2 ways (6 ways) to select one element from 2,3,5
Step 2: There is one way to select the 7.
Step 3: Total sets = 6*1 = 6

Our table looks like

Let’s take a pause here.

  1. There is exactly one way to generate a null set.
  2. There are 2+2+2+1 ways to generate a set with one element. 7 ways.
  3. There are 0+4+8+6 ways to generate a set with two elements. 18 ways.

So if k = 2. If the maximum number of elements was 2, we could have generated 1+7+18 sets. 26 sets!

What if k was 3?
Our table looks like

Explanation: We cannot generate three-element sets from just 2 and 3. But if we are given 2, 3, 5 - we can take two-element set containing 2 and 3 (total 4 in number from row 3 column 2) and multiply it with the number of possible ways to introduce 5 (2 ways). This becomes 4*2 = 8.
Similarly, we can generate three-element sets with 2,3,5,7 that necessarily contains 7 in (4+8)*1 ways = 12 ways.

So if k was 3 we can generate an additional 20 sets. Yielding a total of (26+20) sets. 46 sets.

What if k was 4 or greater. In that case, we can generate additional sets containing all elements.

Our table looks like

If we are to find total elements. Add every call value except the first row and then add one to it to account for the null set. The answer becomes 53+1 = 54.

Let us get rid of the first row in our DP and then formulate the principle:


Here is the final DP formula:

  1. First row to contain frequency of elements. 2, 2, 2, 1 in this case.
  2. Starting second row, For any cell Cij, add all elements in previous row (i-1 row) until j-1 column and multiply it with C0j

Let me know if it’s not clear.
Here is the implementation:


Hey I implemented the solution in the same way but i’m getting TLE. I used Python.
Can please suggest any changes?
#Here is my code
N,K = list(map(int,input().rstrip().split(’ ‘)))
A = list(map(int,input().rstrip().split(’ ')))
Unique = []
D = {}
for a in A:
if D.get(a):
D[a] +=1
D[a] = 1
M = 1000000007
Dp = [[[0 for _ in range(len(Unique))],[0 for _ in range(len(Unique))]] for _ in range(K)]
t = 0
for i,_ in enumerate(Unique):
t += D[]
Dp[0][0][i] = D[
Dp[0][1][i] = t
res = 1+(Dp[0][1][len(Unique)-1])%M
for i in range(1,min(len(Unique),K)):
for j in range(i,len(Unique)):
Dp[i][0][j] = ((D[Unique[j]]%M)*((Dp[i-1][1][j-1]%M)))%M
Dp[i][1][j] = (Dp[i][1][j-1]%M+Dp[i][0][j])%M
res += Dp[i][0][j]%M

format your code or share a link


Hey, Just made some modifications it worked! ( I used modulo operator on every iteration in prevision solution it caused TLE. )

:+1: :+1: