CODEVITA -lazy student

general
#1

Problem description

There is a test of Algorithms. Teacher provides a question bank consisting of N questions and guarantees all the questions in the test
will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a
question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can’t solve the question he didn’t
practice. What is the probability that Codu will pass the test?

Constraints

0 < T <= 10000

0 < N, T <= 1000

0 <= M <= 1000

M,T <= N

Input Format
First line contains single integer T denoting the number of test cases.

First line of each test case contains 3 integers separated by space denoting N, T, and M.

Output
For each test case, print a single integer.

If probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is multiplicative inverse of x
under modulo 1000000007.

Test Case
Example 1

Input

1

4 2 1

Output

500000004

Explanation

The probability is ½. So output is 500000004.

#2

ac code for this problem-

import java.io.*;
public class Codevita
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int tc=Integer.parseInt(bu.readLine()),i,j,N=1000;
        long M=1000000007,ncr[][]=new long[N+1][N+1];
        ncr[0][0]=1;
        for(i=1;i<=N;i++)
        {
            ncr[i][0]=1;
            for(j=1;j<=i;j++)
                ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%M;
        }

        while(tc-->0)
        {
            String s[]=bu.readLine().split(" ");
            int n=Integer.parseInt(s[0]),t=Integer.parseInt(s[1]),m=Integer.parseInt(s[2]);
            long deno=ncr[n][t],num=deno,red=0;
            if(n-m<t) red=0;
            else red=ncr[n-m][t];
            num-=red;
            if(num<0) num=(num+M)%M;
            long g=gcd(num,deno);
            num/=g; deno/=g;
            sb.append(num*pow(deno,M-2,M)%M+"\n");
        }
        System.out.print(sb);
    }

    static long gcd(long a,long b)
    {
        long t;
        if(a<b) a=a^b^(b=a);
        while(b!=0)
        {
            t=b;
            b=a%b;
            a=t;
        }
        return a;
    }

    static long pow(long x,long y,long M)
    {
        if(y==0) return 1;
        long p=pow(x,y/2,M)%M;
        p=(p*p)%M;
        if(y%2==0) return p;
        else return (x*p)%M;
    }
}
2 Likes
#3

We can use this thought :
Probability_of_Passing = 1 - Probability_of_failing

Now to find Probability_of_failing use the following idea - In how many cases can i select T questions such that codu has not practiced any of them. The number of ways will be - (n-m)Ct…
so Probability_of_failing will be (n-m)C(t)/(n)C(t)…
You will need knowledge about multiplicative inverse and binary exponentiation to find out the final answer(to learn that watch Errichto’s video on youtube on the above mentioned topics)…
Thanks :slight_smile:

1 Like
#4

appreciate ur help.can u do it in c++?

#5

how will u calculate such big combinations?
i saw in internet 1000C500 is ridiculusly high.
like ~ 10^300

#6

You need to precompute the factorials

ll fact[N], invfact[N]; //Put N as given in constraint

ll modinv(ll k)
{
	return power(k, mod1-2, mod1);
}

void precompute()
{
	fact[0]=fact[1]=1;
	for(ll i=2;i<N;i++)
	{
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
	}
	invfact[N-1]=modinv(fact[N-1]);
	for(ll i=N-2;i>=0;i--)
	{
		invfact[i]=invfact[i+1]*(i+1);
		invfact[i]%=mod;
	}
}

ll nCr(ll x, ll y)
{
	if(y>x)
		return 0;
	ll num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}
1 Like
#7

was this the 5th question?

#8

Yes

1 Like
#9

thank you man. appreciate it.