ANUTHM - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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 1 ≤ i ≤ N, 1 ≤ i ≤ M.

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:

Setter’s solution
Tester’s solution

3 Likes
2

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

1 Like
3

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[i-1][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]*(N-i)*0.5) ;
		}
		for(int i=1;i<M;i++){
			ans += (DP[N][i]*(M-i)*0.5) ;
		}
4

there is something wrong with the practice link…

5

Here is the dp approach for the above problem. complexity of 1000^2(for precomputations)+t*(n+m)

http://www.codechef.com/viewsolution/5934786

6

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).

2 Likes
7

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… :slight_smile:

1 Like
8

what does it means that sigma(pi)for all is 1…?? how can you conclude that…? plz explain it…

9

got an O(1) solution by looking into the pattern! Pretty amazing seeing the AC go green! :slight_smile:

10

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.

11

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)

12

Change

printf("%lf",(long double)m+n-1);

to

printf("%f",(float)m+n-1);

13

@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.

14

approach 1: you have zeros as co ordinates, that is a mistake right ?

15

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