HackerEarth Shil and Lab Assignment problem solution

In this HackerEarth Shil and Lab Assignment problem solution For the lab assignment of this week , Shil got N numbers A1 , A2, … AN. He must assign each of these numbers a unique integer value from 1 to M. Let Ci be the integer assigned to Ai . Shil must assign numbers in such a way that maximum number of Ai are divisible by their Ci . You must print maximum numbers of Ai that could be made divisible by Ci in optimal assignment.

HackerEarth Shil and Lab Assignment problem solution.

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<pi,int>
#define f first
#define s second
#define ll long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
vector<int>g[1011];
ll A[1011],B[1011];
int given[100011];
int ass[1011];
bool bpm(int i,map<int,bool>&seen){
    for(auto x:g[i]){
        if(seen.find(x)==seen.end()){
            seen[x]=1;
            if(given[x]==-1){
                given[x]=i;
                return true;
            }
            else{
                if(bpm(given[x],seen)){
                    given[x]=i;
                    return true;
                }
            }
        }
    }
    return false;
}
int main(){
    freopen("input-9.txt","r",stdin);
    freopen("output-9.txt","w",stdout);

    int N;
    int M;
    cin >> N >> M;
    rep(i,N){
        cin >> A[i];
        for(int j=1;j<=sqrt(A[i]);j++){
            if(A[i]%j==0){
                if(j!=A[i]/j){
                    if(j<=M)
                        g[i].pb(j);
                    if(A[i]/j<=M){
                        g[i].pb(A[i]/j);
                    }
                }
                else{
                    if(j<=M){
                        g[i].pb(j);
                    }
                }
            }
        }
    }
    rep(i,100011){
        given[i]=-1;
    }
    int ans=0;
    rep(i,N){
        map<int,bool>seen;
        if(bpm(i,seen)) ans++;
    }
    cout<<ans;
}

Second solution

#include <bits/stdc++.h>
#define MAX 1004
using namespace std;

vector <int> v[MAX];
int match[100005];


bool bpm(int x, set <int> seen, int match[])
{

    for ( int i = 0; i < (int)v[x].size(); i++ ) {
        if ( seen.find(v[x][i]) == seen.end() ) {
            seen.insert(v[x][i]);
            if ( match[v[x][i]] == -1 || bpm(match[v[x][i]], seen, match) ) {
                match[v[x][i]] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n,m,ans = 0,x;
    cin >> n >> m;
    assert(n >= 1 && n <= 1000);
    assert(n <= m);
    assert(m >= 1 && m <= 100000);

    for ( int i = 0; i < n; i++ ) {
        cin >> x;
        assert(x >= 1 && x <= 100000);
        int LIM = (int)sqrt(x);
        for ( int j = 1; j <= LIM; j++ ) {
            if ( x%j == 0 ) {
                if ( j <= m ) v[i].push_back(j);
                if ( x/j != j && x/j <= m ) v[i].push_back(x/j);
            }
        }
    }

    memset(match, -1, sizeof(match));

    for ( int i = 0; i < n; i++ ) {
        set <int> seen;
        if ( bpm(i,seen,match) ) ans++;
    }

    cout << ans << endl;

    return 0;
}

HackerEarth Shil and Lab Assignment problem solution.

Second solution

Leave a Reply