# IS_THIS_GRAPH - EDITORIAL

Author: ashwanth2003
Tester: manoj_vajpeyi
Editorialist: ashwanth2003

MEDIUM

# PROBLEM:

Given two numbers A, B and the number of operations P, you need to determine the number of ways to perform P operations to convert A to B modulo 10^9+7

The operations are defined as follows:

• multiply by 2
• multiply by 4
• divide by 2
• divide by 4
• subtract 1

After every operation, the number A should lie between 1 to 10 inclusive.

# QUICK EXPLANATION:

• Convert this problem into a graph problem with edge-weights as cost and do matrix exponentiation

# EXPLANATION:

• This problem can be modeled as a graph problem keeping each number {1 ā¦ 10} as nodes and the operations as edges (Note: parallel edges may exist)

• Corner cases for parallel edges:

• 1 ā 2 (multiply by 2 or add 1)
• 2 ā 1 (divide by 2 or subtract 1)
• Our ultimate goal is to find the number of paths from A to B with fixed path length P.

• There is an exciting property with the adjacency matrix of a graph

• A^p[i][j] = number of paths from node i to node j with length exactly P

• I like to leave out the proof of this property as an exercise (hint: induction)

• The adjacency matrix of our problem looks like this

• \left[\begin{array}{lll} 0&2&0&1&0&0&0&0&0&0\\ 2&0&1&1&0&0&0&1&0&0\\ 1&1&0&1&0&1&0&0&0&0\\ 1&1&1&0&1&0&0&1&0&0\\ 1&1&0&1&0&1&0&0&0&1\\ 1&0&1&0&1&0&1&0&0&0\\ 1&0&1&0&0&1&0&1&0&0\\ 0&1&0&1&0&0&1&0&1&0\\ 0&1&0&1&0&0&0&1&0&1\\ 0&1&0&0&1&0&0&0&1&0\\ \end{array}\right]

• Since the constraints for P are very large, we could think of matrix exponentiation to solve our problem

# ALGORITHM:

• Step 1: convert into a graph problem
• Step 2: generate an adjacency matrix of size 10 x 10 for the graph
• Step 3: raise the Adjacency matrix to power P using matrix exponentiation modulo 10^9+7
• Step 4: A^p[i][j] contains the number of paths from node i to node j with length P

# TIME COMPLEXITY

O\left(Q \cdot 10^3 \log \left(10^{18}\right)\right)
= 150 \times 10^3 \times \log \left(10^{18}\right)
= 10^7

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<pair<lli , lli>> vpll;
typedef vector<pair<ld , ld>> vplld;
typedef pair<int,int> pii;
typedef vector<lli> vl;
typedef pair<lli,lli> pll;
typedef priority_queue<lli> pq;
typedef priority_queue<pair<lli,lli>> pqp;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define print(a) for(auto x:a) cout<<x<<" ";cout<<endl;
#define printarr(a , n) for(int i = 0 ; i < n  ;i ++) cout << a[i] << " "; cout << endl;
#define inf 1e18

//
// matrix exponentiation on adjacency matrix
//

struct mat
{
lli mat[10][10];
};

struct mat idenmat;
struct mat zeromat;

int reached(lli i , lli j)
{
int count = 0;
if(i*2 == j) count++;
if(i/2 == j) count++;
if(i+1 == j) count++;
if(i-1 == j) count++;
if(i*4 == j) count++;
if(i/4 == j) count++;
return count;
}

void construct()
{
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) adjmat.mat[i][j] = 0;

for(int i = 1 ; i <= 10 ; i ++)
{
for(int j = 1 ; j <= 10 ; j ++)
{
}
}
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) idenmat.mat[i][j] = (i == j);
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) zeromat.mat[i][j] = 0;

}

void printmat(struct mat a)
{
for(int i = 0;  i < 10 ; i ++)
{
for(int j = 0 ;j < 10 ; j ++)
{
cout << a.mat[i][j] << " ";
}
cout << endl;
}
}

lli mod = 1e9 + 7;

struct mat mul(struct mat a , struct mat b)
{
struct mat c;
for(int i = 0 ; i < 10 ; i ++)
{
for(int j = 0 ; j < 10 ; j ++)
{
c.mat[i][j] = 0;
for(int k = 0 ; k < 10 ; k ++)
{
c.mat[i][j] += (a.mat[i][k]*b.mat[k][j])%mod;
c.mat[i][j] %= mod;
}
}
}
return c;
}

struct mat power(struct mat x, lli n)   //x base n exponent
{
if(n==0) return idenmat;
struct mat pow = idenmat;
while(n)
{
if (n & 1)
pow = mul(pow,x);
n = n >> 1;
x = mul(x,x);
}
return pow;
}

void solve()
{

lli a , b , p;
cin >> a >> b >> p;

cout << ans.mat[a-1][b-1] << endl;

}
int main(){

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
construct();
int t;cin>>t; while(t--)
solve();
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
#define int long long int
const int mod = 1e9 + 7;
const int inf = 5e18;
//const int mod = 998244353;
using namespace std;

vector<vector<int>> mul(vector<vector<int>>mat1,vector<vector<int>>mat2)
{
int n=10;
vector<vector<int>>res(n,vector<int>(n,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int ele=0;
for(int k=0;k<n;k++)
{
ele+=mat1[i][k]*mat2[k][j];
ele%=mod;
}
res[i][j]=ele;
}
}
return res;
}

vector<vector<int>> pow(vector<vector<int>>mat,int p)
{
int n=10;
vector<vector<int>>res(n,vector<int>(n,0));
for(int i=0;i<n;i++) res[i][i]=1;
while(p)
{
if(p%2) res=mul(res,mat);
p=p/2;
mat=mul(mat,mat);
}
return res;
}

void myfun()
{
int a,b,n;
cin>>a>>b>>n;
vector<vector<int>>mat(10,vector<int>(10,0));
for(int i=0;i<10;i++)
{
int cur=i+1;
int nex;
nex=cur+1; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur-1; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur/2; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur/4; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur*2; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur*4; if(nex>0 && nex<11) mat[i][nex-1]+=1;
}
mat=pow(mat,n);
cout<<mat[a-1][b-1]<<"\n";
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("input0.txt", "r", stdin);
//freopen("output0.txt", "w", stdout);
int t = 1;
cin >> t;
while (t--)
myfun();
return 0;
}

1 Like

Nice Problem!, I am also looking for Play with Subarray problems editorial but Iām unable to find that.