GDSUB - Editorial

editorial
, , ,
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!

35 
#define mxf 1010
...
int pf[mxf] = {};   //pf array to store frequency of all primes present
...
   cin>>a;
   pf[a] += 1; //increasing frequnency of prime 'a'

From the Problem Constraints, a can be as high as 8000.

2 Likes
36

such stupidity from my side lol, thanks bro for pointing this out. Is there anything i should look to change?

1 Like
37

Yes - fix the bug :stuck_out_tongue:

2 Likes
38

finally it worked,Thanks bro! also dont’ sell all your players to liverpool pls :stuck_out_tongue:

1 Like
39

thank you so much for this beautiful explanation

40

great explanation :heart:

41

why haven’t we filled default values for dp[0][i] where 1<= i <= max(k, 1007) ?
if we don’t do this how can we access dp[i - 1][j - 1] for i = 1 and j = 2

42

This is gold!

43

Why do we add last row of the dp???

44

can anyone explain , why order of subseqence doesn’t matter, and we can take subsets directly ?