Recently I saw this question on my quora feed. This question I think is primarily for someone who have won medals in IMO or any regional mathematics olympiad. Though it is open for everyone who are good in mathematics. I know some of our fellow codeforces users who are winner of previous IMO likes of rng_58,Swistakk,Xellos,hos.lyric, etc. So their view would be quite helpful specially rng_58 has written a blog regarding very nice IMO final problem.

The problem is similar to asking, you have 2 boxes each having capacity of W(<10000). And you have given a list of item of some capacity c( 100 <= c <= 3000). List can contain at max n (<= 200) items. Now you have to access the list in FIFO order and put those items in any of the two boxes until addition of item overflow each of the boxes. Note: You can not skip any item during processing, if it does not fit stop the process.

I did O(Wn) for each test case. My java solution run in 2 sec approx.

Is there any better solution than this? I thought of greedy but instantly got counter case.

Topcoder SRM 642 will take place on 17th dec at 02:00 AM GMT. I was hoping for chrome to announce it.

I hope that most of us do multiple successful challenge and submission and after contest we do nice discussion on problems.

Good Luck to all.

Problem Statement

Many top accepted solution used DP.I have not practiced DP so much so will wait for editorial then try.I used different approach after the competition and It got accepted.

My Solution for the problem -

I made two cases one for N is even and another for N is odd:

Case 1: N is even.

1. Calculate N!/((N / 2)!*(N / 2)!).

2. Divide the above value by 2^N(Multiple of 2 N times) and store it in some double variable.

3. Multiply the above stored variable with (2*N + 1), this is result, return it.

Case 2: N is odd.

1. Calculate (N + 1)!/(((N + 1) / 2)!*((N + 1) / 2)!).

2. Divide the above value by 2^(N + 1) and multiply this value with (N + 1) and store it in some double variable as Sum1.

3. Calculate (N — 1)!/(((N — 1) / 2)!*((N — 1) / 2)!).

4. Divide the above value by 2^(N — 1) and multiply this value with N and store it in some double variable as Sum2.

5. Return this result (sum1 + sum2).

Link to Code

UPD: Sorry I forgot to mention why I posted It.I don't know the proof so can someone give me its proof.