Difficulty
Hard
Problem
Solution
Lets solve another problem.
We are given a list containing n non-negative integers where each integer is less than or equal to n. We are allowed to perform only one kind of operation on this list, in a single step we can choose some integer x and subtract it from all the elements of the list which are greater than or equal to x. Now we want to find out the minimum number of steps in which we can make all the elements of the list equal to 0.
This problem can be solved in O(n^2\cdot 2^n) time using dp with bitmasking. We can represent any list by an integer, we will simply set the bit corresponding to all the numbers which exist in the list, i.e. j^{th} bit of integer equivalent of the list will be set only if j is present in the list. For example 1 is the integer equivalent of a list containing only 0s and 6 is the integer equivalent of list containing only 1s and 2s.
Lets assume that i is the integer equivalent of our list, if we subtract the elements of the list by some integer x (as per the above described operation), we will obtain a new list and let’s say its integer equivalent is equal to j, so we can use the recursive relation dp[i] = min(dp[i],1+dp[j]). In simple words, we just iterate over all the values of x, we find the integer equivalent corresponding to the list obtained after performing the operation using x and apply the recursive relation mentioned above. Our base case is dp[1] = 0, as we know that 1 is the integer equivalent of a list containing only 0s.
The original problem can be reduced into the above problem. The list, we were talking about is actually the list containing the highest powers for a prime number which appear as factors in the elements of arr. So we just have to solve the above mentioned problem for the list corresponding to each prime number.
Time complexity
It is a bit difficult to guess the time complexity of this solution, but some mathematical analysis shows that it should be somewhat close to O(200n(log_2n)^2) for big values of n, so it will most probably give TLE with the existing constraints.
Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
vector<int>exp2(21,1);
for(int i=1; i<=20; i++)
exp2[i]=2*exp2[i-1];
const int N=1e6;
vector<int>sieve(N+1,1);
for(int i=2; i<=N; i++){
if(sieve[i]==1){
for(int j=1; i*j<=N; j++){
sieve[i*j]=i;
}
}
}
int n;
cin>>n;
map<int,set<int> >rel; //stores the powers corresponding to prime numbers
for(int i=0; i<n; i++){
int num;
cin>>num;
while(num>1){
int div=sieve[num];
int count=0;
while(num%div==0){
num/=div;
count++;
}
rel[div].insert(count);
}
}
int ans=0;
for(auto var : rel){
int up=*prev(var.second.end());
int mask=0;
for(int j=1; j<=up; j++){
if(var.second.count(j)){
mask+=exp2[j];
}
}
vector<int>dp(mask+1,1e9);
dp[1]=0;
dp[0]=0;
for(int i=2; i<=mask; i++){
for(int j=1; j<=up; j++){
int num=1;
for(int k=1; k<=up; k++){
if(j>k){
num+=(i&exp2[k]);
}
else{
if((i&exp2[k]) && ((num&exp2[k-j])==0)){
num+=(exp2[k-j]);
}
}
}
dp[i]=min(dp[i],1+dp[num]);
}
}
ans+=dp[mask];
}
cout<<ans;
return 0;
}