Bags with Balls
Published: 2022-08-16 10:50:00



This post is my first experience in solving a "hard" problem on CodeForces.

As I logged in to CodeForces for the first time, I went to the `Problemset`
section hoping to solve some question. I was blissfully unaware how the
difficulty rating system worked. I picked the first problem in the list and
tried to have a go.

## [The question](https://codeforces.com/problemset/problem/1716/F)

There are n bags, each bag contains m balls with numbers from 1 to m. For
every ![I](https://korigamik.deno.dev/svg/OMgnbTsUR2.svg)
∈[1, m], there is exactly one ball with number 
![I](https://korigamik.deno.dev/svg/UFmFt1ZjgB.svg)
in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for
example, taking the ball 1 from the first bag and the ball 2 from the second bag
is not the same as taking the ball 2 from the first bag and the ball 1 from the
second bag). After that, you calculate the number of balls with odd numbers
among the ones you have taken. Let the number of these balls be 
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/hvYeBwkG4O.svg">
Your task is to calculate the sum of 
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/W1OEcmaIfA.svg">
over all possible ways to take n balls, one from each bag.

## Initial Thoughts

So when I saw the notation for 
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/TIQXfeo8b0.svg">
I thought this supposed to refer to a
[Multi-index n-tuple](https://en.wikipedia.org/wiki/Multi-index_notation)
where
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/AOFI9TpXon.svg">
was a tuple of all the odd index selected balls.

But that was stupid, it's just the regular exponent. Still it was pretty
interesting of them to ask the sum of the number of balls to
the
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/PudsU5TNrh.svg">
&nbsp;power.

## The working

I was definitely stuck on this. There weren't even any solutions on the internet
either. But I was able to find some similar problems and that's where
WolframAlpha gave me the key to solve this problem.

### Formulating the solution

We can consider the number of was to pick `i` odd balls from `n` bags each
containing `m` balls. This can be found out by:



<div align="center"><img style="background: white;" src="https://korigamik.deno.dev/svg/UBIx2N9Ctv.svg"></div>

We basically choose `i` boxes which we want the odd balls from and each of the
`i` boxes has m+1/2 choices, and then we want to choose even balls from the
`n-i` remaining bags which have m/2 choices each.

To make the expressions easier to maintain we will



<div align="center"><img style="background: white;" src="https://korigamik.deno.dev/svg/GL2RFkmAov.svg"></div>

So the final answer can be formulated as


<div align="center"><img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/g4Wb0nv3ux.svg"></div>

Where we sum through all the number of odd balls which can be selected (from 0
to n) each contributes 
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/gJzwNsRmB1.svg">
to answer.

Now the challenge was the simplify this expression, as it is now it will be way
over the O(n) complexity that is required to solve these "hard" problems.

It seems awfully close to the well known binomial formula but the pesky
<img style="transform: translateY(0.1em); background: white;" src="https://korigamik.deno.dev/svg/gJzwNsRmB1.svg">
makes it almost impossible to simplify further.

Luckily after research on this a little, WolframAlpha taught me about the
existense of the
[Stirling numbers](https://en.wikipedia.org/wiki/Stirling_number) which are
denoted by the { a b } bracketes like the binomial coefficient.

They have the interesting property that:



<div align="center"><img style="background: white;" src="https://korigamik.deno.dev/svg/DUTdoX60zc.svg"></div>

Which will help us to do something about the the exponent. I present to you the
steps to the simplification:



<div align="center"><img style="background: white;" src="https://korigamik.deno.dev/svg/dPt76zSz5m.svg"></div>

Therefore, the answer can be simplified into



<div align="center"><img style="background: white;" src="https://korigamik.deno.dev/svg/5YGRBmc3dW.svg"></div>

The first term can be precomputed into a 2-D dp array. The final complexity of
the program should be ~ O(n + c)

## Conclusion

I hope you found this thread interesting. I still don't think I will be able to
give much time to the competitive coding side of things. For me, it's similar to
a Sudoku or a puzzle that I would solve once in a while but not spend all my
brain power on just doing them.