Can someone tell me how to solve this problem. The typical DP approach won’t work here because of the contraints
Answer of this question is simply trying every possible scenario from x1 to x2 and from y1 to y2 which reduces it to a combinatorics problem.
We have to take summation of every i from (0 to min(x2-x1,y2-y1)) (binomial(x2-x1+y2-y1-2*i,x2-x1-i)multiplied by binomial(x2-x1+y2-y1-i,i)).
Here is my AC code for reference Click Here
These permutation Q haunt me outta my wits. Waiting for an answer!
I didn’t understand. Can u explain y we are doing that.
Summation over every i from (0 to min(x2-x1,y2-y1)) signifies moving from one end to the other and for every possible case calculating combinations and adding them together.
for eg. (x1,y1,x2,y2)=(2,4,3,8) now I would calculate number of ways if i move 0 step diagonally+number of ways if i move 1 steps diagonally.
If that case corresponds to (x1,y1,x2,y2)=(4,2,8,3).Then I would calculate number of ways if i move 0 step diagonally+number of ways if i move 1 step diagonally.That means Calculating number of combinations I could make moving I step closer to my nearest x or y-co-ordinate.
Thanks I understood.