# Codingame Solution: Bag of Balls

Imagine you have a bag, which is filled with

If you extract a ball from the bag, the probability changes of the remaining balls.

Your job is it to output the ratio of the odds that you extracted

Balls are never put back into the bag!

You have 3 balls in the bag, 2 of which are white.

What is the probability of having 2 white balls by extracting 2 balls?

When

P(A) = Probability of getting 2 white balls =

P(!A) = Probability of not getting 2 white balls =

So the ratio P(A) : P(!A) is

The ratio

`N`balls. Each ball can have the color**black**or**white**. You know that`W`balls in the bag are white.If you extract a ball from the bag, the probability changes of the remaining balls.

Your job is it to output the ratio of the odds that you extracted

`k`white balls after extracting`s`balls from the bag.Balls are never put back into the bag!

**Example:**You have 3 balls in the bag, 2 of which are white.

What is the probability of having 2 white balls by extracting 2 balls?

2/3 * 1/2 = 1/3

When

**A**is the event of getting 2 white balls:P(A) = Probability of getting 2 white balls =

**2/3 * 1/2 = 1/3**P(!A) = Probability of not getting 2 white balls =

**1-1/3 = 2/3**So the ratio P(A) : P(!A) is

**1:2**(read 1 to 2).The ratio

**2:4**would be the same ratio, but both numbers are divisible by**2**, so you need to reduce the ratio.Input

**Line 1:**An Integer

`N`for the number of balls in your bag.

**Line 2:**An Integer

`W`for the number of white balls in your bag.

**Line 3:**An Integer

`s`for the size of your sample.

**Line 4:**An Integer

`k`for the desired number of white balls in your sample.

Output

**Line 1:**

`A`:

`B`, the odds ratio (in lowest terms) that

`k`white balls are in your sample of

`s`balls

Constraints

0 ≤ N ≤ 60

0 ≤ W ≤ N

0 ≤ s ≤ N

0 ≤ k ≤ s

0 ≤ k ≤ W

0 ≤ W ≤ N

0 ≤ s ≤ N

0 ≤ k ≤ s

0 ≤ k ≤ W

## Solution

We calculate the Laplace-Probability by first determining the underlying set of \(s\) balls out of \(n\) balls without repetition, which are \({n\choose s}\). We then treat the draw of black and white balls separately. We first draw \(k\) white balls, which gives \(w\choose k\) possibilities and \(s-k\) black balls, which gives \(n-w\choose s-k\) possibilities and therefore

\[ P(X) = \frac{{w\choose k}\cdot{n-w\choose s-k}}{n\choose s} \]

When we take the probability as a rational number \(q=P(X)\), the odds are \(\frac{q}{1-q}\). Implemented in Ruby, the whole solution then looks as

n = gets.to_i w = gets.to_i s = gets.to_i k = gets.to_i def binom(n, k) n = n - k c = 1 for i in 1..k do c = c * (n + i) / i end return c end q = Rational(binom(w, k) * binom(n - w, s - k), binom(n, s)) if 1 == q then puts "1:0" else puts (q / (1 - q)).to_s.sub("/", ":") end