You are not logged in. Please login at www.codechef.com to post your questions!

×

ICLFIN03 - Editorial

PROBLEM LINK:

Contest link: ICLFIN03

Author

Sourabh Bansal

Tester

Shubham Gupta

Editorialist

Sourabh Bansal

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.

PROBLEM SETTER's SOLUTION:

http://ideone.com/INMFvC

This question is marked "community wiki".

asked 12 Apr '15, 07:30

sourabh13's gravatar image

2★sourabh13
16
accept rate: 0%

edited 23 Apr '15, 17:06

admin's gravatar image

0★admin ♦♦
19.8k350498541


Solution link is not working.

link

answered 30 Jul '16, 10:09

dark_army's gravatar image

0★dark_army
1
accept rate: 0%

I am from professional essay help providing company, kindly elaborate your query.

link

answered 30 Jul '16, 15:07

educationexper's gravatar image

0★educationexper
-1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,214
×1,220
×40

question asked: 12 Apr '15, 07:30

question was seen: 1,247 times

last updated: 30 Jul '16, 15:07