0

Given a grid of size N X N. Its bottom-left point is (0,0) and top-right element is (N-1,N-1).

We can traverse the grid in either top or right direction. We have to find the number of ways to traverse from the bottom-left to top-right point. There are some checkpoints which we have to visit in every path. There is at least one valid path.

Example : Let N=5 and we have 1 checkpoint at (2,2) then here answer is 36.

Note : I need to count only valid paths and have no concern in finding them.

What can be efficient way to count them ?

Lrrr
  • 4,755
  • 5
  • 41
  • 63
user3840069
  • 765
  • 1
  • 6
  • 20

3 Answers3

2

you have to know two things :

  1. Rule of product: it means that number of ways from start to end is equal number of ways from start to middle point * number of ways from middle point to end.

  2. C(R,R+U) ( R is number of your right moves and U is the number of up moves it means if you want to go from (a,b) to (c,d) then R = c-a and U = d-b, and C(R,R+U) = (R+U)!/R!U! ) is the answer of how many ways there are from bottom left to top right in a grid.

Example in your example from my second rule we have :

number of moves from (0,0) to (2,2) because after two right move from 0 you reach 2 and after two up move from 0 you reach 2 so R=2 and U=2 so C(2,2+2) = C(2,4) = 4!/2!2! = 6. And doing the same for R and U number of moves from (2,2) to (4,4) is C(2,2+2) = C(2,4) = 4!/2!2! = 6

and from the first rule we have number of all possible moves : 6 * 6 = 36

Community
  • 1
  • 1
Lrrr
  • 4,755
  • 5
  • 41
  • 63
  • How are you finding R and U like here : number of moves from (2,2) to (4,4) is C(2,2+2) ? – user3840069 Feb 10 '15 at 13:12
  • Say we want to move from (a,b) to (c,d) then what are your R and U ? – user3840069 Feb 10 '15 at 13:13
  • Say we have one more checkpoint at (3,2) then please explain your approach – user3840069 Feb 10 '15 at 13:15
  • @user3840069 I add the details that you want :) – Lrrr Feb 10 '15 at 13:16
  • @user3840069 The order of visiting checkpoints is predefined - you can never visit (3,2) before (2,2) not after (4,4), so the order must be (2,2),(3,2),(4,4). If you want to go from (x1,y1) to (x2,y2) - L=x2-x1, R=y2-y1 – amit Feb 10 '15 at 13:17
  • @amit Is their some easy way to predefine the order if we are given K checkpoints like (a1,b1) , (a2,b2)...(ak,ck) – user3840069 Feb 10 '15 at 13:18
  • @user3840069 Yes, sort by `a_i+b_i`, the smaller the sum is - the first you visit this checkpoint. This claim is correct because you can never go back, so if you had to make k steps to reach point `(ai,bi)`, and `k'>k` steps to reach `(aj,bj)` - `(ai,bi)` must have been visited first. – amit Feb 10 '15 at 13:20
  • @amit I think you need to mention we also must check a1=b2 we cant make this happen at all! – Lrrr Feb 10 '15 at 13:25
  • @Lrrr Problem's restrictions ensures existence of at least one path, so that's redundant – amit Feb 10 '15 at 13:29
1

Use dynamic programming:

dp[k, i, j] = number of paths from checkpoint k to (i, j)

dp[k, i, j] = dp[k, i - 1, j] +        top
              dp[k, i, j - 1]          right

Answer is the product of dp values between the checkpoints.

Note: you can avoid the first dimension by realizing that the actual positions in the matrix don't matter, just the relative distances between the positions and the positions of the checkpoints.

IVlad
  • 43,099
  • 13
  • 111
  • 179
  • @IVIad I don't understand your DP . Whats right here ? – user3840069 Feb 10 '15 at 13:00
  • @user3840069 - if you have more exact questions, I'll gladly answer, but I won't make it clearer until you show some effort yourself. – IVlad Feb 10 '15 at 13:02
  • Seems overkill to me, if there are no obstacles, the number of paths from (x1,y1) to (x2,y2) is a closed formula – amit Feb 10 '15 at 13:04
  • @amit - the formula is nice and it has its value, but: 1. It's arguably harder to understand and 2. It's harder to implement if you want the answer modulo something (which you might, because the number of paths grows very fast), because it involves division by factorials or even more knowledge of combinatorics. So I wouldn't say this is overkill. It's not the fastest solution, but I'd argue it's the simplest. – IVlad Feb 10 '15 at 13:08
  • @IVlad I don't find a DP solution easier to understand than a simple Choose formula (then again, I am TAing combinatorics), (2) implementing factorial modulos is fairly easy to implement, and the solution using the close formula is significantly more efficient (linear in the number of checkpoints (or klogk, if the checkpoints are not sorted), assuming you have a factorial(x) pre-calculated for 1,2,...,2n - compared to the DP solution which is linear in the number of squares (quadric in n). – amit Feb 10 '15 at 13:19
  • 1
    @amit - you have to implement Choose modulos, not factorial modulos. Those involve division, so you cannot precompute factorials. You either have to implement factorial fraction simplification or use the recurrence formula for combinations (which is really DP again). So I still think it's harder to implement. – IVlad Feb 10 '15 at 13:23
1

The crux of this particular problem is to find the number of paths between sub points (after sorting based on their respective positions) and then multiplying all the number of paths.

The solution here would be:

1. Sort the points from Source to Destination.

Example: If start point is [0,0] end point is [10,10] and intermediate points being [5,6],[2,4] & [8,8], then the sorted points (including source and destination) would be [0,0], [2,4], [5,6], [8,8], [10,10] in a 11X11 matrix

2. Find the number of Paths (preferably using DP) from source to next sub-destination. (In order of sorted points)

In the above example, the number of paths that need to be calculated would be between the following points:

[0,0] to [2,4]

[2,4] to [5,6]

[5,6] to [8,8]

[8,8] to [10,10]

3. Find the product of all the above 4 sub paths

That's it

Here's a solution for finding number of paths (see DP approach) from a source and destination. You need not pass the matrix as argument as that is just not needed. Only source and destination points are needed in the form of [x,y] [X,Y]. The other part (sorting the points and multiplying) has to be done as explained above apart from the code present in the link.

Community
  • 1
  • 1
Anirudh Kabde
  • 66
  • 5