×

# ANUTHM - Editorial

Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu

EASY-MEDIUM

# PRE-REQUISITES:

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 1iN, 1iM.

# QUICK EXPLANATION:

Answer is N+M-1 because after sum of probabilities of all cells in same diagonal is 1.

# EXPLANATION:

## APPROACH 1:

Consider that you are cell (1, 1).
After 1 step, what all cells we can reach?
(0, 1) and (1, 0).

After 2 steps, what all cells we can reach?
(0, 2), (1, 1)and (2, 0).

After 3 steps, what all cells we can reach?
(0, 3), (2, 1), (1, 2)and (0, 3).

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.
For example, this table shows required steps for reaching each cell.

0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8


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.
So our answer in N + M - 1.

## 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).
Consider F2(x, y) to be the number of ways to reach cell (N-1, M-1) from cell (x, y).

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, $P(x, y) = \frac{(F1(x, y) F2(x, y))}{F1(n-1, m-1)}$.

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]}$.
Since we have all values in powers of 2, we can use exponent arithmetic.

Complexity: O(N*M).

# SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

2.5k53137170

@darkshadows If we are taking our grid to be 0-indexed, 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.

(20 Jan '15, 00:59) 3★

 2 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+M-1 cells. Thus each path contribute Pi to exactly N+M-1 cells. Thus answer is (N+M-1)*(1). answered 19 Jan '15, 01:35 281●6 accept rate: 0%
 1 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 11●1 accept rate: 0%
 1 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 51●2 accept rate: 0% 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)
 0 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
 0 there is something wrong with the practice link... answered 19 Jan '15, 01:24 17●3 accept rate: 0%
 0 Here is the dp approach for the above problem. complexity of 1000^2(for precomputations)+t*(n+m) answered 19 Jan '15, 01:34 11 accept rate: 0%
 0 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 472●1●7●32 accept rate: 11%
 0 got an O(1) solution by looking into the pattern! Pretty amazing seeing the AC go green! :) answered 19 Jan '15, 14:40 21●2 accept rate: 0%
 0 int main(){ int tc,m,n,i,j; scanf("%d",&tc); while(tc--){ scanf("%d%d",&n,&m); printf("%lf",(long double)m+n-1); if(tc) printf("\n"); }  } 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 46●2 accept rate: 16% Change printf("%lf",(long double)m+n-1); to printf("%f",(float)m+n-1); (19 Jan '15, 17:40)
 0 approach 1: you have zeros as co ordinates, that is a mistake right ? answered 01 Feb '15, 09:24 2★bicepjai 11 accept rate: 0%
 0 Another solution that hasn't been mentioned : I used DP in computation step with O(MAXM*MAXN) and answer every query in O(1): float a[MAXN+1][MAXM+1]; // foo computes the probablity sum when starting at [i,j] in a "n x m" matrix float foo(int i,int j,int n,int m) { if(i>n || j>m) return 0.000000; if(a[i][j] != 0) return a[i][j]; float x = foo(i+1,j,n,m); float y = foo(i,j+1,n,m); int count = 2; if(x == 0 || y == 0) count = 1; a[i][j] = 1 + ( x + y)/count; return a[i][j]; } ` solution link: https://www.codechef.com/viewsolution/9048075 answered 31 Dec '15, 20:35 716●2●10 accept rate: 31%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×1,186
×40
×14

question asked: 19 Jan '15, 01:12

question was seen: 6,401 times

last updated: 31 Dec '15, 20:35