# Some SUBSFREQ solutions from AUG20A

Here are 16 solutions of SUBSFREQ from Division 1 of August 2020 challenge.

There are some common faults or strange pieces of style.

To calculate the C^n_r values, most of the solutions use code of the form

``````ll nCr(ll n, ll r, ll m=MOD)
{
if (r==0) return 1;
return (((fact[n]*mod_inv(fact[n-r]))%m)*mod_inv(fact[r]))%m;
}
``````

Since calculating mod_inv() is a bit expensive, might be better to say

``````ll nCr(ll n, ll r, ll m = MOD)
{
if (r==0)
return 1;
return fact[n]*mod_inv( fact[n-r]*fact[r]%m ) % m;
}
``````

There is a section where two arrays are initialized. The code looks like:

``````ll cm[n+3],rem[n+1];
for(int i=0;i<=n+1;i++)
{
cm[i]=rem[i]=1;
}
``````

This code writes outside the boundaries of array rem. But by good fortune, nothing too bad happens.

The main calculation is done in a loop

``````for (int i=1; i<=n; i++)
{
ll res=0,ans,sum=1;

for (int j=1; j<=mp[i]; j++)
{
ll tmp;
ans = nCr(mp[i],j);
tmp = ans;
sum += ans;
sum %= MOD;
cm[j] = (cm[j]*mod_inv(sum))%MOD;
ans *= cm[j];
ans %= MOD;
cm[j] = (cm[j]*(sum-tmp+MOD)%MOD)%MOD;
res += ans;
res %= MOD;
}
cout << res%MOD << " ";
}
cout << endl;
``````

All the solutions have something very similar. The line with several MODs is more complicated than necessary. Could just say

``````cm[j] = cm[j] * (sum-tmp+MOD) % MOD;
``````

Or since the (sum-tmp) expression is calculating the value of sum at the start of the loop, one could do â€śtmp=sumâ€ť at the start of the loop, and then

`````` cm[j] = cm[j] * tmp % MOD;
``````

There is an extra modulo operation in the output which is unnecessary.

https://www.codechef.com/viewsolution/36856764 hides the code in a poem using the C pre-processor.
https://www.codechef.com/viewsolution/36855439 and https://www.codechef.com/viewsolution/36795541 change variable names and add extra useless code to try to conceal their history.

It does look as though there is some sharing of detailed ideas.

4 Likes

You can even avoid any expensive inverse computations, if you precompute the inverses for all factorials. And that is possible in O(n) time.

Just compute the inverses of all numbers between 1 and n in O(n) using the method described here, and then compute the inverses of the factorials using the equivalence `factorial_inv(x) = factorial_inv(x-1) * inv(x)`.

Basically:

``````for (int i = 2; i <= n; i++) {
f[i] = f[i-1] * i % m;
inv[i] = m - (m / i) * inv[m % i] % m;
f_inv[i] = f_inv[i-1] * inv[i] % m;
}
``````

that modinv has been taken from from gfgâ€¦dunno abt the rest
tbh there are loads of people whose entire graphs would disappear if their long challenge ratings are removed from themâ€¦and i dont think we shd waste our time even thinking abt em(several of those 15 belong to that category)