Bags with Balls

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

There are n bags, each bag contains m balls with numbers from 1 to m. For
every
∈[1, m], there is exactly one ball with number

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

Your task is to calculate the sum of

over all possible ways to take n balls, one from each bag.

Initial Thoughts

So when I saw the notation for

I thought this supposed to refer to a
Multi-index n-tuple
where

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

 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:

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

So the final answer can be formulated as

Where we sum through all the number of odd balls which can be selected (from 0
to n) each contributes

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

makes it almost impossible to simplify further.

Luckily after research on this a little, WolframAlpha taught me about the
existense of the
Stirling numbers which are
denoted by the { a b } bracketes like the binomial coefficient.

They have the interesting property that:

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

Therefore, the answer can be simplified into

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.