TRAXORB - Editorial (Kodeathon 15.2)

general
,
1

PROBLEM LINK:

Practice

Contest

Author: Satyam Gupta

Tester: Pulkit Sharma

Editorialists: Satyam Gupta,Pulkit Sharma

DIFFICULTY:

MEDIUM

PREREQUISITES:

Maths, Combinatorics, Inclusion-Exclusion Principle

PROBLEM:

There are R types of orbs. There are equal number of orbs of all types.
Each orb is unique in itself. Count the no. of ways to choose k orbs that includes at least one orb from all R types.

EXPLANATION:

Count the no. of ways of choosing k orbs, such that there exists at least one type for which no orb is selected and subtract from the total no. of ways of choosing k orbs. To calculate this, use Inclusion-Exclusion Principle.
Initially, let answer=0 and then, to the answer:

i) Add no. of ways to select k orbs.

ii) Subtract no. of ways of selecting k orbs, where exactly one type exists for which no orb is selected.

iii) Add no. of ways of selecting k orbs, where exactly two types exist for which no orb is selected.

iv) Subtract no. of ways of selecting k orbs, where exactly three types exist for which no orb is selected.
… and so on.

So,

ans = \sum_{i=0}^{R} (-1)^i *\dbinom{R}{i} * \dbinom{n-(i*n/r)}{k}

Here is the pseudocode implementing the above said procedure

	y=n/r
	ans = 0
	
	for i=0 to r:
	
		if(i%2=1)
			ans = ans - ncr(r,i)*ncr(n-i*y,k)
		else
			ans = ans + ncr(r,i)*ncr(n-i*y,k)

     //ncr(a,b) calculates a choose b (Binomial Coefficient)
	
    return ans

Complexity of this solution:

Preprocessing for calculating factorials and modular inverse of factorials (used for computing ^nC_r ): O(100000)

Final complexity = O(R + 100000)

AUTHOR’S AND TESTER’S SOLUTIONS:

#include<iostream>
#include<cstdio>

using namespace std;

#define MOD 1000000007
#define ll long long int

ll fact[1001],ifact[1001];

ll modpow(ll base, ll exponent, int modulus=MOD)
{
    ll result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

ll modinv(ll x)
{
    return modpow(x,MOD-2);
}

void calc()
{
	fact[0]=fact[1]=ifact[0]=ifact[1]=1;

	for(int i=2;i<=1000;i++)
	{
		fact[i]=(fact[i-1]*i)%MOD;
		ifact[i]=(ifact[i-1]*modinv(i))%MOD;
	}
}

ll ncr(ll n,ll r)
{
    if(n<r) return 1;

	return (((fact[n]*ifact[n-r])%MOD)*ifact[r])%MOD;
}

int main()
{
	ll t,n,r,k,i,y,ans;

	calc();

	cin>>t;

	while(t--)
	{
		cin>>n>>r>>k;

		y=n/r;

		ans = 0;

		for(i=0;i<r;i++)
		{
			if(i&1)
				ans = ((ans - (ncr(r,i)*ncr(n - i*y,k))%MOD)+MOD)%MOD;
			else
				ans = (ans + (ncr(r,i)*ncr(n - i*y,k))%MOD)%MOD;

            printf("(%ld,%ld)\n",ncr(r,i),ncr(n - i*y,k));
		}
        cout<<ans<<endl;
	}

	return 0;
}
1 Like