HIRINGWO - Editorial

editorial
, , , ,
15

I was also stucked in same approach. Your solution is trying to assign single worker to every task except two tasks with worker a and b such that lcm(a,b) = no of days. And total no of workers = a+b+ no of days -2. But think of a solution in which lcm(a,b,c)= no. of days such that total number of workers a+b+c + no of days - 3 is smaller.

1 Like
16

Thanks Got it.

17

it is 6 => 2+3+1

18

Can anyone please explain how to brute force partition?

2 Likes
19

Never thought dp would be used to minimize the sum. I just had the observation of lcm and all pairwise gcd’s as 1 and here is a beautiful solution :slight_smile:

As everytime, I love your editorials Taran bhaiyya!

3 Likes
20

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);
    }
  }
}
10 Likes
22

14 and 15

1 Like
23

arr[]={14,15};

1 Like
24

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.

25

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
26

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

27

This doesnot ensure that LCM at the end you get is X , Try it on K=2 and X=36

2 Likes
28

@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
29

Why is it neceassary that pairwise gcd should be 1 ?? should nt it be GCD of all elements should be ?/

30

I was stuck with the same approach too! :frowning_face:

31

Thank you bro. Got TLE but understood brute force partition

32

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
33

I solved it using something similar to multisource bfs…
My Submission

2 Likes
34

2 1024
ans :1024 1
but your code will give 16 , 64 which is wrong

35

Glad you liked it!

1 Like