PROBLEM LINK:
Author: Jaymeet Mehta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic Combinatorics, Probability, Modular Multiplicative Inverse
PROBLEM:
You need to calculate the probability of making team of K fighters from N fighters on given condition(Fighters from Universe 7 > Fighters from Universe 6) by asking 2 types of queries,
- Type 1 : At most n-1 times, Query is defined as, for i & j grader replies with if both fighters are from same universe or not
- Type 2 : Only once,Query is defined as, for any index i grader replies with the Universe of i^{th} fighter
The probability can be represented as P/Q you have to calculate P*Q^{-1} mod (10^9+7), Where Q^{-1} is the modular multiplicative inverse of Q (mod (10^9+7))
QUICK EXPLANATION:
- Ask Type 2 query to get the universe of one fighter.
- Based on the already found universe of the fighter we can get the Universe other fighters from Type 1 Query by asking it exactly N-1 times from which we can use counts of the universes.
- Find the probability of having fighters from Universe 7 > fighters from Universe 6 in the team of K fighters from total N fighters
EXPLANATION:
About Interaction, to find probability we need Counts of fighters from each universe.
Consider the count of fighters from Universe 7 as uni7 and count of fighters from universe 6 as uni6.
- We know that the second type of query gives the Universe of the fighter,so we can find the universe of fighter 1 by giving query as F 1 and increase the count of the given universe i.e if the Universe is 7 then increase uni7 and vice-versa for uni6.
- Now we can ask the Type 1 queries as Q 1 i (2\leq i \leq N) if we get response as same universe we increase the count of the universe of 1^{st} fighter, if not we increase the count of the inverse universe of 1^{st} fighter.
After we have processed all queries we have uni7 and uni6.
Now we have to calculate probability.
We need to select K fighter from total N fighters so we can write denominator Q = n\choose k
Calculation of Numerator:
Consider we select i fighters from uni7 so we have to select k-i fighters from uni6.
So we have to select upper and lower bound of i to calculate the probability.
Calculation of Lower Bound
We want uni7 > uni6 So we can compute lower bound like below.
i > k- i
2*i > k
i > k/2
From above proof we can choose i from k/2 + 1, but what if we don’t have enough fighters from uni6 to satisfy k-i ?
So, we can define the lower bound as max(floor(k/2)+1,k-uni6).
Calculation of Upper Bound
As we want at least 1 fighter from each Universe we can go upto k-1, But what if we don’t have enough fighters from uni7 to get i fighters from uni7.
So, we can define the lower bound as min(uni7,k-1).
From Above proofs we can define the numerator.
P=\sum_{i=max(int(k/2)+1,k-uni6)}^{min(uni7,k-1)} uni7\choose i*uni6\choose k-i \bmod m where m=10^9+7.
We have P and Q and the required probability is in the form of P*Q^{-1} mod (10^9+7).
Since m=10^9+7 is prime, we can use Fermat’s little theorem to calculate Q^{-1}
Hence, Q^{-1} \bmod m \equiv Q^{m-2} \bmod m .
Therefore, the required probability will be (P * (Q^{m-2} \bmod m ) \bmod m).
Implementation Tips
We got the probability,
We are multiplying every combination to calculate P for that we can use Modular Arithmatic,
In Modular Arithmtic (a*b) \bmod m = ((a\bmod m) * (b\bmod m)) \bmod m
So instead of calculating whole we can use mod at every step.
We know that n\choose r = \frac{n!}{r!(n-r)!}, to calculate the factorials every time is costly and the constraints are so big (2\leq N \leq 10^5) so factorials of these numbers will also be big.
As we are doing multiplication with \bmod at each step(described above), We can store factorials with mod.
factorial[i]=(i * factorial[i-1]) \bmod m
To Calculate n\choose r = \frac{n!}{r!(n-r)!}, We need factorial[n] , factorial[r], factorial[n-r]
But,
(a/b) \bmod m \neq ((a\bmod m) / (b\bmod m)) \bmod m .
So, to divide with \bmod, Since we have m=10^9+7 as prime we can apply Fermat’s little theorem.
We can define n\choose r = factorial[n]*modInverse(factorial[r]) * modInverse(factorial[n-r]),
Where modInverse() method contains Fermat’s little theorem.
We can precompute modInverse of all factorial possible values.(so we don’t need to find multiplicative inverse everytime)
Therefore, when we want n\choose r we can get it in O(1) time.
TIME COMPLEXITY:
Time complexity is O(N) for each test case. (Ignoring the precomputation)
Precomputation can be done in O(100000*log(m))
SOLUTIONS:
Setter's Solution
#ILLUMINATI SEASON 6
'''
codechef id :mj_13
Problem : Teaming in Tournament of Power
'''
from sys import stdin,stdout
MOD=1000000007
factorials=[1]
modinv=[1]
for i in range(1,100001):
factorials.append((factorials[-1]*i)%MOD)
for i in range(1,100001):
modinv.append(pow(factorials[i],MOD-2,MOD))
def ncr(n,r):
global MOD,factorials,modinv
return (((factorials[n]*modinv[r])%MOD)*modinv[n-r])%MOD
test=int(stdin.readline())
for _ in range(test):
uni_counts=[0,0]
uni1=0
N,K = map(int,stdin.readline().split())
assert(N!=1)
print('F',1,flush=True)
uni1=int(input())-6
uni_counts[uni1]+=1
for i in range(2,N+1):
print('Q',1,i,flush=True)
out=int(input())
if out==1:
uni_counts[uni1]+=1
else:
uni_counts[not uni1]+=1
q=pow(ncr(N,K),MOD-2,MOD)
i=1
p=0
for i in range(max(K//2+1,K-uni_counts[0]),min(uni_counts[1],K-1)+1):
p=(p+(ncr(uni_counts[1],i)*ncr(uni_counts[0],K-i))%MOD)%MOD
i+=1
ans=(p*q)%MOD
print('A',ans,flush=True)
Feel free to Share your approach, or you can ask any queries you have 