arr[]={14,15};
1 Like
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 K 1's and keep multiplying greedily a prime power from B to the minimum in the list.
I used min heap for n>k liKe if x=2×3×5×7×11
Evertime until the size of heap becomes k i popped out top 2 elements and pushed their product
If k=3
2×3×5×7×11=>5×6×7×11=>7×11×30
Can someone explain why i m getting WA?
1 Like
Run it on Case K=2 X=36 you will get 12 as the ans in this case you are dividing into 6 and 6 who actually have LCM 6 not 12
This doesnot ensure that LCM at the end you get is X , Try it on K=2 and X=36
2 Likes
@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.
3 Likes
Why is it neceassary that pairwise gcd should be 1 ?? should nt it be GCD of all elements should be ?/
I was stuck with the same approach too! 
Thank you bro. Got TLE but understood brute force partition
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.
2 Likes
2 1024
ans :1024 1
but your code will give 16 , 64 which is wrong
Glad you liked it!
1 Like
Codechef November Cook-Off 2020 Division 1 : Hiring Workers - YouTube made a video on Hiring workers. Give it a watch if you are stuck.
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
1 Like
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
yes I got it , thanks buddy.
Yup, had the same logic. No idea why it’s wrong
Try out this case prime factors are 5^1 * 2^3 * 11^1 * 23^1 * 3^3 for k =2 output will be 1061 taking (23,27) in one group, (5,8,11) in other group.
i was thinking a different approach.if i can pick two number whose lcm is the given K…then i can take (n-2) number as 1…like for k=15 and n=4 … i take 1st two number 3,5 and last (n-2) number as 1…so ans will be 3+5+1+1…and if we can not find such two number then we will take value k (in this question 15) and last (n-1) number as 1…so for k=7 and n=3 ans will be(7+1+1)…
i submited this logic but got wrong ans.
can anyone tell me what i am missing here and for which test case my code will not work?i will be a big help for me