# Matrix Tracing

# Matrix Tracing

q1a2z3 + 3 comments Just thinking through the problem, I realized it's just a sideways Pascal's Triangle. Let's say our word is "ABCDE".

- A B C
- B C D
- C D E

Let's look at each individual spot and how many paths there are to them. The "C" in the top right and bottom left have only one path to them, and the same can be said of the "B"s and "A". So, we can write the grid like:

- 1 1 1
- 1 C D
- 1 D E

Now, looking at the remaining "C", there are two ways to reach it. You can either come in from above, or come in from the left. There is only one way to come in from the top and one way to come in from the left, we can say that there are two ways to reach it:

- 1 1 1
- 1 2 D
- 1 D F

Now, for the right-most D, we can see that there are two ways to come in from the left, and one way to come in from above:

- 1 1 1
- 1 2 3
- 1 D E

Following a similar process for the last two letters, we can map out the number of paths to each spot in the matrix as:

- 1 1 1
- 1 2 3
- 1 3 6

Giving us a final answer of 6.

This pattern should look familiar. It is actually a Pascal's Triangle in a different orientation. With a much larger matrix, we would get (sorry for terrible formatting):

- 1 1 1 1 1 1
- 1 2 3 4 5 6
- 1 3 6 10 15 21
- 1 4 10 20 35 46
- 1 5 15 35 70 116
- 1 6 21 46 116 232

For a Pascal's Triangle, one can simply use a Combination function to find the value for any point in the triangle.

I haven't solved it yet, but for those completely clueless about where to even start, hopefully this helps.

rajneshmalik + 1 comment I implemented your logic but some of test cases are failing. Can you please point out mistake in this.

int solve(int n, int m) { int i,j; int arr[n][m]={0};

`for(i=0; i<n; i++) { for(j=0; j<m; j++) { if(i == 0 || j == 0) arr[i][j] = 1; else arr[i][j] = arr[i][j-1] + arr[i-1][j]; } } return arr[n-1][m-1];`

}

dr0opy + 0 comments check your constraints for this question 1 ≤ m,n ≤ 10^6. you can't take such large matrix

3Murthi + 0 comments Not 46 it's 56. Since 35+21=56

michellerodri247 + 0 comments Matrix is an exciting topic in Mathematics real estate photo retouching . I think the topics related to the matrix are easy to study. The thing needed to solve the matrix is only the basics. If a person has a basic idea of the matrix then it is really easy to handle the problems of the matrix.

[deleted] + 1 comment **Prerequisites to solve this problem**1.

**fast exponentiation**#define ll long long int #define mod %1000000007 ll fastexpo(ll a, ll n) { ll ret=1; ll b=a; while(n) { if(n&1)ret=(ret*b)mod; //if(n==odd) b=(b*b)mod; n>>=1; // n/=2 } return (ll)ret; }

2.

**X^(-1) mod(p) can be written as X^(p-2) mod(p)**vikasjha + 1 comment We can skip fast exponentiation, if we know the extended Euclid's Algorithm to find the modulo inversion.

Mohit_Yadav_389 + 0 comments i love extended euclid's algorithm as it takes like no time to calculate MMI of a number;

Mohit_Yadav_389 + 0 comments If anyone want euclid's extended algo; Here we go;

int mmi(int a, int m){ if(a==1)return 1; int e=m; int f=a; int x= 0; int y= 1; unsigned long long u = 1; int v = 0; int q=0,r=0,c=0,d=0; while(f!=1){ q = e/f; r = e%f; c = x- q*u; d = y - q*v; x = u; y = v; u = c; v = d; e = f; f = r; } return (u+m)%m; }

shell87301 + 1 comment Passes all TC:

