Another Problem About Dividing Numbers :: Codeforces Round 725 D

Problem link

In this problem you will be given two integer number a and b. You need to make a and b equal in exactly k operation(s).  In one operation you can either,

• Take an integer c (c>1 and a should be divisible by c) and replace a with ac
  
• Take an integer c
(c>1and b should be divisible by c) and replace b with bc.

Observations: If we at least  need x moves to make a and b equal and we have at most y moves which is total number of moves we can make in total. A move is choosing such a C discussing above. Then we can also make a and b equal by x+1,x+2,x+3.......y-2,y-1,y moves. [for better understanding a paperwork may help]

Explanation:

For finding the minimum number of moves to make a and b (if a!=b) are equal will be 1 or 2. 

>>if gcd(a,b)==min(a,b) then it will be 1.

lets say, a=36 and b=12;

gcd(36,12) = min(36,12) = 12 

we can make a=12 by dividing 36 by 3 in one move.

>>if gcd(a,b)!=min(a,b) then it will be 2. Because we need to divide both a and b to make equal to its gcd.

For finding the at most moves we have, we had to find number of prime factors both for a and b. because at most we can divide them until they left any prime factors.

For calculating the Number of prime factors. we will be needed prime numbers. For this purpose a simple sieve will work fine.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define int long long #define IOS ios::sync_with_stdio(false); int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);} const int maxn=100005; bitset<maxn+5>bs; vector<int> prime; void seive(){ bs.set(); bs[0]=0; bs[1]=0; for(int i=2;i<maxn;i++){ if(bs[i]){ prime.pb(i); for(int j = i*i; j<maxn;j+=i)bs[j]=0; } } } ///solution void solution(){ int a,b,k; cin>>a>>b>>k; if(a==b && k==1){ cout << "NO\n"; return; } int cnta=0,cntb=0,now=a; for(auto it:prime){ if(it*it>now){ break; } while(now%it == 0){ now/=it; cnta++; } } if(now>1)cnta++; now=b; for(auto it:prime){ if(it*it>now )break; while(now%it == 0){ now/=it; cntb++; } } if(now>1)cntb++; int x=gcd(a,b); int atmost=cnta+cntb,least=0; if(x==min(a,b))least=1; else least=2; if(least<=k && atmost>=k){ cout << "YES\n"; } else cout << "NO\n"; } signed main() { IOS int t; t=1; seive(); cin>>t; while(t--){ solution(); } return 0; }

A simple Cycle detection Problem using DFS :: Codeforces 977E

 Problem Link

In this problem several connected components are given, we need to find number of such components with cycle.

A components is contain a cycle if and only if all of its vertices has degree exactly 2.

To find connected components of the graph, we will use  a simple dfs through unvisited nodes. You can learn dfs from here

After that we will check if all the vertices has degree exactly 2 or not.

Official Editorial

Code:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include<bits/stdc++.h> using namespace std; #define pb push_back ///the connected component is a cycle iff the degree of each its vertex equals to 2 const int maxn=200005; vector<int>edge[maxn],connected; int vis[maxn],degree[maxn]; int cnt=0; void dfs(int u){ vis[u]=1; connected.pb(u); for(auto it:edge[u]){ if(vis[it]==0){ dfs(it); } } } int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int u,v; cin>>u>>v; edge[u].pb(v); edge[v].pb(u); degree[u]++; degree[v]++; } for(int i=1;i<=n;i++){ if(vis[i]==0){ connected.clear(); dfs(i); bool ok=1; for(auto it:connected){ if(degree[it]!=2){ ok=0; } } if(ok){ cnt++; } } } cout << cnt << endl; }

Solving a Problem With Bitmask DP Codeforces 550B

 Problem Link

In this problem the constraints is very low it can only be 15, that's why it gives a hints that it could be solve with bitmask.

Bitmask is a masking technique, by which we can have the all possible combination in 2^n complexity rather than n! complexity. To learn more about bitmask click here 

In this problem we have to calculate number of ways to choose a sum where number of elements in the sum is greater than 1 and the sum itself is at least l and at most r. And difference between maximum and minimum element which are contributed to the sum is at least x.

To do that we will check all possible subset of the set and check the requirements satisfies or not.

Code:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define highest(x) numeric_limits<x>::max()
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
    ll n,l,r,x;
    cin>>n>>l>>r>>x;
    ll arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    ll ans=0;
    for(int i=0;i<=pow(2,n);i++){
        int cnt=0;
        ll sum=0,mini=highest(ll),maxx=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                cnt++;
                sum+=arr[j];
                mini=min(mini,arr[j]);
                maxx=max(maxx,arr[j]);
            }
        }
        if(sum>=l && sum<=r && cnt>=2 && maxx-mini>=x){
            ans++;
        }
    }
    cout << ans << endl;
}
signed main()
{
    IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah
  

Solving An Interactive Problem CF Round 700 Div2 C

First of all, what is an interactive problem?

read it from here

The blog says all about it, still i am showing it roughly and practically.

In interactive problem we have to grab input data from the problem on our demand. we have to make queries and if our query stand valid then the problem (interactor) give us some input and based on these inputs of some limited number of query we have to answer a valid result of this problem.

Lets see a problem,

problem link  

Problem statement:

 

 

Okay, Our hero Homer has an array which is a permutation, but hidden. We have to find any local minimum of the array in at most 100 queries. Wants to know more about local minimum click here

In each query we can get a value of any index we asks for. For finding local minimum we will run a binary search.

For every printf() function or cout << we have to flush

in C++, we can use cout.flush() or fflush(stdout)

Here is the official Editorial of this problem.

Code:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int arr[maxn];
int n;
///solution
void take(int w){
    if(1<=w && w<=n){
        printf("? %d\n",w);
        fflush(stdout);
        scanf("%d",&arr[w]);
    }
}
void solution(){

   //cin>>n;
    scanf("%d",&n);
    int ans;
    arr[0]=n+1;
    arr[n+1]=n+1;
    int left=1, right=n;
    while(left<right){
        int mid=(left+right)/2;
        take(mid);
        take(mid+1);
        if(arr[mid+1]>arr[mid]){
            right=mid;
        }
        else left=mid+1;
    }
    printf("! %d\n",left);
    fflush(stdout);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
    #endif
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah