Some SUBSFREQ solutions from AUG20A

john_smith_3 · August 20, 2020, 9:06pm

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.

CodeChef: Practical coding for everyone hides the code in a poem using the C pre-processor.
CodeChef: Practical coding for everyone and CodeChef: Practical coding for everyone 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.

afaxnraner · August 21, 2020, 4:09pm

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;
}

tamo11 · August 21, 2020, 10:16pm

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)