Modified paths Counting in a Rectangle

Question

I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:

We are given K Rectangles. The dimensions of $x$-th Rectangle is ($N_x \times M_x$), where $1\leq x \leq K$. From each rectangle $x$ , Alice Cuts a rect. of dimension ($P_x \times Q_x$), where $1 \leq x \leq K$ , from the Top-Right Corner and trashes the cut portion.

Initially Alice placed a robot, at the top left corner of each rectangle. He is very interested to find the number of ways, each robot can reach the bottom-right corner (target) using the following rules:

• The robot can only move 1 unit right* or the robot can only move 1 unit downward.
• The robot cannot move upward, can't move even left and can't move even diagonally.
• The robot can move on rectangle boundary.

The number of ways can be very large. Thus, Answer = (Number of ways) mod 10^9+7.

Constraints is very large:

1<=K<=10
2<=(Nx,Mx)<=5*10^5
1<=Px<Nx
1<=Qx<Mx

The Time Limit is just 1 second.

Example:

K=1

N1=2 M1=2

P1=1 Q1=1

Answer: 5 ways

I had solved the easier version of this problem (Using Pascal triangle + Combinatorics), when no portion of rectangle is cut/removed. But I don't know how to solve the above modified problem, where a small rectangle is cut from top-right Corner of the original rectangle.

Answer 1

As mentioned in the comments, DP is a perfectly valid solution to the problem. If the numbers are too large to calculate directly the number of solutions, then you can take things mod 10^9 + 7 during intermediate steps, too. This will work out because $(a \% b + c \% b) \% b = (a + c) \% b$ (for positive numbers or programming languages that implement negative mod correctly such as Python.

For a more elegant approach, you can calculate directly using more combinatorics. You know the total number of paths in the rectangle before part of it was removed, so it suffices to count the number of paths that went through the removed portion. To do this, take a diagonal from the bottom left of each removed rectangle up and to the right until you reach the border, Any path that goes in the removed portion must hit this diagonal, so if you sum the number of paths there are through each spot on the diagonal, you know how many paths to remove from your total. To count the number of paths that go through a square, count the number of paths to that square and multiply by the number of paths from there to the finish.

A fancier version of this approach is to count directly the paths that avoid the removed portion. To do this, take a diagonal from the corner of the removed rectangle (but not including it) down and to the left until you reach the border. A path avoids the removed rectangle if and only if it goes through this diagonal, so you can sum the number of paths through each location on this diagonal. Again, multiply the number of paths to a point by the number of paths from that point.

Answer 2

We start from the common corner grid (B,N-A) of the rectangle and the cut part. Now, we start from grid (0,0) and find path till that corner multiplied by paths from that corner till grid (N+1,M+1) , i.e the first term of above expression. Now further we move one grid back and calculate path from grid (0,0) till that grid multiplied by paths from there to grid (N+1,M+1) but removing the cases where common grid is used. Similarly , following above process till grid (B,N-A-1) to (B,0) we get the result.

Thus,You may use the formula I have derived:

$${N-A+B \choose B} {M-B+A \choose A} + \sum_{r=0}^{N-A-1} {B+r \choose r} {N-r+M-B-1 \choose N-r}$$

where $A=P$ and $B=Q$.

You need to simplify it further to convert into $O(n \log n)$ solution.