F - Coprime Present :: Panasonic Programming Contest (AtCoder Beginner Contest 195)

The main observations of this problem is if two number is not coprime, there largest prime factors of their greatest common divisors will not exceed 72.

So, we just check all possible pairs of numbers from a to b. hence there will be atmost 20 primes, upto 72. we can apply a bitmask dp approach to check which numbers will benefits us most.

Problem link

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

/// Bismillahir Rahmanir Rahim #include<bits/stdc++.h> using namespace std; #define ll long long #define IOS ios::sync_with_stdio(false); ///solution void solution(){ ll primes[20]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 53, 59, 61, 67, 71}; vector<ll>dp((1<<20)); ll a,b; cin>>a>>b; dp[0]=1; for(ll i=a;i<=b;i++){ int bit=0; for(int j=0;j<20;j++){ if(i%primes[j]==0) bit|=(1<<j); } for(int j=0;j<(1<<20);j++){ if((j&bit)==0)dp[j|bit] += dp[j]; } } ll ans=0; for(int i=0;i<(1<<20);i++){ ans+=dp[i]; } cout << ans << endl; } signed main() { IOS int t; t=1; //cin>>t; while(t--){ solution(); } return 0; }

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