MDIVSET - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Hazem Tarek
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Bitmasking

PROBLEM:

You are given a set A=[A_1,A_2,\dots ,A_N], where A_i \le C for each valid i. Find any set B=[B_1,B_2,\dots,B_M] such that:

  • A is divisible by B.
  • 2 \le B_i \le C, for each valid i.
  • M is the smallest positive integer such that there is at least one set satisfying the previous two conditions.

The set A is said to be divisible by B if each integer in A is divisible by at least one (not necessarily the same for each of them) integer in B.

EXPLANATION:

Observation: An optimal set of B exists which contains only prime numbers.

  • Suppose we have a number X in set B which divides [A_1,A_3,\dots,A_y] in set A. Then any prime divisor of X, say P_x will always divide [A_1,A_3,\dots,A_y]. It may be also possible to divide some other number of set A by P_x which was not divisible by X. Hence it is always optimal to have a set B which contains only prime numbers,

Subtask 1:

Here, C \le 50.

Since the value of C is small enough, we can iterate over all masks of primes that are less than C and check if the current mask covers the set A. Finally, we will output the minimal such set.

Solution
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 50

int main()
{
    vector <int> primes;
    for(int i=2; i<=MAX_N; i++){
        bool ok = true;
        for(int j=2; j<i; j++)
            ok &= (i%j != 0);
        if(ok)
            primes.push_back(i);
    }
    int t;
    scanf("%d",&t);
    while(t--){
        int n ,c;
        scanf("%d%d",&n,&c);
        vector <int> pr;
        for(int i=0; i<primes.size() && primes[i]<=c; i++)
            pr.push_back(primes[i]);
        vector <int> a;
        for(int x,i=0; i<n; i++){
            scanf("%d",&x);

            int mask = 0;
            for(int j=0; j<pr.size(); j++)
                mask |= (x%pr[j] == 0)<<j;
            a.push_back(mask);
        }

        int ans = INT_MAX;
        for(int mask = 1; mask < 1<<pr.size(); mask++){
            bool ok = true;
            for(int&i : a)
                ok &= (i&mask) != 0;
            if(ok && __builtin_popcount(mask) < __builtin_popcount(ans))
                ans = mask;
        }

        printf("%d\n",__builtin_popcount(ans));
        for(int i=0; i<pr.size(); i++) if(ans>>i&1)
            printf("%d ",pr[i]);
        printf("\n");
    }
}

Subtask 2:

it is guaranteed that M \le 2.

If the gcd of all the numbers in set A is not equal to 1, then in this we can have our set B to contain only one element and that element is gcd of all the numbers in set A. Since gcd will be dividing all the elements of the set A.

If gcd equals 1, then we will iterate over all possible B_0 and let g be the gcd of the elements of set A that are not divisible by B_0. Then there must exist at least one g \neq 1 and therefore our set B will be [B_0, g]

Solution
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 7500

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n ,c ,g = 0;
        scanf("%d%d",&n,&c);
        vector <int> a(n);
        for(int&i : a){
            scanf("%d",&i);
            g = g? __gcd(g ,i) : i;
        }

        if(g != 1){
            printf("1\n%d\n",g);
            continue;
        }

        for(int i=2; i<=c; i++){
            g = 0;
            for(int&j : a) if(j%i != 0)
                g = g? __gcd(g ,j) : j;
            if(g != 1){
                printf("2\n%d %d\n",i,g);
                break;
            }
        }
    }
}

Subtask 3:

The condition of M \le 2 is removed.

Claim: There can be at most 1 prime factor of X greater than \sqrt{X}.

Proof:

If possible let there be two distinct prime factors of X which are greater than \sqrt{X}, say P_1 and P_2. As both P_1 and P_2 are different prime factors of X their product P_x=P_1*P_2 should also be the factor of X. But P_x would exceed X as both P_1 and P_2 are greater than \sqrt{X}, which contradicts our assumption, hence there can only be one prime factor of X greater than \sqrt{X}.

Let’s modify the solution of Subtask1 1, a little. A better approach is to iterate over all of primes subsets that are less than or equal to \sqrt{C}. Now for every element in set A that isn’t covered by this mask, we add its prime divisor to the set.

