For brute force partition run two nested loops and remove a[i] and a[j] from the array and insert (a[i] * a[j] ) into the array. Repeat the process until you get the desired size.
Spoiler
// left is number of times we need to compress the array
void partition(int left, vector <ll> v1){
if(left==0){
ll temp=0;
for(auto itr: v1){
temp+=itr;
}
sum=min(sum,temp);
return;
}
for(ll i=0;i<v1.size();i++){
for(ll j=i+1;j<v1.size();j++){
vector <ll> v2;
v2.pb(v1[i]*v1[j]);
for(ll k=0;k<v1.size();k++){
if(k!=i && k!=j){
v2.pb(v1[k]);
}
}
partition(left-1,v2);
}
}
}
I did the following bruteforce when K < N, can anyone prove/disprove that it works?
Let B be list of distinct prime powers. For every permutation of B,
start with a list with K1's and keep multiplying greedily a prime power from B to the minimum in the list.
@he1senberg I also had the same approach in my mind but this will not work when the product you are adding back to the heap exceed the largest number present in the heap every time.(reason may or may not be correct)
For example take this for k=3
5 * 8 * 11 * 23 * 27 => 11 * 23 * 27 * 40 => 27 * 40 * 243 => 310 output
but the correct answer will be (5,23) in one group, (8,11) in another and 27 in the last group which makes the output equals to 230 which is less than the previous one.
Let’s take pairwise gcd is not 1
Let’s assume that in the X given there are m powers of 2 available.
Let’s take two groups G1, G2 for which gcd is not 1 so we have two cases
1st Case:
G1 has m powers of 2 and G2 has n(<=m) powers of 2 and rest all the groups don’t have any power of 2 so lcm will be containing m powers of 2 which is fine but let’s say we remove those n powers of 2 from G2 we still got m powers of 2 in lcm because of G1 but the sum in this case will be less as compared to previous one as G2 becomes less from its initial value. So for this case it seems that if they will attain the minimum sum when pairwise gcd becomes 1.
2nd Case:
G1 has n1(<m) powers of 2 and G2 has n(<=n1) powers of 2 and rest all the groups don’t have any power of 2 so lcm will be containing n1(<m) powers of 2 which is not fine as lcm must have m powers of 2.
So our assumption of having pairwise gcd not equal to 1 is wrong so for minimum sum pairwise gcd has to be 1.
Eg for test case:
3 30
Your smallest pair will be 6, 5
So your ans would be 6+5+(3-2) = 12
But 30 can be split into 3,2,5 so the ans would be 3+2+5 = 10
Hence results in WA
For n <K
i put n-k elements into max heap and rest k elements into set , and then one by one take elements from heap and min elements of set and then insert their product in set .
like if my primefactors are 2 3 5 7 and k is 2
my priority queue will contain 3 2 and set will contain 5 7
then first i take 3 from queue and multiply it with min element of set i.e… 5 and insert 15 into set such that my set is know 7 15 .
then again i take 2 and multiply it with 7 and then my final set is 14 15
ans my ans is 14+15 = 29.
but i get WA
plz anyone give test case , where my logic fails
