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