The answer is the set with minimal size overall masks.

Solutions
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 7500

int main()
{
    vector <int> primes ,lp(MAX_N+1);
    for(int i=2; i<=MAX_N; i++) if(!lp[i]){
        for(int j=i; j<=MAX_N; j+=i)
            lp[j] = lp[j]? lp[j] : i;
        primes.push_back(i);
    }

    int t;
    scanf("%d",&t);
    while(t--){
        int n ,c;
        scanf("%d%d",&n,&c);
        vector <int> pr{2};
        for(int i=1; i<primes.size() && primes[i]*primes[i] <= c; i++)
            pr.push_back(primes[i]);
        vector <pair<int ,int>> a;
        for(int x,i=0; i<n; i++){
            scanf("%d",&x);

            int mask = 0;
            for( ; x > 1 && lp[x] <= pr.back(); x /= lp[x])
                mask |= 1<<(find(pr.begin() ,pr.end() ,lp[x])-pr.begin());
            a.push_back({mask ,x});
        }

        bitset <MAX_N+1> ans ,cur;
        ans.set();
        for(int mask = 0; mask < 1<<pr.size(); mask++){
            cur.reset();
            for(int i=0; i<pr.size(); i++) if(mask>>i&1)
                cur.set(pr[i]);
            for(auto&p : a) if((p.first&mask) == 0)
                cur.set(p.second);
            if(!cur[1] && cur.count() < ans.count())
                swap(ans ,cur);
        }

        printf("%d\n",ans.count());
        for(int i=0; i<=MAX_N; i++) if(ans[i])
            printf("%d ",i);
        printf("\n");
    }
}

Subtask 4:

The idea is that instead of brute-forcing the mask of small primes and then checking what numbers are already divisible by something. We can precalculate what will we have to additionally pay for each mask.

Hence, In general, our solution will be:

  • Factorize each number into a mask of small primes with one big prime (possibly).
  • Group the numbers by their big prime.
  • For each big prime find out for which masks, We’ll have to take this big prime additionally,
    and add 1 to answer for those masks (numbers without big prime add inf to bad masks)

Suppose we are working with big prime P, then numbers with this big prime could only have small primes up to C/P. So, We can mark bad masks only on those small primes and all the other primes are not significant for this big prime.

So for any big prime P, let’s say that there are k small primes that are smaller than C/P
in O(2^k * k) we can mark all the bad masks for this prime. And then we can make a query to do 1 on all bad masks of size k and any mask of size P-k. We will then collect them with SOS- DP

We can also group big primes with the same k in batches and do the O(2^k * k) propagation at once.

TIME COMPLEXITY:

O(2^k*k)

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;

#define MAX_C 7500
#define MAX_P 23

vector <int> primes ,lp(MAX_C+1 ,-1);
vector <int> bad[MAX_C+1] ,b[MAX_P+1];
int a[(1<<MAX_P)+1] ,c[(1<<MAX_P)+1];

