WA in HIRINGWO

Please help. I’m getting WA in HIRINGWO, although I think that my approach is correct. Can you please help me identify as to what the error in my appraoch/code is :

Approach :
given, K tasks and X days, we have to find K different integers such that :-1:

  1. LCM(A1, A2, … Ak) = X

  2. A1 + A2 + … + Ak = minimum possible

Now my approach is as follows :
=> Lets say K = 180. Then, first step is to find the prime factorization of 180, which is : 2 * 2 * 3 * 3 * 5.
=> Because we want to find the values such that the LCM is X, thus we can’t have two integers out of any of the K integers that have HCF greater than 1. This means that HCF(Ai, Aj) = 1. ( This was stated in the editorial too.)
=> So to implement this what i did was i grouped the factors together, in the following way : (2 * 2) * (3 * 3) * 5. So 180 becomes (4 * 9 * 5) and then i put these values in a Priority Queue

=> lets say X = 3
Then this is our answer (4 + 9 + 5)
=> lets say X > 3
Then we add 1 that number of times (4 + 9 + 5 + 1 + 1 + 1 … )
=> lets say X < 3.
Then we poll the minimum 2 elements from the Priority Queue, and then multiply them to get the new number, and then put it back. We repeat this until the size of the pq becomes equal to our X value

So in this case, we have [4, 9, 5] in the priority queue, and if X = 2, then we will have [20, 9] in the priority queue after this step, because we replace 4 and 5 by (4*5)
and then answer = 20 + 9 = 29

Code : Code Link

Can you please tell me what the problem is!? Why am i getting WA. Is the approach correct?

I have used a similar algorithm and was getting WA. In the last case (X<3)-
i have an array A with X elements each having value 1.
then in decreasing order of my grouped factors i am multiplying it with min of array.
a=[1,1]
f = [9,5,4]
a = [9,1]
a=[9,5]
a = [9,20]
sum(a) = 29

1 Like

Hey! multiplying minimum elements will not always work, you have to generate possible partitions and choose optimally. If we take K=2 and x=210, we have 2,3,5,7 as prime factors, here your code code gives 37 (2x3x5+7) but we can have much optimal answer 29(5x3+2x7). An easy brute force method for getting optimal partition is given in editorial’s thread here.

1 Like

Thanks a lot Vishwas!

1 Like