PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY:EASYMEDIUM PREREQUISITES:Mathematics, Probability PROBLEM:Consider an N by M grid. Rows are numbered 1 to N, from top to bottom. Columns are numbered 1 to M, from left to right. You are initially at cell (1, 1) and want to go to cell (N, M). From any cell you can move to the cell below it or to the cell right to it. You should never go out of the grid. At any point you should consider all the possibilities of movement with equal probability Let P[i][j] be the probability of visiting cell (i, j). You need to calculate the sum of P[i][j] for 1 ≤ i ≤ N, 1 ≤ i ≤ M. QUICK EXPLANATION:Answer is N+M1 because after sum of probabilities of all cells in same diagonal is 1. EXPLANATION:APPROACH 1:Consider that you are cell (1, 1). After 2 steps, what all cells we can reach? After 3 steps, what all cells we can reach? and so on. If we go on writing like that, we end up writing the diagonals from left top to right bottom and each cell being covered once.
Now, probability at (0,0) is 1. After we take a step, the sum of probabilities of positions a step away from (0,0) will be 1 because it is clear, no matter how we move we will be one step further, we'll reach the next diagonal. So the sum of probabilities remains 1. Therefore, sum of probabilities in each diagonal is 1. And there are a total of N + M  1 diagonals. APPROACH 2(slow, wouldn't pass):Consider F1(x, y) to be the number of ways to reach cell (x, y) from cell (0, 0). We know that F1(x, y) = (x + y)! (x! * y!), where N! denotes 1*2*3...N. So, in a similar way F2(x, y) = F1(n  x  1, m  y  1). Now, what's the probability of visiting cell (x, y). It's equal to number of paths that pass through it divided by total number of paths. So, we precalculate array fact, where fact[i] stores log2(1*2*3...i). We store our calculation log2 because otherwise we'll have to store numbers as large as 1000 factorial! Now, $F1(x, y) = 2^{fact[x + y]  fact[x]  fact[y]}$. Complexity: O(N*M). SOLUTIONS:
This question is marked "community wiki".
asked 19 Jan '15, 01:12

I could come up with the final answer in a very easy way. we have to tell the sum of probabilities of each cell being visited. Now lets say there are some P different paths possible to reach N,M from 1,1. let the ith path be followed with probability Pi. so we know sigma(Pi) for all i is equal to 1. We also know any path from 1,1 to N,M will go through N+M1 cells. Thus each path contribute Pi to exactly N+M1 cells. Thus answer is (N+M1)*(1). answered 19 Jan '15, 01:35

I made a another approach to this problem that uses dp and answers every testcase in O(n+m) time after an O(MAXN*MAXM) preprocessing. Here is a link to my solution http://www.codechef.com/viewsolution/5934171 answered 19 Jan '15, 01:19

Nothing can be better than this.. mine O(1) solution.. do a little crunching and I reached my solution..http://www.codechef.com/viewsolution/5931193.. :) answered 19 Jan '15, 10:26
Your link doesn't work, it should be http://www.codechef.com/viewsolution/5931193 But yes, the solution requires basically no code once your realize that point.
(19 Jan '15, 16:40)

Here is something new and quite intutive to me .. I processed a DP table in this manner .. Have a look DP[1][1] = 1 ; for(int i=1;i<MAXN;i++){ double s = 0 ; for(int j=1;j<MAXN;j++){ DP[i+1][j] += 0.5*DP[i][j] ; DP[i][j+1] += 0.5*DP[i][j] ; s += DP[i][j] ; SUM[i][j] = SUM[i1][j] + s ; } } here you can see DP table is filled with the traditional approach of DP and SUM matrix is maintained just to store the sum of probabilities. SUM[i][j] = stores sum from DP[1][1] to DP[i][j] (inclusively) then i used the following code to answer the test case in O(M+N) which is quite justified to the given constraints .. double ans = SUM[N][M] ; for(int i=1;i<N;i++){ ans += (DP[i][M]*(Ni)*0.5) ; } for(int i=1;i<M;i++){ ans += (DP[N][i]*(Mi)*0.5) ; } answered 19 Jan '15, 01:19

there is something wrong with the practice link... answered 19 Jan '15, 01:24

Here is the dp approach for the above problem. complexity of 1000^2(for precomputations)+t*(n+m) answered 19 Jan '15, 01:34

what does it means that sigma(pi)for all is 1..?? how can you conclude that..? plz explain it... answered 19 Jan '15, 13:09

got an O(1) solution by looking into the pattern! Pretty amazing seeing the AC go green! :) answered 19 Jan '15, 14:40

int main(){
} some one please tell me what's wrong in this. It is giving me WA. Please help. (logical mistake. not header file) answered 19 Jan '15, 17:31

approach 1: you have zeros as co ordinates, that is a mistake right ? answered 01 Feb '15, 09:24

Another solution that hasn't been mentioned : I used DP in computation step with O(MAXM*MAXN) and answer every query in O(1):
solution link: https://www.codechef.com/viewsolution/9048075 answered 31 Dec '15, 20:35

@darkshadows If we are taking our grid to be 0indexed, then shouldn't it be (0,0) as the initial position in the first approach? Then only we can reach to (0,1) or (1,0) as mentioned in the first step.