[Math] modified-paths-counting-in-a-rectangle

algorithmscombinatorics

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.

Related Question