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