We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Matrix Tracing
  5. Discussions

Matrix Tracing

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 51 Discussions, By:

votes

Please Login in order to post a comment

  • q1a2z3
    5 years ago+ 4 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.

    26|
    Permalink
    View more Comments..
  • [deleted] 6 years ago+ 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)

    12|
    Permalink
  • Mohit_Yadav_389
    5 years ago+ 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;
    }
    
    7|
    Permalink
  • daniel_yardley
    3 years ago+ 2 comments

    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.

    5|
    Permalink
  • chetbhateja
    1 year ago+ 2 comments

    Just for fun, a code golf solution in Python:

    def solve(n, m):
        inv=lambda a,b,c,d:(b<2)*d or inv(b,a%b,d,c-a//b*d)
        p,q,C=1,1,10**9+7
        for i in range(m,n+m-1):
            p,q=p*i%C,q*(i-m+1)%C
        return p*inv(q,C,1,0)%C
    

    To avoid timing out this uses the factorial formula for the choose function, modding out at each step so that multiplication does not become too costly. Note that building tables can take quadratic time while the formula takes linear time. To tackle the division in the formula inside the modulus, a modular inversion function based on the Euclidean algorithm is written on the first line.

    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature