2
$\begingroup$

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

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.

  • 1
    cross-posted: http://cs.stackexchange.com/questions/7152/2012-12-04

3 Answers 3

2

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.

  • 0
    You need to use dynamic programming, this problems is very "overflow way". So, with this formula, why don't you use memoization.2012-12-07
1

(I'm going to scrap your $x$ subscript, and consider a single case given by $(N,M,P,Q)$. I use $x$ as my $x$-coordinate.)

Let $H$ be the horizontal line segment from $(0,M-Q)$ to $(N-P,M-Q)$ that extends the lower boundary of the cut-out rectangle across the uncut part. Consider a point $(x,y)$ on $H$. Let $U(x,y)$ be the number of paths from the top left corner $(0,M)$ to $(x,y)$ that first meet $H$ at $(x,y)$; and let $L(x,y)$ be the number of paths from $(x,y)$ to the bottom right corner $(N,0)$. Then the number of paths from $(0,M)$ to $(N,0)$ that first meet $H$ at $(x,y$) is just $U(x,y)L(x,y)$, and we get the total by summing this over $x$ from $0$ to $N-P$.

Now let $R(i,j)$ be the number of paths from one corner of an $i \times j$ rectangle to the opposite corner: $R(i,j)=\frac{(i+j)!}{i!j!}$(as you know). We get immediately $L(x,y)=R(N-x,M-Q)$. And for $U(x,y)$, note that a path that first meets $H$ at $(x,y)$ must pass through $(x,y+1)$, so $U(x,y)$ is just $R(x,Q-1)$.

1

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.