### 1e9's blog

By 1e9, 10 years ago, 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).  Comments (7)
 » My solution's a double DP.First, compute the probability that a given random walk from position 0 will reach cell j in i steps, without ever moving into negative numbers. Denote this as P0[i][j].Clearly, P0 = 1 and P0[i > 0] = 0. From state (i, j), we can move to (i + 1, j + 1) with 50% probability and (if j > 0) to (i + 1, j - 1) with 50% probability. Therefore, for j > 0 and .Now, compute the probability that we'll reach cell j ≥ 0 in step i for the first time: P[i][j]. Clearly, P = 1 and P0[i > 0] = 0. For i > 0, we can reach cell j - 1 in step k < i for the first time; we also reach it in step i - 1 and between these steps, we move in the same way as computed in P0[i - 1 - k]; in step i, the choice is "move right". The probability of these events is .We can try all k and compute P[i][j] as a sum of all their probabilities. The answer is then the sum of all P[i][j] — each state describes the probability of coloring of one cell in some step. This DP has complexity O(N3), which easily passes a 2s time limit.