HackerEarth Movement in arrays problem solution

In this HackerEarth Movement in arrays problem solution Consider an array A of size N. You start from the index 0 and your goal is to reach index N - 1 in exactly M moves.

At any index, you can move forward or backward by a number of steps that is equal to a prime divisor of the value which exists at that index. You cannot go beyond the array while going forward or backward.

Write a program to determine whether it is possible to reach index N - 1 in M moves.

HackerEarth Movement in arrays problem solution.

#include<bits/stdc++.h>
using namespace std;
vector<vector<bool> > multiply(vector<vector<bool> > a,vector<vector<bool> > b)
 {
    int i,j,k;
    int r1=a.size();
    int r2=b.size();
    int c1=a[0].size();
    int c2=b[0].size();
    
    vector<vector<bool> > c(r1,vector<bool> (c2));
    for(i=0;i<r1;i++)
      {
        for(j=0;j<c2;j++)
          {
            for(k=0;k<r2;k++)
              {
                 if(a[i][k]&&b[k][j])
                    c[i][j]=true;
              }
          }
      }
    return c;
 }

vector<vector<bool> > pow(vector<vector<bool> > a,long long n)
  {
    if(n==0)
      {
        assert(0);
        return a;
      }
    if(n==1)
      return a;

    vector<vector<bool> > b=pow(a,n/2);
    b=multiply(b,b);
    if(n%2)
      b=multiply(a,b);
    return b;
  }

vector<int> getFactors(int x)
 {
    vector<int> fact;
        if(x%2==0)
         {
            fact.push_back(2);
            while(x%2==0)
                x/=2;
           }
    for(int i=3;i*i<=x;i+=2)
     {
        if(x%i==0)
         {
            fact.push_back(i);
            while(x%i==0)
                x/=i;
           }
     }
     if(x!=1)
        fact.push_back(x);
    return fact;
 }

void eval()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    int moves;
    cin>>moves;
    
    vector<vector<bool> > mat(n, vector<bool>(n));
    vector<vector<bool> > graph(1, vector<bool>(n));
    graph[0][0]=1;
    
    for(int i=0;i<n-1;i++)
     {
        vector<int> factors = getFactors(a[i]);
        for(int j=0;j<factors.size();j++)
            {
                int x = factors[j];
                if(i-x>=0)
                    mat[i][i-x]=1;
                if(i+x<n)   //less than n-1
                    mat[i][i+x]=1;
            }
     }

    mat = pow(mat, moves);
    graph = multiply(graph,mat);
    if(graph[0][n-1]==1)
        cout<<"YES\n";
    else
        cout<<"NO\n";
}

int main()
{
    int t;
    cin>>t;
    while(t--) 
     {
        eval();
     }
}

Second solution

#include<bits/stdc++.h>


using namespace std;

#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<ll int,ll int>
#define mp make_pair
#define pb push_back

vector<int>v;
int mv,n;
vector<vector<int> > mul(vector<vector<int> > a,vector<vector<int> > b)
 {
    int i,j,k,r=a[0].size(),c=a.size();
    vector< vector<int> > ans(r);
    for(i=0;i<r;i++)
      {
        ans[i].resize(c,0);
        for(j=0;j<c;j++)
          {
            for(k=0;k<r;k++)
                ans[i][j]+= a[i][k]*b[k][j];
          }
      }
    return ans;
 }
 
vector<vector< int > > mat_pow(vector<vector< int > > mat,int n)
  {
    if(n==1)
      return mat;
    vector<vector< int > > ans=mat_pow(mat,n/2);
    ans=mul(ans,ans);
    if(n%2)
      ans=mul(mat,ans);
    return ans;
  }
int foo()
{
    int i,j;
    vector<vector< int > > mat(n);
    for(i=0;i<n;i++)
    {
        mat[i].resize(n,0);
        int fac;
        fac=2;
        if(v[i]%fac==0)
        {
            if(i+fac<n)
                mat[i][i+fac]=1;
            if(i-fac>=0)
                mat[i][i-fac]=1;
            while(v[i]%fac==0)
                v[i]/=fac;
        }
        for(fac=3;fac*fac<=v[i];fac+=2)
        {
            if(v[i]%fac==0)
            {
                if(i+fac<n)
                    mat[i][i+fac]=1;
                if(i-fac>=0)
                    mat[i][i-fac]=1;
                while(v[i]%fac==0)
                    v[i]/=fac;
            }
        }
        if(v[i]>1)
        {
            fac=v[i];
            if(i+fac<n)
                mat[i][i+fac]=1;
            if(i-fac>=0)
                mat[i][i-fac]=1;
        }
    }
    mat= mat_pow(mat,mv);
    return mat[0][n-1];
}
int main()
{
    int t;
    cin>>t;
    assert( t>=1 && t<=10);
    while(t--)
    {
        int i,j,m;
        cin>>n;
        assert( n>=2 && n<=40);
        v.clear();
        v.resize(n);
        rep(i,n){
            cin>>v[i];
            assert( v[i]>=1 && v[i]<=1000000);
        }
        cin>>mv;
        assert( mv>=1 && mv<=1000000);
        if(foo())
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}