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 $x$-th Rectangle is ($N_x \times M_x$), where $1\leq x \leq K$. From each rectangle $x$ , Alice Cuts a rect. of dimension ($P_x \times Q_x$), where $1 \leq x \leq 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.