HackerEarth Shil and Lab Assignment problem solution

YASH PAL, 31 July 202417 February 2026

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

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;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply