GDSUB - Editorial (Unofficial) - Dynamic Programming Steps Demonstrated

https://www.codechef.com/SEPT19B/problems/GDSUB

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:

|2|3|5|7|
|2|2|2|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:

|2|3|5|7|
|2|2|2|1|
|0|

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:
|2|3|5|7|
|2|2|2|1|
|0|4|

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:
|2|3|5|7|
|2|2|2|1|
|0|4|8|

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
|2|3|5|7|
|2|2|2|1|
|0|4|8|6|

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
|2|3|5|7|
|2|2|2|1|
|0|4|8|6|
|0|0|8|12|

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
|2|3|5|7|
|2|2|2|1|
|0|4|8|6|
|0|0|8|12|
|0|0|0|8|

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:

|2|2|2|1|
|0|4|8|6|
|0|0|8|12|
|0|0|0|8|

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: https://www.codechef.com/viewsolution/26659107

3 Likes

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
else:
Unique.append(a)
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
print(res%M)

format your code or share a link

Sure, https://www.codechef.com/viewsolution/34124740

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

:+1: :+1: