GN_THEORY - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kishan Gadhiya
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

2059

PREREQUISITES:

Prime Factorization

PROBLEM:

After solving some Graph Theory related problems KBG challenged Sameer to solve following problem.

You are given an integer N and Q queries. There is an undirected weighted edge between x and y for following conditions:

  • 1 \leq x \leq N.
  • y is divisor of x and weight of this edge will be x divide by y (x/y).

Each query is of the form:

  • u v: Given two integers u and v (1 \leq u , v \leq N),

There is no multiple edges and self loops in graph.

For each query, find the minimum possible cost to reach v from u.

EXPLANATION:

We can always write v as u \times A / B, where A and B are integers > 1 (there are no self loops).

So, it is clear that there always exist a path of length at most 2 from u to v (u → (u \times A) → (v = u \times A / B)). The weight of this path is A + B.

For the minimum the path weight, there should not be any common factor of A and B (GCD(A, B) = 1) because in that case we can always divide A and B by their common factor to reduce the path weight. This leads to a contradiction!

We know that X \times Y \geq X + Y for X, Y \geq 2. This can be easily proved by taking the larger among X and Y to the left side of the inequality. Using this fact it is clear that if A or B can be broken into any 2 factors \geq 2 then we will reduce the path weight. In other words, if A = P \times Q, where P, Q \geq 2 then P + Q \leq A.

Hence, for the minimum path weight we will have to keep on breaking A and B into factors (\geq 2) so that no further breaking is possible. This clearly implies that we need prime factorization because primes cannot be broken further.

We can find out the prime factorization of u and v. Let u = 2^{u_1} \times 3^{u_2} \times 5^{u_3} ... and v = 2^{v_1} \times 3^{v_2} \times 5^{v_3} ... then the combined A / B factor can be written as 2^{v_1-u_1} \times 3^{v_2-u_2} \times 5^{v_3-u_3} ...

The path weight for this would be 2 \times abs(v_1-u_1) + 3 \times abs(v_2-u_2) + 5 \times abs(v_3 -u_3) + … because the weights add up for A and B as it is. This would be the minimum one for the reasons stated above.

This can be found out using prime factorization using sieve and a hash map.

TIME COMPLEXITY:

O(log(U)) + O(log(V)) for each test case and O(Nlog(log(N))) for precomputation.

SOLUTION:

Setter's solution
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
using   ll = long long;
using   ld = long double;
 
#define fast            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
#define pb              push_back
#define mp              make_pair
#define F               first
#define S               second
#define pii             pair<int , int>
#define int             long long int
#define endl            "\n"
 
 
#define ALL(v)          v.begin(),v.end()
#define ALLR(v)         v.rbegin(),v.rend()
// #define sz(v)           (int) v.size()
#define PI              3.14159265358979323
#define inf             LLONG_MAX
#define ones(x)         __builtin_popcount(x)
#define mod             1000000007
#define MOD             998244353
 
ll mod_pow(ll a,ll b,ll m)
{
        ll res = 1;
        while(b)
        {
                if(b&1)
                {
                        res=(res*a) % m;
                }
                a=(a*a) % m;
                b>>=1;
        }
        return res;
}
 
ll mod_inverse(int a , int m)
{
        return mod_pow(a , m - 2 , m);
}
 
const int N = 1e5 + 5;
 
int lpf[N];
 
void pre() {
        for(int i = 2; i < N; ++i) {
                if(lpf[i] == 0) {
                        for(int j = i; j < N; j += i) {
                                lpf[j] = i;
                        }
                }
        }
}
 
void solve()
{
        int n , q;
        
        cin >> n >> q;
        
        for(int i = 0; i < q; ++i) {
                int u , v;
                
                cin >> u >> v;
                
                int dummy_u = u;
                int dummy_v = v;
                
                map<int , int> frq;
                
                while(dummy_u > 1) {
                        int y = lpf[dummy_u];
                        while(dummy_u % y == 0) {
                                dummy_u /= y;
                                frq[y] += 1;
                        }
                }
                
                while(dummy_v > 1) {
                        int y = lpf[dummy_v];
                        while(dummy_v % y == 0) {
                                dummy_v /= y;
                                frq[y] -= 1;
                        }
                }
                
                int res = 0;
                
                for(auto r : frq) {
                        res += abs(r.S) * r.F;
                }
                
                cout << res << endl;
        }
}   
 
