Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
cross-posted: cs.stackexchange.com/questions/7152 –  A.Schulz Dec 4 '12 at 12:08

3 Answers 3

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.

share|improve this answer
2  
You are subtracting each path through the removed rectangle many times! (As many times as the removed points it goes through.) –  TonyK Dec 4 '12 at 13:17
    
TonyK, you are right, I've now corrected my original post –  darioses Dec 4 '12 at 14:44
    
The constraint is very large :2<=(Nx,Mx)<=5*10^5 . Can we convert the above equation into combinatorics. The Factorial of 10^5 is hard to handle because of overflow –  Maths123 Dec 4 '12 at 16:06
    
Maths123, what do you mean by converting into combinatorics? One way I can think of to avoid overflow while multiplying big numbers is to use logarithms. Anyway I think this issue would better be discussed in a different topic. –  darioses Dec 4 '12 at 17:27
    
You need to use dynamic programming, this problems is very "overflow way". So, with this formula, why don't you use memoization. –  d555 Dec 7 '12 at 15:12

(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)$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.