Some SUBSFREQ solutions from AUG20A

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

https://www.codechef.com/viewsolution/36610046
https://www.codechef.com/viewsolution/36613151
https://www.codechef.com/viewsolution/36663995
https://www.codechef.com/viewsolution/36770084
https://www.codechef.com/viewsolution/36795541
https://www.codechef.com/viewsolution/36800384
https://www.codechef.com/viewsolution/36826369
https://www.codechef.com/viewsolution/36830995
https://www.codechef.com/viewsolution/36837681
https://www.codechef.com/viewsolution/36852053
https://www.codechef.com/viewsolution/36853501
https://www.codechef.com/viewsolution/36853887
https://www.codechef.com/viewsolution/36855439
https://www.codechef.com/viewsolution/36855997
https://www.codechef.com/viewsolution/36856764
https://www.codechef.com/viewsolution/36857970

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)