we have to find min cost path in a mtrix from top left to bottom right.

Move allowed -> Right,left,Bottom,Up.

I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?

Input: given n and m

Task : For given n and m we have to calculate (n+m-2)C(n-1) mod 1000000007 where c is binomial coefficient

Constraints : 1 <= T <= 10^3

1 ≤ m,n ≤ 10^6

My solution

Accepted solution

For the given test case(Which I is used in ideone)

1) Both are passing in ideone

2) My solution is failing on hackerrank(Segmentation fault) other one is passing on hackerrank

Can anyone tell me why my solution is not getting accepted on hackerrank ?

Problem link

Problem link : PK and interesting Language

I read the editorial but I didn't find the proof of correctness in editorial. Can anyone explain with the recurrence,how the below logic is working thanks in advance.

Editorial:

Complexity(per query): O(z^3 log(l)) where z is the number of alphabets and l is the length of word.

Explanation: Suppose we have a graph having each english alphabet as a vertex. There is an edge between the ith and jth english alphabet if the entry a[i][j]=1, where a is the input matrix. Now each word in the language is simply a path from the starting alphabet to the ending alphabet. To calculate the numbers of words of length l ending at particular alphabet,we need to calculate total paths of length l-1 ending at that alphabet. This can be found by raising the adjancy matrix to the power l-1. The jth number in the ith row of this matrix gives the number of words of length l starting at character i and ending at character j. To find the total number of words ending at a particular alphabet take the sum of all the numbers in the jth column.

input:

10 1 2

1

100

debug val 1 and debug val 2 are printing are same but req which is equal to (debug val 1 — debug val 2) is not getting zero ?

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int l,s1,s2;
    cin>>l>>s1>>s2;
    int q;
    cin>>q;
    long long int relspe = abs(s2-s1);
    while(q--){
        long long int a;
        cin>>a;
        cout<<"debug val 1  "<<sqrt(2)*l<<endl;
        cout<<"debug val 2 "<<sqrt(2)*sqrt(a)<<endl;
        double req = abs(sqrt(2)*l-sqrt(2)*sqrt(a));
        cout<<"req "<<req<<endl;
        double ans = req/relspe;

        cout<<ans<<endl;
    }
}

https://www.hackerrank.com/challenges/sherlock-and-moving-tiles/problem

This is authors solution 55959992

This is my solution 55959887

I am getting TLE although i have used the same approach

https://mirror.codeforces.com/contest/675/problem/D

I tried many test cases ,I am passing all of them But it is failing at test case 5 on codeforces. Since test case are quite large ,I am unable to figure out my error.Please forgive me if my question is not good. 55748387(My submission)

https://mirror.codeforces.com/contest/52/problem/C

47841668 My solution to to codeforces 455A giving wrong answer on test case 12 ,can anyone tell me where i did the mistake?