GDSUB - Editorial

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

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

1 Like

#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

On my machine, this testcase causes your ā€œERROR CODEā€ to crash - hopefully this helps you debug :slight_smile:

1 Like

From where did you generated these testcases?

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

3 Likes

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

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

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

1 Like

thank you for this explanation

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!

#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

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

1 Like

Yes - fix the bug :stuck_out_tongue:

2 Likes

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

1 Like

thank you so much for this beautiful explanation

great explanation :heart:

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

This is gold!

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