Help for a atcoder problem

Problem link
I was trying to solve but could not solve it. Please help…

Define dp[i][j] as the number of ways she can reach the cell [i][j]. It can be clearly seen that dp[0][x] = 1 for 0 < x < n and dp[x][0] = 1 for 0 < x < (m - a).

Transition

dp[i][j] = dp[i-1][j] + dp[i][j-1] for regular i, j
dp[i][j] = 0 for and i, j in the forbidden section.

can u share ur solution link, it would be a great help. i was trying to implement ur idea but it got me error as dp is a two dimensional array having size of each dimensions of size 10^5, i think it will lead to run time error.

I haven’t solved that problem yet. Anyways a 2D array of that size will cause MLE.

You can do a space saving dp. Just remember the values for the previous row and current row. After you finish the current row, just assign prev = cur, and overwrite cur for the next row.

Psuedo Code
int prev[n], cure[n];
for(int i = 0; i < n; i++) prev[i] = 1;

for(int r = 1; r < m; r++)
{
    if(r >= (m - a))
        cur[0] = 0;
    else
        cur[0] = 1;
    for(int c = 1; c < n; c++)
    {
        if(r >= (m - a) && c < b)
            cur[c] = 0;
        else
            cur[c] = prev[c] + cur[c-1];
    }
    prev = cur;
}

cout << cur[n-1] << endl;

You can use combinatorics.
The number of ways to go from (a,b) to (h,w) is \binom{(h-a)+(w-b)}{(h-a)} or \binom{(h-a)+(w-b)}{(w-b)}.
That’s because I have to choose h-a down moves in h-a + w-b total moves.

Let’s calculate the number of blocked paths.

Now notice the blocked region is a rectangle in the bottom left. Notice that if you cannot go the top layer, you can’t go into any of the blocks below it either. So we can reopen them and the answer will be the same.

Now for each blocked path. Let us assume (h-a+1, i), i\le b is the first blocked point in our path. If we iterate over each point being the first blocked point, then each blocked path will get counted only once.

For (h-a+1,i) to be the first point we must come from above. So we need to go from (1,1) to (h-a,i) then you will go to (h-a+1,i) and then go to (h,w).
If you use the above formula, then you get the answer \binom{h-a-1 + i-1}{i-1} \times \binom{a-1 + w-i}{w-i} Now we have to iterate i from 1 to b and subtract all of them from the total paths.
Code : Submission #14467550 - AtCoder Beginner Contest 042

thanks a lot… i have learnt something new…

Thanxx man…