#include <bits/stdc++.h> using namespace std; const int p=1000000007; int n, m, t; long long fmod(long long N) { if (N<2) return 1; else return (N*fmod(N-1))%p; } long long mmi(long long x) { long long result=1, e=p-2; while (e) { if (e & 1) result = (result*x)%p; x = (x*x)%p; e >>= 1; } return result; } int main() { cin >> t; while (t--) { cin >> n >> m; printf("%lld\n", ((fmod(m+n-2)*mmi((fmod(m-1)*fmod(n-1))%p))%p)); } return 0; }

sarbajitnandey + 0 comments what's the logic behind it?

rajeevbhatt595 + 2 comments Can anyone improve my code, Test cases 5,6,7,8 are timed out:

from math import factorial for _ in range(0, int(raw_input())): m, n = map(int, raw_input().split()) p1 = 1 if (m > n): for i in range(m, m+n-1): p1 = p1 * i print (p1/factorial(n-1))%((10**9)+7) else: for i in range(n, m+n-1): p1 = p1 * i print (p1/factorial(m-1))%((10**9)+7)

1998rkrk + 0 comments Great post! I appreciate you for the effort you take to share your knowledge with people. I can find many things that are still unaware. Thanks for you time and knowledge. Great!!! verizon email problem

stempl + 0 comments I have a different view. If I understand well. We have to go from top-left to bottom-right. We have two types of step: R(ight), D(own). (m-1) -> R (n-1) -> D

So just have to count the Permutations of two type of steps (patterns or ways). The problem if I am right hard to calculate. If I am wrong please let me know!

mmcss + 1 comment The solution has little to do with elementary facts about combinatorials, and a lot to do with properties of modular arithmetic where the modulus is a prime number. 1000000007 happens to be a prime number. I copied the solution provided by shell87301, below, only translating it to Python3. It was both gratifying and humiliating to see it work after so many tries on my own.

sbahrami + 0 comments Hi,

I am trying the following in python:

def solve(n, m):

`if m==1 or n==1: return 1 elif n==2 and m>1: return m%c else: x=reduce(lambda x,y:pow(x*y,1,c), [pow(m+i,1,c) * pow(1+i,c-2,c) for i in range(n-1)]) return x`

any idea why it is not fast enough? I know that it is O(n).

daniel_yardley + 1 comment I thought about it this way: there is nothing special about it being a word (like "AWAY"), all we're trying to do is travel from the top left corner of a matrix to the bottom right by only moving right (R) or down (D).

If the matrix has 'm' rows and 'n' columns, then any valid path needs 'm-1' moves down and 'n-1' moves to the right, so 1 simple path could look like this: RRRRR....RRDDDDD....DD with 'n-1' Right moves and then 'm-1' Down moves.

How many valid paths are there? Well, each valid path has a total of (n+m-2) moves that can be reordered in (n+m-2)! ways. However, all the R's are identical so we need to remove all arrangements that are just shifting the R's around. Same argument applies to the D's, so the total number of valid paths is (n+m-2)! / (n-1)! / (m-1)! (this is why Pascal's triangle is also a correct way of thinking about the number of valid paths). To calculate this, follow the instructions in the discussion of the Sherlock and Permutations problem.

mmcss + 0 comments In the abstract, the problem is to find the number of paths from (0,0) to any point (i,j) in a grid whose nodes are pairs of non-negative integers. Looking at it this way, it's pretty easy to see that Npath(i,j) = Npath(i-1,j) + Npath(i, j-1). Picture Pascal's Triangle. So, the solution is the number of combinations of n + m - 2 things taken n - 1 at a time -- or m - 1 at a time, it doesn't matter. The problem I'm having is that my solution is timing out, and I don't know a faster way to compute the answer.

leontp587 + 1 comment I'm confused how it can be gauranteed that (n-1)!(m-1)! is not a multiple of p, such that Fermat's Little Theorem applies?

ajs672 + 0 comments p is prime so by definition it cannot be the product of two smaller numbers. Both n and m are smaller than p so the factorial product will never contain p as a factor and thus will never be a multiple of p.

Sort 31 Discussions, By:

Please Login in order to post a comment