void solve(){
    int n ,C;
    scanf("%d%d",&n,&C);

    int m = 1 ,k = 1;
    while(primes[m]*primes[m+1] <= C) m++;
    while(k < primes.size() && primes[k] <= C) k++;

    for(int i = 0; i < k; i++)
        bad[i].clear();
    for(int mask = 0; mask < 1<<m; mask++)
        a[mask] = 0;
    for(int i = 0; i <= m; i++)
        b[i] = vector<int>(1<<i);

    for(int i = 0; i < n; i++){
        int x ,mask = (1<<m) - 1;
        scanf("%d",&x);

        for( ; x > 1 && lp[x] < m; x /= primes[lp[x]])
            mask &= ~(1<<lp[x]);
        if(x == 1)
            a[mask] = MAX_C;
        else
            bad[lp[x]].push_back(mask);
    }

    for(int l = m; l < k; l += m){
        int sz = 0;
        while(sz < m && primes[l]*primes[sz] <= C) sz++;
        for(int mask = 0; mask < 1<<sz; mask++)
            c[mask] = 0;

        for(int i = l; i < min(k ,l + m); i++)
            for(int&x : bad[i])
                c[((1<<sz)-1) & x] |= 1<<(i-l);

        for(int mask = (1<<sz)-1; mask; mask--)
            for(int i = 0; i < sz; i++) if(mask>>i&1)
                c[mask^(1<<i)] |= c[mask];

        for(int mask = 0; mask < 1<<sz; mask++)
            b[sz][mask] += __builtin_popcount(c[mask]);
    }

    for(int i = 0; i < m; i++){
        for(int mask = 0; mask < 1<<i; mask++)
            a[mask + (1<<m) - (1<<i)] += b[i][mask];
        for(int mask = 0; mask < 1<<m; mask++) if((mask>>i&1) == 0)
            a[mask] += a[mask^(1<<i)];
    }
    for(int mask = 0; mask < 1<<m; mask++)
        a[mask] += b[m][mask];

    pair <int ,int> ans = {MAX_C ,0};
    for(int mask = 0; mask < 1<<m; mask++)
        ans = min(ans ,make_pair(a[mask] + __builtin_popcount(mask) ,mask));

    printf("%d\n",ans.first);
    for(int i = 0; i < m; i++) if(ans.second>>i&1)
        printf("%d ",primes[i]);
    for(int i = m; i < k; i++){
        for(int&x : bad[i]) if((x&ans.second) == ans.second){
            printf("%d ",primes[i]);
            break;
        }
    }
    printf("\n");
}

int main()
{
    for(int i = 2; i <= MAX_C; i++) if(lp[i] == -1){
        for(int j = i; j <= MAX_C; j += i)
            lp[j] = lp[j] != -1? lp[j] : primes.size();
        primes.push_back(i);
    }

    int t;
    scanf("%d",&t);
    while(t--)
        solve();
}

Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
//#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			cout<<g<<" abc "<<((int)(g))<<endl;
			cerr<<g<<" abc "<<((int)(g))<<endl;
			fflush(stdout);
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
 
bool primus[7605];
int a[7505];
int sum_c=0;
int great=3000,greatcount=0;
vi ffew;
vi pp[7505];
int cntr[7605];
 
int here[7505];
int fans[1<<23];
vi tens[25];
void solve() {
	int n=readIntSp(1,7499),c=readIntLn(n+1,7500);
//	int n=7499,c=7500;
//	int n,c;
//	cin>>n>>c;
	memset(here,0,sizeof(here));
	fr(i,1,c)
		pp[i].clear();
	fr(i,1,n) {
//		cin>>a[i];
		if(i!=n)
			a[i]=readIntSp(2,c);
		else
			a[i]=readIntLn(2,c);
		here[a[i]]=1;
	}
	fr(i,2,c)
		if(here[i])
			for(int j=2*i; j<=c; j+=i)
				here[j]=0;
	vi red;
	fr(i,2,c)
		if(here[i])
			red.pb(i);
	n=sz(red);
	int ms=0;
	while(ffew[ms]*ffew[ms+1]<=c)
		ms++;
	memset(fans,0,(1<<ms)*sizeof(int));
	int lp=0;
	while(ffew[lp]<=c)
		lp++;
	rep(i,0,lp)
		pp[ffew[i]].clear();
	sum_c+=c;
	assert(sum_c<=100000);
	if(c>great)
		greatcount++;
	assert(greatcount<=1);
	for(int i:red) {
		int mask=0;
		for(int j=0; j<ms; j++)
			if(i%ffew[j]==0) {
				mask|=(1<<j);
				while(i%ffew[j]==0)
					i/=ffew[j];
			}
		int te=sqrt(i)-1;
		while(te*te<i)
			te++;
		if(te*te==i)
			i=te;
		pp[i].pb(mask);
	}
	int troll=1;
	for(int i=ms; i<lp; i+=62) {
		int ppu=0;
		while(ffew[ppu]*ffew[i]<=c)
			ppu++;
		tens[troll].assign((1<<ppu),0);
		for(int l=0; l<62&&i+l<lp; l++)
			for(int k:pp[ffew[i+l]])
				tens[troll][((1<<ppu)-1)^k]|=(1LL<<l);
		for(int l=0; l<ppu; l++)
			for(int j=0; j<(1<<ppu); j++)
				if((j>>l)&1)
					tens[troll][j^(1<<l)]|=tens[troll][j];
		for(int i=0; i<(1<<ms); i++)
			fans[i]+=__builtin_popcountll(tens[troll][i&((1<<ppu)-1)]);
		troll++;
	}
	int ppu=ms;
	tens[0].assign((1<<ppu),0);
	for(int i:pp[1])
		tens[0][i^((1<<ppu)-1)]+=100;
	for(int l=0; l<ppu; l++)
		for(int j=(1<<ppu)-1; j>=0; j--)
			if((j>>l)&1)
				tens[0][j^(1<<l)]+=tens[0][j];
	for(int i=0; i<(1<<ppu); i++)
		fans[i]+=tens[0][i];
	for(int i=0; i<(1<<ppu); i++)
		fans[i]+=__builtin_popcount(i);
	int bestans=infi,mask=0;
	for(int i=0; i<(1<<ms); i++)
		if(fans[i]<=bestans) {
			bestans=fans[i];
			mask=i;
		}
	troll=1;
	vi ans;
	for(int i=ms; i<lp; i+=62,troll++)
		for(int j=0; j<62; j++)
			if((tens[troll][mask&(sz(tens[troll])-1)]>>j)&1) {
				ans.pb(ffew[i+j]);
			}
	for(int j=0; j<ms; j++)
		if((mask>>j)&1)
			ans.pb(ffew[j]);
	cout<<sz(ans)<<endl;
	for(int i:ans)
		cout<<i<<" ";
	cout<<endl;
}
 
 
 
