GDSUB - Editorial

editorial
, , ,
13

Here is my solution Solution link
Credits: Vieta’s formula implementation

14

You can read it in this doc : fft_eng.pdf - Google Drive

1 Like
15

i used newton’s identities for symettric polynomial

16

Basically if x1,x2,x3…xn are no. of appearances of a1,a2,a3…an
it’s a SOP i.e 1+(x1+x2+x3…xn)+(x1x2+x2x3…) upto k terms taken together.
Right!

17

Aren’t you doing the same thing as the DP formula but in a different way?
If I am wrong can you please give a formal derivation on how you applied the vieta’s formula to the given problem as it is difficult to understand from the code, how you approached the problem.

18

@allenjv123
Here’s my approach using Polynomials.

Editorial

1 Like
19

Can someone tell me how we deduce this dp formula with a proof?

dp[i][j]=dp[i−1][j]+dp[i−1][j−1]⋅cnt[i]

Please do help, I am unable to sleep properly due to this!

2 Likes
20

I am demonstrating the DP in this post. Consider this 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: CodeChef: Practical coding for everyone

43 Likes
21

yes, this is the main observation!

22

The number of prime numbers in range [1, 8000] are 1007(10^3 approx). Let C[i] be the number of occurrences of the i-th prime number in the array. Now we have to calculate DP with parameters DP[position][count] - which is the number of good subsequences that we use prime numbers up to position-th and our subsequence contains exactly count prime numbers. If we are on state DP[position][count] we can do two things: do not use position-th prime number (and do DP[position+1][count] += DP[position][count]) or use position-th prime number (and do DP[position+1][count+1] += DP[position][count]*C[position], because you have C[position] of position-th prime number). Sum of the last row of the DP will be our required result. Also take modulo while calculating the DP and also while adding up the last row.

CODE

23

This is a great explanation. Extremely helpful for DP beginners like me.

1 Like
24

#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll dp[1010][1010]={0};
ll val[1010];
int main()
{
int n,k,i,x,j;
ll ans=1;
cin>>n>>k;
map<int,int> mp;
for(i=0;i<n;i++)
{
cin>>x;
mp[x]++;
}
i=1;
for(auto it=mp.begin();it!=mp.end();it++,i++)
{
dp[1][i]=((dp[1][i-1]%mod+(it->second)%mod)%mod)%mod;
val[i]=it->second;
}
int p=mp.size();

	for(i=2;i<=k;i++)
    for (j = i; j <= p; j++)
    {
        dp[i][j]=(dp[i-1][j-1]*val[j])%mod)+dp[i][j-1]%mod;
    }

    
for(i=1;i<=min(k,p);i++)
 ans=(ans+dp[i][mp.size()])%mod;
cout<<ans;

}
While calculating ans why we need to run loop till i<=min(k,p) where p is number of unique elements why we can’t loop till i<=k why its giving SIGSEGV error in two subtasks.
CORRECT CODE
https://www.codechef.com/viewsolution/27433263
ERROR CODE
https://www.codechef.com/viewsolution/27433297

1 Like
25

On my machine, this testcase causes your “ERROR CODE” to crash - hopefully this helps you debug :slight_smile:

1 Like
27

From where did you generated these testcases?

28

I usually write a testcase generator when solving a problem (scroll down to the --test part) :slight_smile:

3 Likes
29

CodeChef: Practical coding for everyone here is my solution and i am not getting what is wrong in the code,so anyone suggest plz.

30

There’s an integer overflow on line 78:

mat[i-1][j-1]*mat[0][j]

but even after fixing that, it’s still not right :confused:

Edit:

The two occurrences of

ans+=(mat[i][k]%MOD)

can also be made to overflow.

Edit2:

Read this :slight_smile: Simple Trick to Detect Integer Overflow (C/C++)

2 Likes
31

Yes I fixed the integer overflow issue here CodeChef: Practical coding for everyone
Thank you :slight_smile:

1 Like
32

thank you for this explanation

34

Can anyone help me with this, showing segmentation fault/runtime error. Here’s the code , I have commented it to make it a bit readable. Please help me out guys!