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