signed main() {
        fast;
        
        int t = 1;
        
        pre();
        
        cin >> t;
        
        while(t--) {
                solve();
        }
 
        return 0;
}

Editorialist's Solution
#define MAXN 100001
using namespace std;
int spf[MAXN];
void sieve(){
	spf[1]=1;
	for(int i=2;i<MAXN;i++)spf[i]=i;
	for(int i=4;i<MAXN;i+=2)spf[i]=2;
	for(int i=3;i*i<MAXN;i++){
		if(spf[i]==i){
			for(int j=i*i;j<MAXN;j+=i)
				if(spf[j]==j)
					spf[j]=i;
		}
	}
}
vector<int> getFactorization(int x){
	vector<int>ret;
	while(x!=1){
		ret.push_back(spf[x]);
		x=x/spf[x];
	}
	return ret;
}
int main() {
    sieve();
	int T;
	cin >> T;
	while(T--){
	    int N,Q;
	    cin >> N >> Q;
	    for(int i=0;i<Q;i++){
	        long long ans=0;
	        int U,V;
	        cin >> U >> V;
	        vector<int>res1=getFactorization(U);
	        map<int,int>ff;
	        for(auto x:res1)ff[x]++;
	        vector<int>res2=getFactorization(V);
	        for(auto x:res2)ff[x]--;
	        for(auto x:ff){
	            ans+=abs(x.second)*x.first;
	        }
	        cout << ans << endl;
	    }
	}
	return 0;
}

https://www.codechef.com/viewsolution/67945388
WA test cases feature not working on my solution… The approach is same as that of the editorial…if anyone could debug/make claim on correctness it would be of great help.

1 Like

You can check my code if it helps.

Code

1 Like

Line number 28 to line number 41 is wrong, that’s not how linear sieve is done. Linear Sieve - Algorithms for Competitive Programming (cp-algorithms.com)

A simpler code
Link to my solution

That is correct…The bug was in the query, where I set prime factor to -1 once a prime factor matches…It affects the next query where same number is asked.

I am not getting the fact where the code is failing. Can u please explain? :slight_smile:

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define int long long
#define ld long double
#define endl "\n"
#define pi  3.141592653589
#define INF 1e18
#define vi  vector<int>
#define vvi vector<vector<int>>
#define mi map<int,int>
#define mpi map<pair<int,int>,int>
#define vpi vector<pair<int,int>>
#define pr  pair<int,int>
#define mp  make_pair
#define triplet pair<int,pair<int,int>>
#define ff first
#define ss second
#define pb push_back
#define MAX INT_MAX
#define MIN INT_MIN
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define read(x) int x; cin>>x
#define pD(x,y) cout<<fixed<<setprecision(y)<<x
#define google(tno) cout<<"Case #"<<tno<<": "
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define mod 998244353
#define LMAX 9223372036854775807
const int MOD=1e9+7;
const int GN=1e7+10;
#define upperToLower(x) char(x | ' ')
#define lowerToUpper(x) char(x & '_')

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<bool> sieve(GN,1);
int dsieve[GN];
vi fact(GN,1);

