TEAMTOP - Editorial



Author: Jaymeet Mehta




Basic Combinatorics, Probability, Modular Multiplicative Inverse


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))


  • 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


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]


(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 is O(N) for each test case. (Ignoring the precomputation)
Precomputation can be done in O(100000*log(m))


Setter's Solution
codechef id :mj_13
Problem : Teaming in Tournament of Power
from sys import stdin,stdout
for i in range(1,100001):
for i in range(1,100001):
def ncr(n,r):
    global MOD,factorials,modinv
    return (((factorials[n]*modinv[r])%MOD)*modinv[n-r])%MOD
for _ in range(test):
    N,K = map(int,stdin.readline().split())
    for i in range(2,N+1):
        if out==1:
            uni_counts[not uni1]+=1
    for i in range(max(K//2+1,K-uni_counts[0]),min(uni_counts[1],K-1)+1):

Feel free to Share your approach, or you can ask any queries you have :slight_smile:

1 Like

Very well explained and great editorial @mj_13 . Great work !!