Can someone tell me how to solve this problem. The typical DP approach won’t work here because of the contraints
1 Like
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
2 Likes
These permutation Q haunt me outta my wits. Waiting for an answer!
1 Like
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.