HIRINGWO - Editorial

editorial
, , , ,
36

Codechef November Cook-Off 2020 Division 1 : Hiring Workers - YouTube made a video on Hiring workers. Give it a watch if you are stuck.

37

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
38

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

39

yes I got it , thanks buddy.

40

Yup, had the same logic. No idea why it’s wrong

41

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.

42

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

43

Great editorial and problem! Also thanks a lot for giving a practice problem too! xD

44

CodeChef: Practical coding for everyone what is wrong with my solution. can anyone give me the countercase?. thanks in advance.

45

Why should we go with 2 +3+5=10? We could also use 2,2,3 as it is not given that two teams can’t have the same number of players which would give the sum as 2+2+3=7 which comes less than 10.

46

question said that number of worker should be minimum I thought why not to distribute 1 member for each task and ans should be equal to k can anyone help me I still cant overcome this approach of mine?
and It was nowhere written that all the task should be completed with minimum rejection.
thank you,

47

Try this

1
3 90

answer must be 16 (2 ,9, 5).

48

Thanks bro got it.

1 Like
49

Couldn’t figure out what test case i am getting wrong :frowning: . I have tried all tc’s listed above .
https://www.codechef.com/viewsolution/39780259

50

Can anyone tell me where i am wrong.
https://www.codechef.com/viewsolution/39780819

51

Hey bro , i just tested your code. you are messing up on
1
1 90
and maybe others of this type.

52

Thank you very much

53

Did this approach work?
It seems correct.

54

cause 2,2,3 lcm is 6. so x=6. which is false.

55

can anyone tell which test case is not working in these code.
#include<bits/stdc++.h>

using namespace std;
#define ll long long
ll gcd( ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}

// Function to return LCM of two numbers
ll lcm(ll a, ll b)
{
return (a / gcd(a, b)) * b;
}

int main() {
// your code goes here
ll t;
cin>>t;
while(t–){
ll k,x,c=0,i=0,j=0,min=1000000000;
cin>>k>>x;
vector v,v1;
int flag=0;
int n=x;
//////////////////////////////////////////////////////////////////////
///////////////////////////////////////// v1 contains prime factor while v contains all factors
while (n%2 == 0)
{
if(flag==0){
flag=1;
v1.push_back(2);
}
else
v1[i]=v1[i]*2;
n = n/2;
}
flag=0;
j=i+1;

for (int i = 3; i <= sqrt(n); i = i+2) 
{ 
    flag=0;
    // While i divides n, print i and divide n 
    while (n%i == 0) 
    { 
         if(flag==0){
    flag=1;
    v1.push_back(i);
    }
    else
    v1[j]=v1[j]*i;


        n = n/i; 
    }
    j++;
} 

// This condition is to handle the case when n  
// is a prime number greater than 2 
if (n > 2) 
    v1.push_back(n); 
    int sum=0;
    for(i=0;i<v1.size();i++)
    {
//        cout<<v1[i]<<" ";
        sum+=v1[i];
    }

/////////////////////////////////////////////////////////////////////////
for ( i=1; i<=sqrt(x); i++)
{
if (x%i == 0)
{
if (i*i == x)
v.push_back(i);

        else  
            {
                               v.push_back(i);
            v.push_back(x/i);

    } 
}
}

// cout<<v1.size()<<" "<<sum;
///////////////////////////////////////////////////////////////
if(k<v1.size()){
for(i=0;i<v.size();i++)
{
for(j=i;j<v.size();j++)
{
c=0;
if(lcm(v[i],v[j])==x){
c=v[i]+v[j]+k-2;
if(c<min)
{
min=c;
}
}
}
}
}
else{
min=sum+k-v1.size();
}
cout<<min<<endl;
}
return 0;
}