HIRINGWO - Editorial

Please help me out: Can’t get it where am I going wrong. Please help somebody. My code passes various test cases but I am unable to figure out where it is getting wrong.

#include <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
int mod = 1000000007;

int lcm(int a, int b)
{
    return (a / __gcd(a, b) * b);
}

int func(int n)
{
    for (int i = (int)(sqrt(n)); i >= 1; i--)
    {
        if (n % i == 0 && lcm(i, n / i) == n)
        {
            return i;
        }
    }
    return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    t++;
    while (--t)
    {
        int k, x;
        cin >> k >> x;
        map<int, int, greater<int>> v;
        v[x]++;
        while (true)
        {
            int count = 0;
            for (auto iter = v.begin(); iter != v.end(); iter++)
            {
                int a = func(iter->first);
                int num = iter->first;
                if (a == -1)
                {
                    continue;
                }
                else
                {
                    v.erase(iter->first);
                    if (a != 1)
                        count++;
                    v[a]++;
                    v[num / a]++;
                    break;
                }
            }
            if (count == 0 || v.size() == k)
            {
                break;
            }
        }
        int ans = 0;
        int count = 0;
        for (auto iter = v.begin(); iter != v.end(); iter++)
        {
            // cout << iter->first << " ";
            ans += iter->first;
            count++;
        }
        ans += (k - count);
        cout << ans << endl;
    }
    return 0;
}

isn’t it TLE? its time complexity is O( (7!)^2 ) .

Suppose the size of the array is N, so the total number of arrays of size (N-1) by merging two elements of given array will be (N*(N-1)) . Repeat the same procedure with all the (N*(N-1)) to further reduce the size of array until you get the desired size.

Also the size can’t be less than 2.

Calculating Complexity
 N*(N-1) * (N-1)*(N-2) * (N-2)*(N-3) * (N-3)*(N-4) * (N-4)*(N-5) ......

Since there are atmost 7 prime powers, substitute the value of N=7 in the above formula so in worst case there will be (42 * 30 * 20 * 12 * 6) iterations. You can multiply the value with the number of testcases i.e. T=40.

And the number of iterations are less enough to avoid TLE.

1 Like

Thank you. It helped:)

(CodeChef: Practical coding for everyone)

can anyone help me out finding where I am wrong, any test cases will be helpful, thanks .

Yes please clarify about the time complexity

Thanks for this explanantion

I distribute prime powers, so 36 would divided into 4 and 9, giving answer 13.

Here’s my implementation of that algorithm during contest. CodeChef: Practical coding for everyone

is it necessary for the partition to have consecutive elements of the array A that was constructed

No

idk how to do that k<number of factors part. my code is showing error . can someone help?

https://www.codechef.com/viewsolution/39768485

@taran_1407 Sir, I did not get the part of generating partitions for n values…Is there any standard algo other than partition DP for this thing?And if I do the partition, does it guarantee GCD(Ai,Aj)=1 for every pair thus formed?
Thanks in advance . Also, I would be highly grateful to anyone who might want to answer my doubt.

Your code will work correctly when K>=number of factors but in rest of cases, compressing the array by multiplying smallest numbers doesn’t work always. suppose 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). So you have to consider all the partitions of the array of primes. An easy brute force method for getting optimal partition is given by @cherry0697 in above thread here.

Sorry, I did not get it, why should not I ask for other technique?If you kindly explain…

I am getting the TLE.Please help me.
#include
#include<bits/stdc++.h>
#include
using namespace std;
int recursion(vector li,int k){
vector l;
int actual_size=li.size();
if(k==actual_size)
return accumulate(li.begin(),li.end(),0);
int size=actual_size-1;
if(actual_size%2==0){ //even
for(int i=0;i<actual_size/2;i++){
l.push_back(li[i]li[size-i]);
}
}
else{
for(int i=0;i<actual_size/2;i++){ //odd
l.push_back(li[i]li[size-i]);
}
l.push_back(li[size/2]);
}
sort(l.begin(),l.end());
return recursion(l,k);
}
vector prime_factor(int x){
vector l;
int temp=1;
while(true){
if(x%2==0){
temp
=2;
x/=2;
}
else
break;
}
if(temp!=1)
l.push_back(temp);
for(int i=3;i<=sqrt(x);i=i+2){
temp=1;
while(x%i==0){
x=x/i;
temp
=i;
}
if(temp!=1)
l.push_back(temp);
}
if(x>2)
l.push_back(x);
return l;
}
int main() {
int t;
cin>>t;
while(t–){
int k,x;
cin>>k>>x;
vector li=prime_factor(x);
int sum=0;
if(k<li.size()){
cout<<recursion(li,k)<<endl;
}
if(k==li.size()){
sum=accumulate(li.begin(),li.end(),0);
cout<<sum<<endl;
}
if(k>li.size()){
sum=accumulate(li.begin(),li.end(),0);
cout<<(k-li.size()+sum)<<endl;
}
}
return 0;
}

It’s technically branch and bound (backtracking). Consider a recursive procedure generates all partitions of N values.

Let’s pick one element, and generate all possible partitions for remaining N-1 elements. Now the chosen element can either form a new group, or be added to one of the existing partition, allowing us to generate all partitions.

Since all elements have pairwise GCD 1, and partitioning means each element belongs to exactly one set, no two groups in any partitioning will have GCD > 1

Let k = 4 , X = 12
then acc to u
since , co prime factor of 12 are 2 ,3
then k teams wiil be {1 , 1 , 2 , 3}
and in this way all k teams wiil finish on 6th day as 6 is divisible by each of 4 value
so this approach is wrong

i also did the same bro but consider the test case 2 210
its answer is 29…
i think now u will find ur mistake

Hi I have a trivial doubt.
Why can’t the solution be just equal to “K” as we need to minimize the workers?

Each K team will have only one member which satisfy the constraint that each team shall have atleast one worker, and hence total workers are K.

Each team will submit their work on the AA-th, 2A2A-th, 3A3A-th day etc. And then whatever be the value of “X”, they will meet the work timeline and submit it.

So answer shall be K, as per me.
Please correct me