Coprime Components. Please share your idea on how to solve this task for 100 points.
Just wait… SnackDown 1A has a problem similar to it.
Got stuck too. I would love to know the idea behind it. Solved it by just connecting the 200 numbers with the largest degree to other numbers. Man, the tests are weak as hell.
1 Like
can you please elaborate
- Pre-calculate all prime divisor for each number. (sieve)
- For each number X get its simplest form (i.e. p1 * p2 * p3 instead of p1^a1 * p2^a2 * p3^a3) because for the current problem these are the same.
- Remember how many of the same numbers are (after translation) (There can be maximum ~ 121K of such numbers)
- Initialise DSU (disjoint union set) structures.
- Break early if the array contains number “1” - as all other numbers will be just joined together into single group.
- Allocate as required bit-set array for each prime (sufficient length to cover 121K bits) there are maximum <20K such primes so total memory ~ 256M max. The structure contains up to 121K/64 ~ 1900 long long ints. For each bit-set set i-th bit if the i-th number contains this prime.
- Sort the vector of the numbers with less primes first , then sort by primes themselves.
- Now run cycle from 0 to Nx(the new N which is <= original N) and for each number - get primes that are in this number and on the fly do OR of the bit-sets for these primes.
- Run it for range i+1,Nx, but obviously /64 as each long long int is 64 bit
- Skip any if the current qword is all 1s, If not - run bit mask to check which number is free of primes from x-ith. Then just do union of x and y
- Break early if total number of unions is 1.
- At the end count number of unions and for each union which is size 1 and not united to anything add its size (number of these numbers) minus one to the results. I.e. if there are 3 identical primes in the original array and they are not joined - then we have 2 more free groups to add. Report the final result.
Tons of opportunities for optimisation, but actually not required as the max time ~ 0.15 seconds.
I really liked the problem. Thanks to the author.
4 Likes
On top of 30 point solution I explicitly checked if the sequence contains at least one prime number greater than one half of the largest number in the sequence. If there is such number then there is only one connected component. It helped to get 100 points. Not sure if this is by design or just because test cases weren’t strong enough.
For 30-point solution I converted each number in the sequence into the number with square free factorization. It helped to reduce the sequence size a bit. To loop through neighbors in DFS faster, I used prefix tree based on prime factorization.
If there is atleast 1 prime number in the input array , i will pick one prime number and also i will find all the numbers whose gcd with our current prime number is 1 , at the same time i will erase those numbers from the multiset (initially i inserted all the input elements into it) ! Now they will be in a single component , for the rest of the elements , they wont form components among themselves (because , they all are having our picked prime number as their prime factor ) ! Either they will join the earlier component (because there can be some integer in the formed component whose gcd with our current element is 1) or they will form a separate component each of size 1 ! This can be done by inclusion-exclusion in O(64) time (I mean , checking whether there is an element in the initial component whose gcd with our current element is 1) ! If there are no primes in the input array , i will just find the components using BFS !
Feel free to ask if you have any doubts !
2 Likes
Can you provide a proof for pt 121k ?? And I will stop complaining about weak TC. Only 3 TC (for 50 pts) had no of distinct no <5k and for them I bf. For others answer was simply no of set with size 1 + one large set containing rest of elements.
If possible please prove that above assumption is correct. I will take back my claim of weak TC.
70pts. This is correct except for case when all no are same no and that no is prime >max/2.
I also used inclusion exclusion principle to find which no for a singleton set.
And added one assuming that rest of no form a single large set. Sadly this passes for all test cases except 4 ( 1 from smallest set anf 3 from largest ). But all test cases had no of unique no < 5000 ( after reducing then as used by @lboris simply used if else and brute forced for these tc to get 100 pts.
ohh ! I had hard time with this question bro , felt that the tc are really weird !
Yes, I also separately checked for the existence of 1 in a sequence and whether all numbers are same (and not equal to 1). Otherwise when there are no primes > max/2, DFS based solution didn’t TLE. I tested using a sequence of all numbers 1 to 200,000 excluding all primes greater than 100,000.
Regarding the 121k in @lboris answer, and to answer @aryanc. You can easily verify this for yourself by just writing a program like
# O(n) prime sieve, computes least prime factor
lim = 200000
lp = [0]*(lim+1)
pr = []
for i in range(2,lim+1):
if lp[i] == 0:
lp[i] = i
pr.append(i)
for p in pr:
if p>lp[i] or i*p > lim:
break
lp[i*p] = p
def factor(n):
while n>1:
yield lp[n]
n //= lp[n]
def prod(A):
p = 1
for a in A: p *= a
return p
n = 2*10**5
A = range(1,n+1)
# reduce to radical, i.e. remove prime multiplicities
A = set(prod(set(factor(a))) for a in A)
print(len(A))
which will print 121581.
1 Like
@aryanc403 See my answer https://discuss.codechef.com/questions/137838/please-share-your-approach-to-cpcomp-problem-of-oct-long-challenge/137882
1 Like
Thank you very much. Can you write one program which can split these no in 2 sets which has nos like. {2.3.5,7.11.13,17.19.23} and {7.3.5,17.11.13,2.19.23} these 2 sets are 2 different conected components. And nos like these were present in 4 test cases. But those TC has no of unique no less than 5k so brute force for them was enough. And that is the reason why I’m complaining for weak TC.
You can reduce the number of primes this way. First, you need to use an O(n log log n) prime sieve.
-
If 1 is in the set, then there is one component.
-
Record the number of instances, n, of each number x. If in the end, the number is in a component of size one, then there are n components. If the number is in component of size > 1, then all numbers in the component contribute to a single component (the number of instances don’t matter).
-
Reduce multiple powers of a prime to one.
-
If a prime is either unique to particular number or functionally dependent on another prime (a prime always occurs with another prime), you can erase that prime from all the numbers. That is, remove the prime from each number that is a multiple of that prime and add all the instances of that number to the new number without the prime factor. (Be careful if two primes always co-occur; get rid of one)
2a) After erasing the prime p from number x, the new number becomes x’=x/p without the prime. If x’ is the only number left, then the number of instances of x’ is the final answer.
2b) If x’ becomes 1, then all the other numbers are in in the same component as x’ and the answer is 1.
- Find all numbers that contain just one prime and toss them into a hashset. All these primes together belong to the same component C.
3a) If the number of primes is in the hashset is greater than 7, the final answer is one component.
3b) If the product of all those primes is greater the largest number in whole set, then the final answer is one component, because each number from the whole set will be missing at least one prime from the hashset.
3c) Go through all the other numbers. If that number does not contain all the primes in the hashset, then add that number to the component C.
3d) Later in the search phase when we compare numbers together, we can ignore all the primes in hashset, because we tested them already. You can also ignore any number that contained at least one prime from the hashset, because all the other numbers not in component C will have contained every prime from the hashset as a factor and there not be coprime.
After this, the number of distinct numbers has fallen sharply. We also eliminated a large number of candidates to pair off from step 3d. This is important because, if the test cases weren’t weak, there would be O(n^2) number of pairs that are coprime. So, testing neighbors would TLE even if using a prefix tree solution to prune neighbors. The number of valid neighbors would still be O(n^2).
We can take advantage of another optimization. The number of components–ignoring multiple instances of the same numbers–will be very small.
Then, you can build a disjoint set (union-find data structure). Although, I didn’t brute force, I suspect it would not TLE. The number of values to compare will be a tiny fraction of the original set. You can compare each number to a small group (~20) of numbers containing the least frequent primes. You can also AC by comparing each number to 20 randoms numbers like I did after grouping numbers by their lowest prime factor and not comparing those within the same group.
@algmyr - thanks for the nice clarification with example, just saw the comment, but you already answered it. @aryanc403 , I hope it is clear now. And yes, probably the most complex case could be constructed (without 1 and any primes > 100K or even 60K ), I’m also agree that the test cases were a bit weak, specially initially, and then later adjusted a bit.
2 Likes
The sets you’re describing (triplets) will not be large at all. You can only continue until the product exceeds 2 \times 10^5. This means the smallest factor can’t be larger than around 60.
One observation that severely limits things is that you can’t have too many unique primes among your numbers. If you have > 6 unique primes in your list you’re already forcing numbers > 2\times10^5 for things not to be connected.
Btw, the test data seems pretty weak. Some accepted solution will receive TLE or WA for the following data:
vector<int> ans;
void gen(int a,int b,int c,int d)
{
for(int w=0;w<=200000;w+=a*b)
{
if(w%c==0||w%d==0) continue;
ans.push_back(w);
}
}
int main()
{
gen(2,3,5,7);
gen(5,7,2,3);
gen(3,7,2,5);
gen(2,5,3,7);
gen(2,7,3,5);
gen(3,5,2,7);
printf("%d\n",int(ans.size()));
for(auto x:ans) printf("%d ",x);
puts("");
}