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 xth Rectangle is (Nx * Mx),where 1<=x<=K.
From each rectangle x, Alice cuts a rect. of dimension (Px*Qx), where 1<=x<=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.
Best Answer
Let's restrict the study only to one of the K rectangles. Let's assume that N and M are respectively its height and width, and that P and Q are the height and width of the rectangle that gets cut off it. Let's refer to a coordinate system with origin on the top-left corner of the rectangle and x and y axis oriented right and down respectively.
The number of possible paths from the top-left corner to the bottom-right corner is given by:
$$ \frac{(N+M)!}{N!M!} $$
From the number above we must subtract the number of paths not passing by the removed rectangle. This is all the paths not having a point on the vertical segment (M-Q+1, 0) - (M-Q+1, P-1).
The number of paths passing by a specific point (x, y) is given by:
$$ \frac{(x+y)!}{x!y!}\frac{[(M+N)-(x+y)]!}{(M-x)!(N-y)!} $$
Hence the number we are looking for is:
$$ \frac{(N+M)!}{N!M!}-\sum_{y=0}^{P-1}{\frac{(M-Q+1+y)!}{(M-Q+1)!y!}\frac{(N+Q-1-y)!}{(Q-1)!(N-y)!}} $$
I wouldn't know how to put that sum in closed form though.