IS_THIS_GRAPH - EDITORIAL

PROBLEM LINK:

Click Here

Author: ashwanth2003
Tester: manoj_vajpeyi
Editorialist: ashwanth2003

DIFFICULTY:

MEDIUM

PREREQUISITES:

Adjacency Matrix Properties, Matrix Exponentiation

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
  • add 1
  • 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 adjmat;
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 ++)
        {
            adjmat.mat[i-1][j-1] = reached(i , 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;

    struct mat ans = power(adjmat,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.