HIRINGWO - Editorial

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

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

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.

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,

Try this

1
3 90

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

Thanks bro got it.

1 Like

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

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

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

Thank you very much

Did this approach work?
It seems correct.

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

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;
}

How can the answer be 12?
The lcm will be 36.
First we will multiply 2^2 to 1 because 1 is minimum in the array and then we will multiply 3^2 to 1. So the lcm will be equal to X.
Correct me if i am wrong

request :
Can anyone provide the test case for which my solution fails ??
code CodeChef: Practical coding for everyone

upd : sorry my fault link is updated.

logic :
I took all the prime to there raised power for example 224 I represented it as (2^5) * (7^1), for 30 I represented it as (2^1) * (3 ^ 1) * (5 ^ 1) since they all are the power of prime so there can never be more than 7 values. so it took all these values and also 1 and did a brute force.

additional work done:
I also checked my solution by making a generator and checking on the setter solution and it looks fine to me. I would request If someone can give a look provide some feedback (sample case on which it fails).

Your link is not showing your code

sorry my fault I have updated the link

Your code have 1 or 2 syntax error. Apart from that it is giving wrong at:
1
1 90

Your is getting wrong at :
1
2 90

Answer is 19 but your code is giving 91.

input for K is greater than 1