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