PROBLEM LINK:
Contest link: ICLFIN03
Author
Tester
Editorialist
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Simple Maths
PROBLEM:
A team is to be formed of “n” players, all of which are BITS students. However, the team might have players belonging to different departments. There are “m” departments in BITS, numbered from 1 to m. Bane’s department has number “h”. For each department “i”, Bane knows number s[i] — how many students who play football belong to this department.
Bane was also able to guarantee a spot on the team. Find the probability that he will have at least one teammate belonging to his department.
EXPLANATION:
This problem is asking for the probability. Consider two sets of teams: the set of teams where Bane is the only student from his major and the set where at least one other student from Bane’s major is present. These two sets don’t intersect, so once we can compute the number of teams in the first set, A, and the number of teams in the second set, B, the answer would be B/(A + B).
Let us define a function C(n, r) = combinations of choosing “r” items from “n” items i.e C(n,r) = (n!)/(r! * (n-r)!) and sum(s[i]) = sum of s[i] where 1 <= i <= n ;
The number of teams in the first set is A = C((sum(s[i]) - s[h]), n-1) . We subtract one as Bane is guaranteed the spot, and the other (n - 1) spots are to be taken by the remaining students.
Now let’s count the number of teams having exactly “k” students from Bane’s major apart from him. This number would be F(k) = C(s[h]-1, k)*C((sum(s[i]) - s[h]), n-(k+1)). Much like for the first set, (n - (k + 1)) students from the other majors should he selected, and none of them should be from Bane’s major. The total number of teams where at least one other student is from Bane’s major is therefore B = sum(F(k)) where 1 <= k <= s[h]-1 .
The statements above describe the mathematical solution. It can be implemented in various ways.