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<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.

$\endgroup$
1

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ You are subtracting each path through the removed rectangle many times! (As many times as the removed points it goes through.) $\endgroup$
    – TonyK
    Dec 4, 2012 at 13:17
  • $\begingroup$ TonyK, you are right, I've now corrected my original post $\endgroup$
    – darioses
    Dec 4, 2012 at 14:44
  • $\begingroup$ 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 $\endgroup$
    – Maths123
    Dec 4, 2012 at 16:06
  • $\begingroup$ 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. $\endgroup$
    – darioses
    Dec 4, 2012 at 17:27
  • $\begingroup$ You need to use dynamic programming, this problems is very "overflow way". So, with this formula, why don't you use memoization. $\endgroup$ Dec 7, 2012 at 15:12
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .