PROBLEM LINK:
Setter: Erfan Alimohammadi
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
PREREQUISITES:
Meet in the middle, prime factorisation, SOS dp.
PROBLEM:
Given an array A of n numbers ,construct a graph of n vertices by adding edges between $i$th and $j$th vertex (i \lt j) if and only if A_i* A_j is not divisible by a cubic number. Find number of cliques in this graph (note empty clique with no vertices is also counted).
EXPLANATION
If a number is divisible by a cubic number, then its prime factorisation contains a prime which occurs more than 2 times.
Firstly we will find prime factorisation of each of the N numbers and store them. Complexity of finding factorisation is O(\sqrt{A_i}) for i th number. Complexity of finding factorisation of all N numbers is O(N*\sqrt{A_{max}})
Now, iterate over all pairs of (i,j) such that (i \lt j) and combine their prime factorisations to obtain prime factorisation of A_i*A_j and check if any prime occurs more than 2 times in prime factorisation of A_i*A_j. If yes, then do not add edge between i and j otherwise add an edge between i and j. Each number has at most log(A_{max}) terms in prime factorisation. Hence, complexity of this step is O(n*n*log(n)).
Now, we have a undirected graph with n vertices. We want to find number of cliques in this graph.
Since n can be upto 40, we can encode adjacency list of each vertex in a bitmask of length n (long datatype would suffice). (In adjacency bitmask of ith vertex,we will also mark ith bit, we will see why so in a moment).
Now to check if a subset of vertices represented by mask p forms a clique. We want all of them to be connected to everything else in p. So now, every element in p must be adjacent to every other element. Here is where marking i th bit in adjacency bitmask of i will help. Now , we want p to be submask of the adjacency bitmasks of vertices present in p. So we can check this in O(n) for a single bitmask p.
Let us find for each subset of \{1,2,3,...,n/2\}, if it is clique or not (we will represent subsets using n/2 length bitmask). Checking for each mask takes O(n) time. Checking for all the masks takes O(2^{n/2}*n) time.
Now we know for each subset of first n/2 elements, if it is a clique or not. (Let us call this B array and its 1 if clique can be formed for this mask otherwise 0).
Similarly we can calculate for each subset of last n/2 vertices, if it is a clique or not.
Now, we will find for each mask of first n/2 elements, number of submasks of this mask which are cliques i.e for each mask m, we want summation of B[p] where p is submask of m.
This is a standard problem solved by SOS dp. Complexity is O(2^{n/2}*n).
Now, we have for each subset of first n/2 vertices, how many subsets of that subset are cliques.
We will iterate over all subsets of last n/2 vertices. And for each mask p, we will find count of masks p1 of first n/2 vertices such that vertices from p and p1 together form clique. Let us call the vertices from p and p1 together as set S.
We will identify some necessary conditions for vertices from p and p1 together to form a clique.
Condition 1: vertices from p need to form a clique
Condition 2: all vertices from p1 must be adjacent to all the vertices in p.
Condition 3: vertices from p1 need to form a clique.
Now, Lets prove these are sufficient.
Condition 1 and 2 state that all vertices from p have edges to all vertices in S (obviously except self edge).
Condition 2 and 3 state that all vertices from p1 have edges to all vertices in S (obviously except self edge).
Hence, S forms a clique if and only if above all conditions are true.
So we will iterate over subsets of last (n/2) vertices. And consider only those mask p that satisfy condition 1.
So now, we will find all vertices belonging to first (n/2) vertices which are adjacent to all vertices in p. Lets say this set of vertices are represented by mask p2. Now any subset of p2 combined with p satisfy condition 2. And no other subset of first n/2 vertices combined with p satisfy condition 2. Now, we want to find number of subsets of p2 that are cliques (Because p1 is a clique). Yayy!!, we have solved this above using SOS dp.
NOTE: “we will find all vertices belonging to first n/2 vertices which are adjacent to all vertices in p.” for this, we will take bitwise and of all the adjacency bitmasks of vertices in p and take first n/2 bits of it. This take O(n) complexity per mask. And after finding p2, it will take O(1) comp$O(nnlog(n))$lexity because we already know count of cliques in each mask of first n/2 vertices. So total complexity across all subsets of last n/2 vertices is O(2^{n/2}*n).
TIME COMPLEXITY
O( n*n*log(n) + n*\sqrt{A_{max}} + 2^{n/2}*n).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 43;
const int MAXDPSIZE = (1 << (MAXN / 2)) + 10;
int t, n, m, a[MAXN], firstPartNeighbors[MAXN];
long long dp[MAXDPSIZE], ans;
bool isClique[MAXDPSIZE], mat[MAXN][MAXN];
unordered_map<int, int> factorsMap;
set<pair<int, int> > factorsSet;
void factorize(int x) {
for (int i = 2; i * i <= x; i++)
while (x % i == 0) {
factorsSet.erase({i, factorsMap[i]});
factorsMap[i]++;
factorsSet.insert({i, factorsMap[i]});
if (factorsMap[i] >= 3) //for optimization
return;
x /= i;
}
if (x > 1) {
factorsSet.erase({x, factorsMap[x]});
factorsMap[x]++;
factorsSet.insert({x, factorsMap[x]});
}
}
bool adjacent(int x, int y) {
factorsMap.clear();
factorsSet.clear();
factorize(x);
factorize(y);
for (auto i: factorsSet)
if (i.second >= 3)
return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
memset(mat, 0, sizeof mat);
memset(firstPartNeighbors, 0, sizeof firstPartNeighbors);
int half = n / 2;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (adjacent(a[i], a[j])) {
if (j < half)
firstPartNeighbors[i] |= (1 << j);
if (i < half)
firstPartNeighbors[j] |= (1 << i);
mat[i][j] = mat[j][i] = true;
}
isClique[0] = true;
for (int mask = 1; mask < (1 << half); mask++) {
int v = __builtin_ctz(mask);
int mask2 = (mask ^ (1 << v));
if (!isClique[mask2]) {
isClique[mask] = false;
continue;
}
isClique[mask] = true;
for (int i = 0; i < half; i++) {
if ((mask2 & (1 << i)) && !mat[v][i]) {
isClique[mask] = false;
break;
}
}
}
dp[0] = 1;
for (int mask = 1; mask < (1 << (n - half)); mask++) {
int v = __builtin_ctz(mask);
int mask2 = (mask ^ (1 << v));
dp[mask] = dp[mask2];
int mask3 = 0;
for (int i = 0; i < n - half; i++)
if (mat[v + half][i + half] && ((1 << i) & mask))
mask3 |= (1 << i);
dp[mask] += dp[mask3];
}
ans = 0;
for (int mask = 0; mask < (1 << half); mask++) {
if (!isClique[mask])
continue;
int mask2 = 0;
for (int i = half; i < n; i++) {
if ((firstPartNeighbors[i] & mask) == mask)
mask2 |= (1 << (i - half));
}
ans += dp[mask2];
}
cout << ans << endl;
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
vector< map<int,int> > mapi(100);
int gg[100];
int good1[(1<<21)+10],wow[100],haha[100],bad[100][100];
int a[123];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
rep(i,n){
cin>>a[i];
gg[i]=0;
}
int j;
rep(i,n){
mapi[i].clear();
for(j=2;j*j<=a[i];j++){
while(a[i]%j==0){
mapi[i][j]++;
a[i]/=j;
}
}
if(a[i]!=1){
mapi[i][a[i]]++;
}
}
map<int,int>::iterator it;
rep(i,n){
for(it=mapi[i].begin();it!=mapi[i].end();it++){
if(it->ss>=3){
gg[i]=1;
}
}
}
rep(i,n){
rep(j,n){
bad[i][j]=0;
}
}
rep(i,n){
f(j,i+1,n){
if(gg[i] || gg[j]){
bad[i][j]=1;
bad[j][i]=1;
}
for(it=mapi[j].begin();it!=mapi[j].end();it++){
if(mapi[i].find(it->ff)!=mapi[i].end() && mapi[i][it->ff]+it->ss>=3){
bad[i][j]=1;
bad[j][i]=1;
break;
}
}
}
}
if(n==1){
cout<<2<<endl;
continue;
}
int part1=n/2;
int part2 = n-n/2;
rep(i,n){
wow[i]=0;
}
rep(i,(n/2)){
rep(j,n/2){
if(!bad[i][j]){
wow[i]|=(1<<j);
}
}
}
int ans,ans1;
ll tot=0;
rep(i,(1<<part1)){
good1[i]=0;
ans=(1<<part1)-1;
rep(j,part1){
if((1<<j)&i){
ans=ans&wow[j];
}
}
if((ans&i)==i){
good1[i]=1;
}
}
rep(i,part1){
rep(j,(1<<part1)){
if(j&(1<<i)){
good1[j]+=good1[j^(1<<i)];
}
}
}
rep(i,n){
wow[i]=0;
haha[i]=0;
}
rep(i,part2){
rep(j,part2){
if(!bad[i+part1][j+part1]){
wow[i]|=(1<<j);
}
}
//cout<<wow[i]<<endl;
}
rep(i,part2){
rep(j,part1){
if(!bad[i+part1][j]){
haha[i]|=(1<<j);
}
}
}
rep(i,(1<<part2)){
ans=(1<<part2)-1;
ans1=(1<<part1)-1;
rep(j,part2){
if((1<<j)&i){
ans=ans&wow[j];
ans1=ans1&haha[j];
}
}
if((ans&i)==i){
tot+=good1[ans1];
}
}
// if(tot>1e8){
// assert(0);
// }
cout<<tot<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 