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.

## Top comments (0)