You are not logged in. Please login at www.codechef.com to post your questions!

×

ANUTHM - Editorial

3
4

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

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 19 Jan '15, 01:12

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 04 Feb '15, 06:34

dpraveen's gravatar image

4★dpraveen ♦♦
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) damn_me3★

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

link

answered 19 Jan '15, 01:35

karanaggarwal's gravatar image

3★karanaggarwal
2816
accept rate: 0%

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

link

answered 19 Jan '15, 01:19

dragonslayerx's gravatar image

5★dragonslayerx
111
accept rate: 0%

edited 19 Jan '15, 01:36

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

link

answered 19 Jan '15, 10:26

code_streak's gravatar image

2★code_streak
512
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) luc4sdreyer4★

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) ;
        }
link

answered 19 Jan '15, 01:19

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

there is something wrong with the practice link...

link

answered 19 Jan '15, 01:24

akhileshydv20's gravatar image

2★akhileshydv20
173
accept rate: 0%

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

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

link

answered 19 Jan '15, 01:34

codecracker4's gravatar image

4★codecracker4
11
accept rate: 0%

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

link

answered 19 Jan '15, 13:09

va1ts7_100's gravatar image

3★va1ts7_100
4721732
accept rate: 11%

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

link

answered 19 Jan '15, 14:40

ankitdhall's gravatar image

2★ankitdhall
212
accept rate: 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)

link

answered 19 Jan '15, 17:31

basant_1994's gravatar image

5★basant_1994
462
accept rate: 16%

edited 19 Jan '15, 17:34

Change

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

to

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

(19 Jan '15, 17:40) mediocoder3★

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

link

answered 01 Feb '15, 09:24

bicepjai's gravatar image

2★bicepjai
11
accept rate: 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

link

answered 31 Dec '15, 20:35

nilesh3105's gravatar image

5★nilesh3105
716210
accept rate: 31%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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