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.

Calculate

**N!/((N / 2)!*(N / 2)!)**.Divide the above value by

**2^N(Multiple of 2 N times)**and store it in some double variable.Multiply the above stored variable with

**(2*N + 1)**, this is result, return it.

Case 2: N is odd.

Calculate

**(N + 1)!/(((N + 1) / 2)!*((N + 1) / 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**.Calculate

**(N — 1)!/(((N — 1) / 2)!*((N — 1) / 2)!)**.Divide the above value by

**2^(N — 1)**and multiply this value with**N**and store it in some double variable as**Sum2**.Return this result

**(sum1 + sum2)**.

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

I guess there were many random challenge trials, right? XD

I did not submit it during the contest

My solution's a double DP.

First, compute the probability that a given random walk from position 0 will reach cell

jinisteps, without ever moving into negative numbers. Denote this asP_{0}[i][j].Clearly,

P_{0}[0][0] = 1 andP_{0}[0][i> 0] = 0. From state (i,j), we can move to (i+ 1,j+ 1) with 50% probability and (ifj> 0) to (i+ 1,j- 1) with 50% probability. Therefore, forj> 0 and .Now, compute the probability that we'll reach cell

j≥ 0 in stepifor the first time:P[i][j]. Clearly,P[0][0] = 1 andP_{0}[0][i> 0] = 0. Fori> 0, we can reach cellj- 1 in stepk<ifor the first time; we also reach it in stepi- 1 and between these steps, we move in the same way as computed inP_{0}[i- 1 -k][0]; in stepi, the choice is "move right". The probability of these events is .We can try all

kand computeP[i][j] as a sum of all their probabilities. The answer is then the sum of allP[i][j] — each state describes the probability of coloring of one cell in some step. This DP has complexityO(N^{3}), which easily passes a 2s time limit.Thanks for DP solution.Nice editorial to understand.

Btw my solution is O(N).Can you prove it?

If you use doubles, it's quite obvious that all expressions only require

O(N) time to compute. (you do justO(N) multiplications)No I am not saying to prove its O(N) sorry for misunderstanding.I am asking for proof of my solution , why it is working in this problem.I just wrote the solution on the basis that robot will start moving from origin then what is the probability of reaching origin again if it moves left or right with equal probability.For even

Nits understandable it will move equal half in both direction but for oddNI used it randomly and its working.Oh, OK. Rather than "prove", the question's to "compute" the sums from some DP and show that we get your formulas.