void pre() {
	memset(primus,1,sizeof(primus));
	primus[0]=primus[1]=0;
	fr(i,2,7600)
		if(primus[i]) {
			cntr[i]=sz(ffew);
			ffew.pb(i);
			for(int j=i*i; j<=7600; j+=i)
				primus[j]=0;
		}
}
signed main() {
	pre();
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=readIntLn(1,1000);
//	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
1 Like

This algorithm may be defeated by some specially constructed test case, but I do know that my Python solution is (at posting) the fastest 100% solution on the board, using the following steps:

  • Precalculate the prime divisors of the numbers up to 7500.
  • For a given list, reduce each entry to the square-free number with the same divisors (using sets to eliminate duplicates)
  • Cycle around:
    • Find any prime entries; add that value to the B list and remove that entry and any others divisible by that prime
    • Count how often each prime occurs as a factor in the whole list, looking for primes that only occur once (lone primes)
    • For each entry with only lone primes, we can pick one prime, add it to the B list and remove the entry
    • For each entry with some lone primes, replace it with the product of non-lone primes since it’s never better to use the lone primes as its divisor. (note this may produce a prime entry or revise the “lone prime” definition, hence the cycle)
  • Once the list is not changing, work through combinations of possible primes for the remaining items - I do this fairly slowly, so could improve the speed if needed, but the list is usually short by this point.

Example:

  • Given A = [64,75,105,98]
  • Squarefree : [2,15,105,14]
  • 2 is prime (B=[2]) & divides 14
  • Reduced: [15,105]
  • prime counts: [3:2, 5:2, 7:1]
  • 105 has lone prime, reduce to 15
  • Reduced set: [15]
  • prime counts: [3:1, 5:1]
  • 15 is all lone primes, pick one: B = [2,3]
    … so no need for combination hunting in this case.

So the improved verion now uses recursion to avoid trudging through prime combinations. Once the decision cycle above has reduced the set as far as possible, the same process is invoked on two modified candidate sets; one with the most-commonly-used prime added, and one with that same prime divided out wherever it occurs. The smaller resulting B set is used in combination with the existing values.

For the particular test set used with this problem, there isn’t a noticeable performance change, but I think recursion is a better general solution since it uses the selection optimization cycle repeatedly.

I made a couple more optimizations to treating the list after prime removal, including cases where the most popular prime is sufficiently dominant to require its use and a special case where every prime participates in 2 entries and every entry is the product of two primes. Mostly this effort was inspired by test case 10, which remains about 3x slower than the other cases.

However I also realized that this is in fact a set cover optimization problem, which is NP-hard, so I shouldn’t necessarily expect to achieve a consistent running time reduction below a certain level.