SPOj LVADER solution

Can someone tell me how to solve this problem. The typical DP approach won’t work here because of the contraints

1 Like

These permutation Q haunt me outta my wits. Waiting for an answer!

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

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.

//