GRAPH CONS. FOR THE PROBLEM

1

Problem link: this
I did the problem using dp but i think it is doable by graphs for which i read editorial but soln is not given. Ihave quite inefficient technique for graph cons.
Can anyone help in graph construction as shortest path using dfs will be the answer.
My dp soln:here

2

shortest path using bfs

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
vector<int> edge[20007]; 
void init(){
    for(int i=0;i<20007;i++){  //only till 2*10^4 since it is never better to go more than 2m
         if(i-1>0){ //make sure the edges are in bound
         edge[i].pb(i-1);
         }
         if(2*i<20007){
         edge[i].pb(2*i);
         }
    }
}
ll solve(){
    int n,m;
    cin>>n>>m;
    queue<pair<int,int>> tochk;
    bool found[20007]={0};
    tochk.push(mp(n,0));  //start from n at distance 0
    while(!tochk.empty()){   //standard bfs
        if(tochk.front().first==m){
            return tochk.front().second; //return the distance of m
        }
        for(int i=0;i<edge[tochk.front().first].size();i++){
            if(!found[edge[tochk.front().first][i]]){
                 tochk.push(mp(edge[tochk.front().first][i],tochk.front().second+1));
                 found[edge[tochk.front().first][i]]=1;
            }
        }
        tochk.pop();
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	//cin >>t;
	t=1;
    srand(time(0));
    init();
	while(t--){
	    cout<<solve()<<"\n";
	}
}
1 Like