/*---------------------------------------------------------------------------------------------------------------------------*/
bool isPrime(int n){for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}
void primeSieve(){sieve[0] = sieve[1] = false;for (int i = 2; i*i<= GN; i++) {if (sieve[i]) {for (int j = i*i; j <= GN; j += i)sieve[j] = false;}}}
void divSieve(){for(int i=1;i*i<=GN;i++){for(int j=i;j<=GN;j=j+i){++dsieve[j];}}}
vector<vector<int>> matProd(vector<vector<int>> A,vector<vector<int>> B,int size){int sum=0;vector<vector<int>> C(size);
for(int i=0;i<size;i++){for(int j=0;j<size;j++){for(int k=0;k<size;k++){sum+=A[i][k]*B[k][j];}C[i].pb(sum);sum=0;}}return C;}
vector<vector<int>> matExp(vector<vector<int>> A,int n,int size){
if(n==0){for(int i=0;i<size;i++){for(int j=0;j<size;j++){if(i==j) A[i][j]=1; else A[i][j]=0;}}return A;}
if(n==1)return A;
vector<vector<int>> temp=matExp(A,n/2,size);if(n%2==0)return matProd(temp,temp,size);else return matProd(A,matProd(temp,temp,size),size);}
vector<int> prefixSum(vector<int> &A){vector<int> res(A.size());res[0]=A[0];for(int i=1;i<A.size();i++){res[i]=A[i]+res[i-1];} return res;}
void printMatrix(vector<vector<int>> &A,int n,int m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<A[i][j]<<" ";}cout<<endl;}}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int binexp(int x,int n){int a=x;int prod=1;while(n){if(n%2==1)prod=prod*a;a=a*a;n=n/2;    }return prod;}
map<int,int> primeFactorisation(int n){map<int,int> mpp;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0){++cnt;n=n/i;}mpp[i]=cnt;}}if(n>1)mpp[n]=1;return mpp;}
vector<int> merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> temp;int ptr1=0;int ptr2=0;int c=0;while(true){if(ptr1==m || ptr2==n)break;if(nums1[ptr1]<nums2[ptr2]){temp.push_back(nums1[ptr1]);ptr1++;}else{temp.push_back(nums2[ptr2]);ptr2++;}c++;}for(int i=ptr1;i<m;i++){temp.push_back(nums1[i]);c++;}for(int i=ptr2;i<n;i++){temp.push_back(nums2[i]);c++;}return temp;}
int modexp(int a, int b, int m) {a %= m;int res = 1LL;while (b > 0) {if (b & 1)res = (res%m *1LL* a%m) % m;a = (a%m *1LL* a%m) % m;b >>= 1;}return res%m;}
void factSieve(){for(int i=1;i<GN;i++)fact[i]=(fact[i-1]%MOD*1LL*i%MOD)%MOD;}
int modinv(int a){return modexp(a,MOD-2,MOD);}
int nCr(int n,int r){int nmr=fact[n]%MOD;int dmr=(fact[r]%MOD*1LL*fact[n-r]%MOD)%MOD;return (nmr%MOD *1LL* modinv(dmr)%MOD)%MOD;}
/*--------------------------------------------------------------------------------------------------------------------------*/



void solve()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,q;
        cin>>n>>q;

        vector<vector<pair<int,int>>> graph(n+10);
        for(int i=1;i<=n;i++){
            for(int j=i*2;j<=n;j+=i){
                graph[i].pb({j,j/i});
                graph[j].pb({i,j/i});
            }
        }
        // NLogN
        // Dijkstra
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,1});
        vi dist(n+10,INT_MAX);
        dist[1]=0;
        dist[0]=0;
        while(!pq.empty())
        {
            int nodeNum=pq.top().second;
            int currDist=pq.top().first;
            pq.pop();
            for(auto &it : graph[nodeNum])
            {
                int adjNodeNum=it.first;
                int wt=it.second;
                if(currDist+wt<dist[adjNodeNum])
                {
                    dist[adjNodeNum]=currDist+wt;
                    pq.push({dist[adjNodeNum],adjNodeNum});
                }
            }
        }
        while(q--)
        {
            int u,v;
            cin>>u>>v;
            if(u==v)
            {
                cout<<0<<endl;
                continue;
            }
            int pu=min(u,v);
            int pv=max(u,v);
            
            int g=__gcd(pu,pv);
            if(g>1)
            {
                if(pv%pu==0)
                {
                    cout<<pv/pu<<endl;
                }
                else    
                    cout<<pu/g + pv/g<<endl;
            }
            // g=1
            else{
                cout<<dist[u]+dist[v]<<endl;
            }
        }

    }
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    auto start1 = high_resolution_clock::now();
    solve();
    auto stop1 = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop1 - start1);
    cerr << "Time : " << duration . count() / 1000 << endl;

return 0;
}








































Loved this problem!!

1 Like

Please tell why taking gcd will leads to contradiction ?

can anyone tell me what will be the answer for u = 6 and v = 36.

In here suppose pu =2, and pv = 20

then your answer will be 10.

but we can actually go in 7 moves. 2->10 ->20 (5+2)

5 as we can go from 6 to 12 then from 12 to 36 , := 12/6 + 36/12 = 2 + 3 = 5

but according to editorial gcd will be 6 so answer should be 6/6 + 36/6 = 6.

answer will be 5

We can actually solve this using Djikstras.(Not easier than other soln…just a different take)
Preprocess step: build the adj list of the graph in O(NlogN) and run Dijkstra’s with 1 as source vertex(We get the shortest distance of all nodes from 1 from Djikstras).
Now answer to each query (u,v) = dist(v)+dist(u)-2*dist(gcd(u,v))

2 Likes

Solution using Dijkstra’s. Same algorithm as pointed out by @tripledamn

Submission link

I am unable to solve problems like this (like how came to know gcd/lcm will get the ans?)
Any tips?