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